Engineering Commons^™

Visko: Semantic Web Support For Information And Science Visualization, Nicholas Del Rio, Paulo Pinheiro Da Silva

Departmental Technical Reports (CS)

Constraint Problems: Computability Is Equivalent To Continuity, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we would like to compute the set of all possible values that satisfy given constraints. It is known that even for computable (constructive) constraints, computing such set is not always algorithmically possible. One reason for this algorithmic impossibility is that sometimes, the dependence of the desired set on the parameters of the problem is not continuous, while all computable functions of real variables are continuous. In this paper, we show that this discontinuity is the only case when the desired set cannot be computed. Specifically, we provide an algorithm that computes such a set for all …

Towards Interval Techniques For Model Validation, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

Most physical models are approximate. It is therefore important to find out how accurate are the predictions of a given model. This can be done by validating the model, i.e., by comparing its predictions with the experimental data. In some practical situations, it is difficult to directly compare the predictions with the experimental data, since models usually contain (physically meaningful) parameters, and the exact values of these parameters are often not known. One way to overcome this difficulty is to get a statistical distribution of the corresponding parameters. Once we substitute these distributions into a model, we get statistical predictions …

Propagating Range (Uncertainty) And Continuity Information Through Computations: From Real-Valued Intervals To General Sets, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems of interval computations is to find an enclosure Y that contains the range f(X₁, ..., X_n) of a given function f(x₁, ..., x_n) over given intervals X₁, ..., X_n. Most of the techniques for estimating this range are based on propagating the range through computations. Specifically, we follow the computations of f(x₁, ..., x_n) step-by-step: we start with ranges X₁, ..., X_n of the inputs, and then we sequentially compute the enclosures for the ranges of …

No-Free-Lunch Result For Interval And Fuzzy Computing: When Bounds Are Unusually Good, Their Computation Is Unusually Slow, Ildar Batyrshin, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

On several examples from interval and fuzzy computations and from related areas, we show that when the results of data processing are unusually good, their computation is unusually complex. This makes us think that there should be an analog of Heisenberg's uncertainty principle well known in quantum mechanics: when we an unusually beneficial situation in terms of results, it is not as perfect in terms of computations leading to these results. In short, nothing is perfect.

Extreme Distributions On Intervals, Monchaya Chiangpradit, Wararit Panichkitkosolkul, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main tasks of interval computation is to analyze situations in which we only know the lower and upper bounds on the desired quantity, i.e., we only know an interval that contains this quantity. One of the objectives of such analysis is to make decisions. According to decision theory, a consistent decision making procedure is equivalent to assigning probabilities to different values within each interval. Thus, we arrive at the problem of describing a natural probability distribution on an interval. In this paper, we describe such a distribution for the practically important case of the "weakest link" arrangement, …

A Heuristic For Selecting The Cycle Length For Fairio, Sarala Arunagiri, Y. Kwok, Patricia J. Teller, R. A. Portillo, S. Seelam

Departmental Technical Reports (CS)

FAIRIO is a cycle-based I/O scheduling algorithm that provides differentiated service to workloads concurrently accessing a consolidated RAID storage system. FAIRIO enforces proportional sharing of I/O service through fair scheduling of disk time. During each cycle of the algorithm, I/O requests are scheduled according to workload weights and disk-time utilization history. There are several parameters in the FAIRIO scheduler that can affect its behavior. One parameter in particular, the length of a scheduling cycle, can affect the scheduler's ability to react to and compensate for changes in workload access characteristics. Unfortunately, there is no cycle length that is optimal for …

Efficient Geophysical Technique Of Vertical Line Elements As A Natural Consequence Of General Constraints Techniques, Rolando Cardenas, Martine Ceberio

Departmental Technical Reports (CS)

One of the main objectives of geophysics is to find how density d and other physical characteristics depend on a 3-D location (x,y,z). In general, in numerical methods, a way to find the dependence d(x,y,z) is to discretize the space, and to consider, as unknown, e.g., values d(x,y,z) on a 3-D rectangular grid. In this case, the desired density distribution is represented as a combination of point-wise density distributions. In geophysics, it turns out that a more efficient way to find the desired distribution is to represent it as a combination of thin vertical line elements that start at some …

Prediction In Econometrics: Towards Mathematical Justification Of Simple (And Successful) Heuristics, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

Many heuristic and semi-heuristic methods have been proposed to predict economic and financial processes. Some of these heuristic processes are intuitively reasonable, some seemingly contradict to our intuition. The success of these heuristics leads to a reasonable conjecture that these heuristic methods must have a more fundamental justification. In this paper, we provide such a justification for two simple (and successful) prediction heuristics: of an intuitive exponential smoothing that provides a reasonable prediction for slowly changing processes, and of a seemingly counter-intuitive idea of an increase in volatility as a predictor of trend reversal. As a possible application of these …

Reconstructing An Open Order From Its Closure, With Applications To Space-Time Physics And To Logic, Francisco Zapata, Vladik Kreinovich

Departmental Technical Reports (CS)

In his logical papers, Leo Esakia studied corresponding ordered topological spaces and order-preserving mappings. Similar spaces and mappings appear in many other application areas such the analysis of causality in space-time. It is known that under reasonable conditions, both the topology and the original order relation can be uniquely reconstructed if we know the "interior" < of the order relation. It is also known that in some cases, we can uniquely reconstruct < (and hence, topology) from the original order relation. In this paper, we show that, in general, under reasonable conditions, the open order < (and hence, the corresponding topology) can be uniquely determined from its closure.

The Cleanjava Language For Functional Program Verification, Yoonsik Cheon, Cesar Yeep, Melisa Vela

Departmental Technical Reports (CS)

Unlike Hoare-style program verification, functional program verification supports forward reasoning by viewing a program as a mathematical function from one program state to another and proving its correctness by essentially comparing two mathematical functions, the function computed by the program and its specification. Since it requires a minimal mathematical background and reflects the way that programmers reason about the correctness of a program informally, it can be taught and practiced effectively. However, there is no formal notation supporting the functional program verification. In this article, we describe a formal notation for writing functional program specifications for Java programs. The notation, …

High-Concentration Chemical Computing Techniques For Solving Hard-To-Solve Problems, And Their Relation To Numerical Optimization, Neural Computing, Reasoning Under Uncertainty, And Freedom Of Choice, Vladik Kreinovich, Olac Fuentes

Departmental Technical Reports (CS)

Chemical computing -- using chemical reactions to perform computations -- is a promising way to solve computationally intensive problems. Chemical computing is promising because it has the potential of using up to 10^{23} molecules as processors working in parallel -- and thus, has a potential of an enormous speedup. Unfortunately, for hard-to-solve (NP-complete) problems a natural chemical computing approach for solving them is exponentially slow. In this chapter, we show that the corresponding computations can become significantly faster if we use very-high-concentration chemical reactions, concentrations at which the usual equations of chemical kinetics no longer apply. We also show that …

All Kinds Of Behavior Are Possible In Chemical Kinetics: A Theorem And Its Potential Applications To Chemical Computing, Vladik Kreinovich

Departmental Technical Reports (CS)

Linear Neural Networks Revisited: From Pagerank To Family Happiness, Vladik Kreinovich

Departmental Technical Reports (CS)

The study of Artificial Neural Networks started with the analysis of linear neurons. It was then discovered that networks consisting only of linear neurons cannot describe non-linear phenomena. As a result, most currently used neural networks consist of non-linear neurons. In this paper, we show that in many cases, linear neurons can still be successfully applied. This idea is illustrated by two examples: the PageRank algorithm underlying the successful Google search engine and the analysis of family happiness.

Density-Based Fuzzy Clustering As A First Step To Learning The Rules: Challenges And Possible Solutions, Gözde Ulutagay, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, it is necessary to cluster given situations, i.e., to divide them into groups so that situations within each group are similar to each other. This is how we humans usually make decisions: instead of taking into account all the tiny details of a situation, we classify the situation into one of the few groups, and then make a decision depending on the group containing a given situation. When we have many situations, we can describe the probability density of different situations. In terms of this density, clusters are connected sets with higher density separated by sets …

How To Encourage Imperfect Individuals To Care More About Society In General: A Utility-Theory Approach, Vladik Kreinovich

Departmental Technical Reports (CS)

A Simple Physics-Motivated Equivalent Reformulation Of P=Np That Makes This Equality (Slighty) More Plausible, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

In our opinion, one of the reasons why the problem P=NP? is so difficult is that while there are good intuitive arguments in favor of P=/=NP, there is a lack of intuitive arguments in favor of P=NP. In this paper, we provide such an argument -- based on the fact that in physics, many dependencies are scale-invariant, their expression does not change if we simply change the unit in which we measure the corresponding input quantity (e.g., replace meters by centimeters). It is reasonable to imagine similar behavior for time complexity t_A(n) of algorithms A: that the form …

How Accurately Should We Write On The Board? When Marking Comments On Student Papers?, Martine Ceberio, Olga Kosheleva

Departmental Technical Reports (CS)

Writing on the board is an important part of a lecture. Lecturers' handwriting is not always perfect. Usually, a lecturer can write slower and more legibly, this will increase understandability but slow down the lecture. In this paper, we analyze an optimal trade-off between speed and legibility.

I-Complexity And Discrete Derivative Of Logarithms: A Symmetry-Based Explanation, Vladik Kreinovich, Jaime Nava

Departmental Technical Reports (CS)

In many practical applications, it is useful to consider Kolmogorov complexity K(s) of a given string s, i.e., the shortest length of a program that generates this string. Since Kolmogorov complexity is, in general, not computable, it is necessary to use computable approximations K_~(s) to K(s). Usually, to describe such an approximations, we take a compression algorithm and use the length of the compressed string as K_~(s). This approximation, however, is not perfect: e.g., for most compression algorithms, adding a single bit to the string $s$ can drastically change the value K_~(s) -- while …

A New Justification For Weighted Average Aggregation In Fuzzy Techniques, Jaime Nava

Departmental Technical Reports (CS)

In many practical situations, we need to decide whether a given solution is good enough, based on the degrees a_i to which different criteria are satisfied. In this paper, we show that natural requirements lead to the weighted average decision, according to which a solution is acceptable if w₁ * a₁ + ... + w_n * a_n > t for some weights w_i and threshold t.

Computation In Quantum Space-Time Could Lead To A Super-Polynomial Speedup, Vladik Kreinovich, Michael Zakharevich

Departmental Technical Reports (CS)

How To Tell When A Product Of Two Partially Ordered Spaces Has A Certain Property?, Francisco Zapata, Olga Kosheleva, Karen Villaverde

Departmental Technical Reports (CS)

In this paper, we describe how checking whether a givenproperty F is true for a product A₁ X A₂ of partiallyordered spaces can be reduced to checking several relatedproperties of the original spaces A_i.

This result can be useful in the analysis of propertiesof intervals [a,b] = {x: a <= x <= b}over general partially ordered spaces -- such as the spaceof all vectors with component-wise order or the set of allfunctions with component-wise ordering f <= g <-->for all x (f(x) <= g(x)). When we consider sets of pairs ofsuch objects A₁ X A₂, it is natural to define the orderon this set in terms of orders in A₁ and A₂ -- this is, e.g.,how ordering and intervals are defined on the set R² of all2-D vectors.

This result …

Ground Penetrating Radar System For Underground Imaging, Michelle Salvador, Ricardo Von Borries*

COURI Symposium Abstracts, Summer 2011

No abstract provided.

Smart Grid Platform, David Guzman ^, Virgilio Gonzalez *

COURI Symposium Abstracts, Summer 2011

No abstract provided.

Skin Cell Regeneration, Polette Cortez^, Maria Yanez, Thomas Boland*

COURI Symposium Abstracts, Summer 2011

No abstract provided.

Development Of A Direct-Write System For Ceramic Colloidal Inks, Jorge Mireles^, Miguel Verdecchia, David Espalin, Geoffrey Saupe, Noe Vargas, Frank Medina, Ryan Wicker*

COURI Symposium Abstracts, Summer 2011

No abstract provided.

Analysis Of Sealing Methods For Fdm-Fabricated Parts, Arturo Adame^, Jorge Mireles, David Espalin, Frank Medina, Rob Winker, Terry Hoppe, Bob Zinniel, Ryan Wicker*

COURI Symposium Abstracts, Summer 2011

No abstract provided.

Mapping Mos2-Co Catalytic Nanostructures Using Hrtem And Tem Simulations, Eduan Martínez-Soto ^, Brenda Torres, Domingo Ferrer, Gilles Berhault, Russell Chianelli, Manuel Ramos *

COURI Symposium Abstracts, Summer 2011

No abstract provided.

Theoretical Explanation Of Bernstein Polynomials' Efficiency: They Are Optimal Combination Of Optimal Endpoint-Related Functions, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

In many applications of interval computations, it turned out to be beneficial to represent polynomials on a given interval [x_-, x₊] as linear combinations of Bernstein polynomials (x- x _- )^k * (x₊ - x)^n-k. In this paper, we provide a theoretical explanation for this empirical success: namely, we show that under reasonable optimality criteria, Bernstein polynomials can be uniquely determined from the requirement that they are optimal combinations of optimal polynomials corresponding to the interval's endpoints.

Why Neural Networks Are Computationally Efficient Approximators: An Explanation, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

Many real-life dependencies can be reasonably accurately described by linear functions. If we want a more accurate description, we need to take non-linear terms into account. To take nonlinear terms into account, we can either explicitly add quadratic terms to the regression equation, or, alternatively, we can use a neural network with a non-linear activation function. At first glance, regression algorithms would work faster, but in practice, often, a neural network approximation turns out to be a more computationally efficient one. In this paper, we provide a reasonable explanation for this empirical fact.