Computer Engineering Commons^™

A Feasible Algorithm For Locating Concave And Convex Zones Of Interval Data And Its Use In Statistics-Based Clustering, Vladik Kreinovich, Eric J. Pauwels, Scott Ferson, Lev Ginzburg

Departmental Technical Reports (CS)

Often, we need to divide n objects into clusters based on the value of a certain quantity x. For example, we can classify insects in the cotton field into groups based on their size and other geometric characteristics. Within each cluster, we usually have a unimodal distribution of x, with a probability density d(x) that increases until a certain value x0 and then decreases. It is therefore natural, based on d(x), to determine a cluster as the interval between two local minima, i.e., as a union of adjacent increasing and decreasing segments. In this paper, we describe a feasible algorithm …

Computational Complexity And Feasibility Of Data Processing And Interval Computations, With Extension To Cases When We Have Partial Information About Probabilities, Vladik Kreinovich, Luc Longpre

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,...,xn). How different?

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

Eliminating Duplicates Under Interval And Fuzzy Uncertainty: An Asymptotically Optimal Algorithm And Its Geospatial Applications, Roberto Torres, George R. Keller, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

Geospatial databases generally consist of measurements related to points (or pixels in the case of raster data), lines, and polygons. In recent years, the size and complexity of these databases have increased significantly and they often contain duplicate records, i.e., two or more close records representing the same measurement result. In this paper, we address the problem of detecting duplicates in a database consisting of point measurements. As a test case, we use a database of measurements of anomalies in the Earth's gravity field that we have compiled. In this paper, we show that a natural duplicate deletion algorithm requires …

Determination Of Properties Of Composite Materials From The Lamb Wave Propagation: Probabilistic, Interval, And Fuzzy Approaches, Fariba Ansari, William Durrer, Soheil Nazarian, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the most efficient non-destructive techniques for finding hidden faults in a plate is the use of ultrasonic Lamb waves. These waves are reflected by faults, and from this reflection, we can locate the faults. For that, we need to know how the Lamb waves propagate. Their propagation is determined by the dynamic elastic constants C_pq, so we must find these constants. These constants cannot be measured directly; instead, we measure the dependence of the speed of frequency c(f), and we must reconstruct C_pq from the measured values of c(f). In this paper, we show how this can be …

Robust Methodology For Characterizing System Response To Damage: A Subjective (Fuzzy) Partial Ordered Modification Of The Traditional Utility-Probability Scheme, Carlos De La Mora, Piotr Wojciechowski, Vladik Kreinovich, Scott A. Starks, Paul J. Tanenbaum, Alexandr V. Kuzminykh

Departmental Technical Reports (CS)

No abstract provided.

The Use Of Fuzzy Measures As A Data Fusion Tool In Geographic Information Systems: Case Study, Cynthia Campos, George R. Keller, Vladik Kreinovich, Luc Longpre, Francois Modave, Scott A. Starks, Roberto Torres

Departmental Technical Reports (CS)

Geospatial databases generally consist of measurements related to points (or pixels in the case of raster data), lines, and polygons. In recent years, the size and complexity of these databases have increased significantly and they often contain duplicate records, i.e., two or more close records representing the same measurement result. In this paper, we use fuzzy measures to address the problem of detecting duplicates in a database consisting of point measurements. As a test case, we use a database of measurements of anomalies in the Earth's gravity field that we have compiled. We show that a natural duplicate deletion algorithm …

Complexity And Approximation Studies Of Finding Polynomially Bounded Length Plans For Temporal Goals, Chitta Baral, Vladik Kreinovich, Sudeshna Sarkar, Nam Tran, Raul Trejo, Xin Zhang

Departmental Technical Reports (CS)

In this paper, we consider the problem of planning with temporal goals, focussing on polynomially bounded length plans. Past results about complexity of planning are mostly about finding plans that take the world to one of several desired states, often described using a goal formula. We first consider goals expressed using linear temporal logic and analyze the complexity of planning with respect to such goals for both when the states in the trajectory are complete states, and when they are incomplete states. For the later case we also develop a notion of approximate planning and show its complexity to be …

Fast Quantum Algorithms For Handling Probabilistic, Interval, And Fuzzy Uncertainty, Mark Martinez, Luc Longpre, Vladik Kreinovich, Scott A. Starks, Hung T. Nguyen

Departmental Technical Reports (CS)

We show how quantum computing can speed up computations related to processing probabilistic, interval, and fuzzy uncertainty.

Robust Methodology For Characterizing System Response To Damage: Approach Based On Partial Order, Paul J. Tanenbaum, Carlos De La Mora, Piotr Wojciechowski, Olga Kosheleva, Vladik Kreinovich, Scott A. Starks, Alexandr V. Kuzminykh

Departmental Technical Reports (CS)

To describe the response of engineering complex systems to various damage mechanics, engineers have traditionally use number-valued utilities to describe the results of different possible outcomes, and (number-valued) probabilities (often, subjective probabilities) to describe the relative frequency of different outcomes. This description is based on the assumption that experts can always make a definite preference between two possible outcomes, i.e., that the set of all outcomes is linearly (totally) ordered. In practice, experts often cannot make a choice, their preference is only a partial order.

Outlier Detection Under Interval And Fuzzy Uncertainty: Algorithmic Solvability And Computational Complexity, Vladik Kreinovich, Praveen Patangay, Luc Longpre, Scott A. Starks, Cynthia Campos, Scott Ferson, Lev Ginzburg

Departmental Technical Reports (CS)

No abstract provided.

Detecting Cracks In Thin Plates By Using Lamb Wave Scanning: Geometric Approach, Roberto A. Osegueda, Vladik Kreinovich, Enrique Roldan, Rodrigo Mares

Departmental Technical Reports (CS)

A crack in a thin plate reflects ultrasonic waves; therefore, it is reasonable to determine the location of the crack by measuring the reflected waves. The problem of locating the crack can be reformulated in purely geometric terms. Previously, time-consuming iterative numerical methods were used to solve the resulting geometric problem. In this paper, we show that explicit (and fast to compute) formulas can be used instead.

Probabilities, Intervals, What Next? Optimization Problems Related To Extension Interval Computations To Situations With Partial Information About Probabilities, Vladik Kreinovich

Departmental Technical Reports (CS)

When we have only interval ranges [xi-,xi+] of sample values x1,...,xn, what is the interval [V-,V+] of possible values for the variance V of these values? We prove that the problem of computing the upper bound V+ is NP-hard. We provide a feasible (quadratic time) algorithm for computing the exact lower bound V- on the variance of interval data. We also provide feasible algorithms that computes V+ under reasonable easily verifiable conditions, in particular, in case interval uncertainty is introduced to maintain privacy in a statistical database.

We also extend the main formulas of interval arithmetic for different arithmetic operations …

On The Relation Between Two Approaches To Combining Evidence: Ordered Abelian Groups And Uninorms, Ronald R. Yager, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we develop a relationship between two approaches to combining evidence: the Ordered Abelian Group (OAG) approach and the uninorm approach. We show that while there exist uninorms that are not extended OAG's it turns out that for operations which are continuous (in some reasonable sense), these two approaches coincide.

Dirty Pages Of Logarithm Tables, Lifetime Of The Universe, And (Subjective) Probabilities On Finite And Infinite Intervals, Hung T. Nguyen, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

To design data processing algorithms with the smallest average processing time, we need to know what this "average" stands for. At first glance, it may seem that real-life data are really "chaotic", and no probabilities are possible at all: today, we may apply our software package to elementary particles, tomorrow -- to distances between the stars, etc. However, contrary to this intuitive feeling, there are stable probabilities in real-life data. This fact was first discovered in 1881 by Simon Newcomb who noticed that the first pages of logarithm tables (that contain numbers starting with 1) are more used than the …

Exact Upper Bound On The Mean Of The Product Of Many Random Variables With Known Expectations, Vladik Kreinovich, Scott Ferson, Lev Ginzburg

Departmental Technical Reports (CS)

In practice, in addition to the intervals [xi] of possible values of inputs x1,...,xn, we sometimes also know their means Ei. For such cases, we provide an explicit exact (= best possible) upper bound for the mean of the product x1*...*xn of positive values xi.

Dimension Compactification -- A Possible Explanation For Superclusters And For Empirical Evidence Usually Interpreted As Dark Matter, Vladik Kreinovich

Departmental Technical Reports (CS)

According to modern quantum physics, at the microlevel, the dimension of space-time is at least 11; we only observe 4 dimensions because the others are compactified: the size along each of the other dimensions is much smaller than the macroscale. There is no universally accepted explanation of why exactly 4 dimensions remain at the microscopic level. A natural suggestion is: maybe there is no fundamental reason why exactly 4 dimensions should remain, maybe when we go to even larger scales, some of the 4 dimensions will be compactified as well? In this paper, we explore the consequences of the compactification …

Use Of Fuzzy Expert's Information In Measurement And What We Can Gain From Its Application In Geophysics, Leon Reznik, Vladik Kreinovich, Scott A. Starks

Departmental Technical Reports (CS)

The paper considers the problem of measurement information fusion from different sources, when one of the sources is an information about approximate values of the measured variables or their combinations. The information is given with fuzzy models and is used in combination with the measurement results. The properties of the modified estimates are studied in comparison with the conventional ones. The conditions when an expert's information application can give a high gain are derived, the gain value is estimated, the recommendations to an expert on making predictions are given. The possible gain in measurement result efficiency in geophysical applications is …

Kolmogorov Complexity: How A Paradigm Motivated By Foundations Of Physics Can Be Applied In Robust Control, Vladik Kreinovich, Issak A. Kunin

Departmental Technical Reports (CS)

Born about three decades ago, Kolmogorov Complexity Theory (KC) led to important discoveries that, in particular, give a new understanding of the fundamental problem: interrelations between classical continuum mathematics and reality (physics, biology, engineering sciences, ...). Crudely speaking, it enables us to better distinguish between mathematical possible (possible abnormal) and physically possible situations.

We show that this formalization is not only in good accordance with theoretical physics, but it can also be applied to robust control: instead of requiring that the control work for all mathematically possible situations, we only require that the control works for all "non-abnormal" situations.

Statistical And Dempster-Shafer Techniques In Testing Structural Integrity Of Aerospace Structures, Roberto A. Osegueda, Seetharami R. Seelam, Bharat Mulupuru, Vladik Kreinovich

Departmental Technical Reports (CS)

Several techniques are known for non-destructive testing of aerospace structures, such as pulse echo, Eddy current, magnetic resonance, etc. Each of these techniques detects some faults but misses others, so it is desirable to combine (fuse) the results of these techniques. Several methods of data fusion are known. To improve the quality of fault detection, we modified the straightforward statistical method as follows: (1) we computed mean and variance iteratively: detected faults are excluded form the computation on the next iteration; (2) we treated the plate's edge and the inside separately; (3) we dismissed measurements in which only one technique …

A New Cauchy-Based Black-Box Technique For Uncertainty In Risk Analysis, Vladik Kreinovich, Scott Ferson

Departmental Technical Reports (CS)

Uncertainty is very important in risk analysis. A natural way to describe this uncertainty is to describe a set of possible values of each unknown quantity (this set is usually an interval), plus any additional information that we may have about the probability of different values within this set. Traditional statistical techniques deal with the situations in which we have a complete information about the probabilities; in real life, however, we often have only partial information about them. We therefore need to describe methods of handling such partial information in risk analysis. Several such techniques have been presented, often on …

Detection Of Cracks At Rivet Holes In Thin Plates Using Lamb-Wave Scanning, Roberto A. Osegueda, Vladik Kreinovich, Soheil Nazarian, Enrique Roldan

Departmental Technical Reports (CS)

This paper describes a Lamb-wave scanning method for the detection of notches simulating cracks at rivet holes in thin plates. The approach requires the generation of an ultrasonic So-Mode Lamb wave using an incident transmitter excited with a tone burst centered at a near non-dispersive frequency. Area scans are performed of a plate with a hole with a notch to generate times series information which is used to create animations illustrating the wave propagation characteristics. The time series are subject to a sifting process to obtain intrinsic mode functions which contain narrow frequency banded information of the signals. The Hilbert-Huang …

Complexity Of Single-Agent And Equilibrium-Based Multiagent Planning And Plan Checking: Approach When We Have A List Of Valid States, Chitta Baral, Vladik Kreinovich

Departmental Technical Reports (CS)

In a recent paper M. Bowling, R. Jensen, and M. Veloso proposed a new formalization of the problem of multiagent planning - a formalization that is based on the (intuitively natural) notion of an equilibrium. In this paper we analyze the computational complexity of the corresponding equilibrium-based multiagent planning and plan checking. Within the traditional approach in which states are described by fluents, the computational complexity of planning under incompleteness is PSPACE-hard already for a single agent; therefore, to make a meaningful comparison between the complexity of single-agent and multi-agent planning, we analyze complexity in a different approach, in which …

Are There Easy-To-Check Necessary And Sufficient Conditions For Straightforward Interval Computations To Be Exact?, Vladik Kreinovich, Luc Longpre, James J. Buckley

Departmental Technical Reports (CS)

We prove that no "efficient" (easy-to-check) necessary and sufficient conditions are possible for checking whether straightforward interval computations lead to the exact result.

Towards Foundations Of Processing Imprecise Data: From Traditional Statistical Techniques Of Processing Crisp Data To Statistical Processing Of Fuzzy Data, Hung T. Nguyen, Tonghui Wang, Vladik Kreinovich

Departmental Technical Reports (CS)

In traditional statistics, we process crisp data - usually, results of measurements and/or observations. Not all the knowledge comes from measurements and observations. In many real-life situations, in addition to the results of measurements and observations, we have expert estimates, estimates that are often formulated in terms of natural language, like "x is large". Before we analyze how to process these statements, we must be able to translate them in a language that a computer can understand. This translation of expert statements from natural language into a precise language of numbers is one of the main original objectives of fuzzy …

Can Quantum Computers Be Useful When There Are Not Yet Enough Qubits?, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Why Benchmarking Is An (Asymptotically) Optimal Approach To Numerical Methods: A Geombinatoric Proof, Vladik Kreinovich, Scott A. Starks

Departmental Technical Reports (CS)

In numerical mathematics, one of the most frequently used ways of gauging the quality of different numerical methods is benchmarking. Specifically, once we have methods that work well on some (but not all) problems from a given problem class, we find the problem that is the toughest for the existing methods. This problem becomes a benchmark for gauging how well different methods solve problems that previous methods could not. Once we have a method that works well in solving this benchmark problem, we repeat the process again -- by selecting, as a new benchmark, a problem that is the toughest …

Designing Interdisciplinary Approaches To Problem Solving Into Computer Languages, Daniel E. Cooke, Vladik Kreinovich, Joseph E. Urban

Departmental Technical Reports (CS)

Many interdisciplinary design efforts require the involvement of computer scientists because of the complexity of the problem solving tools available for the projects. This paper demonstrates how appropriate language design can place high level languages in the hands of scientists and engineers, thus providing a more automated approach to problem solving that may reduce the amount of computer scientist involvement. The language SequenceL serves as an example of this approach.

Intelligent Techologies, Vladik Kreinovich, Hung T. Nguyen, Nadipuram S. Prasad, Pratit Santiprabhob

Departmental Technical Reports (CS)

No abstract provided.

Universal Approximation Theorem For Uninorm-Based Fuzzy Systems Modeling, Ronald R. Yager, Vladik Kreinovich

Departmental Technical Reports (CS)

Most existing universal approximation results for fuzzy systems are based on the assumption that we use t-conorms and t-conorms to represent "and" and "or". Yager has proposed to use, within the fuzzy system modeling paradigm, more general operations based on uninorms. In this paper, we show that the universal approximation property holds for an arbitrary choice of a uninorm.

Absolute Bounds On The Mean Of Sum, Product, Max, And Min: A Probabilistic Extension Of Interval Arithmetic, Scott Ferson, Lev Ginzburg, Vladik Kreinovich, Jorge Lopez

Departmental Technical Reports (CS)

We extend the main formulas of interval arithmetic for different arithmetic operations x1*x2 to the case when, for each input xi, in addition to the interval [xi]=[xi-,xi+] of possible values, we also know its mean Ei (or an interval [Ei] of possible values of the mean), and we want to find the corresponding bounds for x1*x2 and its mean.