Computer Engineering Commons^™

Towards Applying Computational Complexity To Foundations Of Physics, Vladik Kreinovich, Andrei Finkelstein

Departmental Technical Reports (CS)

In one of his early papers, D. Grigoriev analyzed the decidability and computational complexity of different physical theories. This analysis was motivated by the hope that this analysis would help physicists. In this paper, we survey several similar ideas that may be of help to physicists. We hope that further research may lead to useful physical applications.

The Multi-Layered Interval Categorizer Tesselation-Based Model, Marilton S. De Aguiar, Gracaliz P. Dimuro, Antonio C. Da Rocha Costa, Rafael K.S. Silva, Fabia A. Da Costa, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Advanced Relation Model For Genome Sequence Visualization (Arm 4 Gsv): Exploratory Visualization Examples, Brian J. D'Auriol, Kavitha Tupelly

Departmental Technical Reports (CS)

The Advanced Relation Model for Genome Sequence Visualization (ARM 4 GSV) is proposed in this paper. This model is adapted from an earlier visualization model which has been applied to the visualization of computer programs. A review of the fundamental model components of the earlier visualization model is given. Enhancements so as to make it applicable in genome visualization are discussed. As part of these enhancements, a relational characterization of genome sequences in terms of bases, codons, and patterns such as close inversions is developed and described. An adapted form of the Conceptual Crown Visualization (CCV) model, a part of …

Monte-Carlo-Type Techniques For Processing Interval Uncertainty, And Their Geophysical And Engineering Applications, Matthew G. Averill, Kate C. Miller, George R. Keller, Vladik Kreinovich, Jan Beck, Roberto Araiza, Roberto Torres, Scott A. Starks

Departmental Technical Reports (CS)

To determine the geophysical structure of a region, we measure seismic travel times and reconstruct velocities at different depths from this data. There are several algorithms for solving this inverse problem, but these algorithms do not tell us how accurate these reconstructions are.

Traditional approach to accuracy estimation assumes that the measurement errors are independently normally distributed. Problem: the resulting accuracies are not in line with geophysical intuition. Reason: a typical error is when we miss the first arrival of the seismic wave; it is not normal (bounded by the wave period T) and not independent.

Typically, all we know …

Computing The Cube Of An Interval Matrix Is Np-Hard, Olga Kosheleva, Vladik Kreinovich, Guenter Mayer, Hung T. Nguyen

Departmental Technical Reports (CS)

In many practical applications, we are interested in computing the product of given matrices and/or a power of a given matrix. In some cases, the initial matrices are only known with interval uncertainty. It turns out that under this uncertainty, there is a principal difference between the product of two matrices and the product of three (or more) matrices:

on the one hand, it is more or less known that the problems of computing the exact range for the product of two matrices -- and for the square of a matrix -- are computationally feasible;

on the other hand, we …

Probabilistic Approach To Trust: Ideas, Algorithms, And Simulations, Pattama Jaksurat, Eric A. Freudenthal, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In traditional security systems, for each task, we either trust an agent or we don't. If we trust an agent, we allow this agent full access to this particular task. This agent can usually allow his trusted sub-agents the same access, etc. If a trust management system only uses "trust" and "no trust" options, then a person should trust everyone in this potentially long chain. The problem is that trust is rarely a complete trust, there is a certain probability of distrust. So, when the chain becomes long, the probability of a security leak increases. It is desirable to keep …

Checking If There Exists A Monotonic Function That Is Consistent With The Measurements: An Efficient Algorithm, Kavitha Tupelly, Vladik Kreinovich, Karen Villaverde

Departmental Technical Reports (CS)

In many problems in science and engineering ranging from astrophysics to geosciences to financial analysis, we know that a physical quantity y depends on the physical quantity x, i.e., y=f(x) for some function f(x), and we want to check whether this dependence is monotonic. Specifically, finitely many measurements of xi and yi=f(xi) have been made, and we want to check whether the results of these measurements are consistent with the monotonicity of f. An efficient parallelizable algorithm is known for solving this problem when the values xi are known precisely, while the values yi are known with interval uncertainty. In …

Foundations Of Statistical Processing Of Set-Valued Data: Towards Efficient Algorithms, Hung T. Nguyen, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

Due to measurement uncertainty, often, instead of the actual values xi of the measured quantities, we only know the intervals [Xi]=[Xi-Di,Xi+Di], where Xi is the measured value and Di is the upper bound on the measurement error (provided, e.g., by the manufacturer of the measuring instrument). These intervals can be viewed as random intervals, i.e., as samples from the interval-valued random variable. In such situations, instead of the exact value of a sample statistic such as covariance C(x,y), we can only have an interval [C](x,y) of possible values of this statistic.

In this paper, we extend the foundations of traditional …

Convergence Properties Of An Interval Probabilistic Approach To System Reliability Estimation, Cliff Joslyn, Vladik Kreinovich

Departmental Technical Reports (CS)

Based on a black box model of a complex system, and on intervals and probabilities describing the known information about the inputs, we want to estimate the system's reliability. Using the results of tests performed on the system's computer model, we can estimate the lower and upper bounds of the probability that the system is in a desirable state. In this paper, we prove that these estimates are correct in the sense that under reasonable assumptions, these estimates converge to the actual probability bounds.

A Model Of Computer Science Graduate Admissions Decisions, Nigel Ward

Departmental Technical Reports (CS)

Potential applicants to graduate school find it difficult to predict, even approximately, which schools will accept them. We have created a predictive model of admissions decision-making, packaged in the form of a web page that allows students to enter their information and see a list of schools where they are likely to be accepted. This paper discusses the design of the model and the way its parameters were estimated. Interesting points include the way that weights are assigned dynamically to various factors based on the informativeness of each factor and on the applicant's relative strengths on each factor.

Exact Bounds On Finite Populations Of Interval Data, Scott Ferson, Lev Ginzburg, Vladik Kreinovich, Luc Longpre, Monica Aviles

Departmental Technical Reports (CS)

In this paper, we start research into using intervals to bound the impact of bounded measurement errors on the computation of bounds on finite population parameters ("descriptive statistics"). Specifically, we provide a feasible (quadratic time) algorithm for computing the lower bound on the finite population variance function of interval data. We prove that the problem of computing the upper bound on the finite population variance function of interval data is, in general, NP-hard. We provide a feasible algorithm that computes this upper bound under reasonable easily verifiable conditions, and provide preliminary results on computing other functions of finite populations.

Generating Properties For Runtime Monitoring From Software Specification Patterns, Oscar Mondragon, Ann Q. Gates, Oleg Sokolsky

Departmental Technical Reports (CS)

The paper presents an approach to support run-time verification of software systems that combines two existing tools, Prospec and Java-MaC, into a single framework. Prospec can be used to clarify natural language specifications for sequential, concurrent, and nondeterministic behavior. In addition, the tool assists the user in reading, writing, and understanding formal specifications through the use of property patterns and visual abstractions. Currently, Prospec automatically generates a specification written in Future Interval Logic (FIL). The goal is to automate the generation of MEDL formulas that can be used by the Java-MaC tool to check run-time compliance of system execution to …

Non-Lexical Conversational Sounds In American English, Nigel Ward

Departmental Technical Reports (CS)

This article analyzes the non-lexical conversational sounds (conversational grunts) of English, including such items as uh-huh, un-hn, um, mm, and oh, based primarily on examination of a few hundred occurrences in a corpus of conversations. The data includes extensive phonetic variation, suggesting that these items are best explained, not as fixed words, but as dynamic creations. In particular, the vast majority of these items can be generated by a simple model consisting of 10 component sounds and 2 combining rules. Moreover, each of these component sounds seems to bear some meaning or function which is fairly constant across grunts and …

Optimal Finite Characterization Of Linear Problems With Inexact Data, Vladik Kreinovich

Departmental Technical Reports (CS)

For many linear problems, in order to check whether a certain property is true for all matrices A from an interval matrix [A], it is sufficient to check this property for finitely many "vertex" matrices. J. Rohn has discovered that we do not need to use all 2^(n^2) vertex matrices, it is sufficient to only check these properties for 2^(2n-1)<<2^(n^2) vertex matrices of a special type A_{yz}. In this paper, we show that a further reduction is impossible: without checking all 2^(2n-1) matrices A_{yz}, we cannot guarantee that the desired property holds for all A from [A]. Thus, these special vertex matrices provide an optimal finite characterization of linear problems with inexact data.

Outlier Detection Under Interval Uncertainty: Algorithmic Solvability And Computational Complexity, Vladik Kreinovich, Luc Longpre, Praveen Patangay, Scott Ferson, Lev Ginzburg

Departmental Technical Reports (CS)

In many application areas, it is important to detect outliers. Traditional engineering approach to outlier detection is that we start with some "normal" values x1,...,xn, compute the sample average E, the sample standard variation sigma, and then mark a value x as an outlier if x is outside the k0-sigma interval [E-k0*sigma,E+k0*sigma] (for some pre-selected parameter k0). In real life, we often have only interval ranges [xi] for the normal values x1,...,xn. In this case, we only have intervals of possible values for the bounds E-k0*sigma and E+k0*sigma. We can therefore identify outliers as values that are outside all k0-sigma …

Towards Combining Probabilistic And Interval Uncertainty In Engineering Calculations, Scott A. Starks, Vladik Kreinovich, Luc Longpre, Martine Ceberio, Gang Xiang, Roberto Araiza, J. Beck, R. Kandathi, A. Nayak, R. Torres

Departmental Technical Reports (CS)

In many engineering applications, we have to combine probabilistic and interval errors. For example, in environmental analysis, we observe a pollution level x(t) in a lake at different moments of time t, and we would like to estimate standard statistical characteristics such as mean, variance, autocorrelation, correlation with other measurements. In environmental measurements, we often only know the values with interval uncertainty. We must therefore modify the existing statistical algorithms to process such interval data. Such modification are described in this paper.

Beyond Convex? Global Optimization Is Feasible Only For Convex Objective Functions: A Theorem, R. Baker Kearfott, Vladik Kreinovich

Departmental Technical Reports (CS)

It is known that there are feasible algorithms for minimizing convex functions, and that for general functions, global minimization is a difficult (NP-hard) problem. It is reasonable to ask whether there exists a class of functions that is larger than the class of all convex functions for which we can still solve the corresponding minimization problems feasibly. In this paper, we prove, in essence, that no such more general class exists. In other words, we prove that global optimization is always feasible only for convex objective functions.

Computing 2-Step Predictions For Interval-Valued Finite Stationary Markov Chains, Marcilia Andrade Campos, Gracaliz Pereira Dimuro, Antonio Carlos Da Rocha Costa, Vladik Kreinovich

Departmental Technical Reports (CS)

Markov chains are a useful tool for solving practical problems. In many real-life situations, we do not know the exact values of initial and transition probabilities; instead, we only know the intervals of possible values of these probabilities. Such interval-valued Markov chains were considered and analyzed by I. O. Kozine and L. V. Utkin in their Reliable Computing paper. In their paper, they propose an efficient algorithm for computing interval-valued probabilities of the future states. For the general case of non-stationary Markov chains, their algorithm leads to the exact intervals for the probabilities of future states.

In the important case …

Geon: Geophysical Data Add The 3rd Dimension In Geospatial Studies, R. Aldouri, George R. Keller, Ann Q. Gates, J. Rasillo, Leonardo Salayandia, Vladik Kreinovich, John M. Seeley, P. Taylor, S. Holloway

Departmental Technical Reports (CS)

A major trend in GIS is the addition of subsurface information to provide a 3-D perspective on data. Geophysical data provide information about subsurface structures and conditions, but require considerable analysis. The 4-D emphasis with the GEON projects has required the development of many sophisticated tools to allow users to utilize geophysical datasets that will be available on the GEON grid. Our group has created tools that will allow users to search new gravity and magnetic databases of the entire U.S. These tools will extract specific records from an Oracle database, and display the points over a map, grid and …

Computing Higher Central Moments For Interval Data, Vladik Kreinovich, Luc Longpre, Scott Ferson, Lev Ginzburg

Departmental Technical Reports (CS)

Higher central moments are very useful in statistical analysis: the third moment M3 characterizes asymmetry of the corresponding probability distribution, the fourth moment M4 describes the size of the distribution's tails, etc. When we know the exact values x1,...,xn, we can use the known formulas for computing the corresponding sample central moments. In many practical situations, however, we only know intervals [x1],...,[xn] of possible values of xi; in such situations, we want to know the range of possible values of Mm. In this paper, we propose algorithms that compute such ranges.

Fuzzy And Probabilistic Models Of Association Information In Sensor Networks, Leon Reznik, Vladik Kreinovich

Departmental Technical Reports (CS)

The paper considers the problem of improving accuracy and reliability of measurement information acquired by sensor networks. It offers the way of integrating sensor measurement results with association information available or a priori derived at aggregation nodes. The models applied for describing both sensor sensor results and association information are reviewed with consideration given to both neuro-fuzzy and probabilistic models and methods. The information sources, typically available in sensor systems, are classified according to the model (fuzzy or probabilistic), which seems more feasible to be applied. The integration problem is formulated as an optimization problem.

Application Of Kolmogorov Complexity To Advanced Problems In Mechanics, Vladik Kreinovich, Isaak A. Kunin

Departmental Technical Reports (CS)

In the 1960s, A.N. Kolmogorov described the main reason why a mathematical correct solution to a system of differential equations may be not physically possible: Traditional mathematical analysis tacitly assumes that all numbers, no matter how large or how small, are physically possible. From the engineering viewpoint, however, a number like 10^{10^10} is not possible, because it exceeds the number of particles in the Universe. In this paper, we extend Kolmogorov's ideas from discrete objects to continuous objects known with given accuracy epsilon, and show how this extension can clarify the analysis of dynamical systems.

Geometry Of Protein Structures. I. Why Hyperbolic Surfaces Are A Good Approximation For Beta-Sheets, Boguslaw Stec, Vladik Kreinovich

Departmental Technical Reports (CS)

Protein structure is invariably connected to protein function. To analyze the structural changes of proteins, we should have a good description of basic geometry of proteins' secondary structure. A beta-sheet is one of important elements of protein secondary structure that is formed by several fragments of the protein that form a surface-like feature. The actual shapes of the beta-sheets can be very complicated, so we would like to approximate them by simpler geometrical shapes from an approximating family. Which family should we choose? Traditionally, hyperbolic (second order) surfaces have been used as a reasonable approximation to the shape of beta-sheets. …

Using Fft-Based Data Processing Techniques To Characterize Asphaltic Concrete Mixtures, Scott A. Starks, Vladik Kreinovich, Roberto Araiza, Soheil Nazarian, J. Adidhela

Departmental Technical Reports (CS)

A natural way to test the quality of a pavement is to send signals with different frequencies through the pavement and compare the results with the signals passing through an ideal pavement. For this comparison, we must determine how, for the corresponding mixture, the elasticity E depends on the frequency f in the range from 0.1 to 10^5 Hz. It is very expensive to perform measurements in high frequency area (above 20 Hz). To avoid these measurements, we can use the fact that for most of these mixtures, when we change a temperature, the new dependence changes simply by scaling. …

Using 1-D Radar Observations To Detect A Space Explosion Core Among The Explosion Fragments: Sequential And Distributed Algorithms, P. Debroux, J. Boehm, Vladik Kreinovich, Gang Xiang, J. Beck, K. Tupelly, R. Kandathi, Luc Longpre, K. Villaverde

Departmental Technical Reports (CS)

A radar observes the result of a space explosion. Due to radar's low horizontal resolution, we get a 1-D signal s(t) representing different 2-D slices. Based on these slices, we must distinguish between the body at the core of the explosion and the slowly out-moving fragments. We propose new algorithms for processing this 1-D data. Since these algorithms are time-consuming, we also exploit the possibility of parallelizing these algorithms.

On-Line Algorithms For Computing Mean And Variance Of Interval Data, And Their Use In Intelligent Systems, Berlin Wu, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Interval-Valued And Fuzzy-Valued Random Variables: From Computing Sample Variances To Computing Sample Covariances, Jan B. Beck, Vladik Kreinovich, Berlin Wu

Departmental Technical Reports (CS)

Due to measurement uncertainty, often, instead of the actual values xi of the measured quantities, we only know the intervals [xi]=[Xi-Di,Xi+Di], where Xi is the measured value and Di is the upper bound on the measurement error (provided, e.g., by the manufacturer of the measuring instrument). In such situations, instead of the exact value of the sample statistics such as covariance C(x,y), we can only have an interval [C](x,y) of possible values of this statistic. It is known that in general, computing such an interval [C](x,y) for C(x,y) is an NP-hard problem. In this paper, we describe an algorithm that …

Probabilities, Intervals, What Next? Extension Of Interval Computations To Situations With Partial Information About Probabilities, Vladik Kreinovich, Gennady N. Solopchenko, Scott Ferson, Lev Ginzburg, Richard Alo

Departmental Technical Reports (CS)

In many real-life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y, we find some easier-to-measure quantities x1,...,xn which are related to y by a known relation y=f(x1,...,xn). Measurements are never 100% accurate; hence, the measured values Xi are different from xi, and the resulting estimate Y=f(X1,...,Xn) is different from the desired value y=f(x1,...,x_n). How different?

Traditional engineering to error estimation in data processing assumes that we know the probabilities of different measurement error Dxi=Xi-xi.

In many practical situations, we only know the upper bound Di …

Group-Theoretic Approach As A General Framework For Sensors, Neural Networks, Fuzzy Control, And Genetic Boolean Networks, Hung T. Nguyen, Vladik Kreinovich, Chitta Baral, Valery D. Mazin

Departmental Technical Reports (CS)

When describing a system of interacting genes, a useful approximation is provided by a Boolean network model, in which each gene is either switched on or off - i.e., its state is described by a Boolean variable.

Recent papers by I. Shmulevich et al. show that although in principle, arbitrarily complex Boolean functions are possible, in reality, the corresponding Boolean networks can be well described by Boolean functions from one of the so-called Post classes - classes that are closed under composition. These classes were originally described by E. Post.

It is known that the Boolean model is only an …

Modelling Measurement Processes As Timed Information Processes In Simplex Domains, Gracaliz P. Dimuro, Antonio C. Da Rocha Costa, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper presents a domain-theoretic model for measurements and measuring instruments, by making explicit in simplex-domain structures two important aspects of measurement processes: the notion of standard representation relation, established between the (physical) values that are being measured and the meanings of the readings (semantic values) of the measuring instruments used to measure them, and the time time underlying every measurement process, in a way that it is possible to trace the hostory of every measuring process. We also present the modelling of measurements performed by combined measuring instruments synchrfonized in time. Finally, the domain-theoretic modelling of a sample measuring …