Computer Engineering Commons^™

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 …

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

Departmental Technical Reports (CS)

No abstract provided.

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.

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.

An Idl/Envi Implementation Of The Fft Based Algorithm For Automatic Image Registration, Hongjie Xie, Nigel Hicks, George R. Keller, Haitao Huang, Vladik Kreinovich

Departmental Technical Reports (CS)

Georeferencing images is a laborious process so schemes for automating this process have been under investigation for some time. Among the most promising automatic registration algorithms aare those based on Fast Fourier Transform (FFT). The displacement between the two given images can be computed by computing the ratio F1*conj(F2)/|F1*F2|, and then applying the inverse Fourier transform. The result is an impulse-like function, which is approximately zero everywhere except at the displacement that is necessary to optimally register the images. Coverting from rectangular coordinates to log-polar coordinates, shifts representing rotation and scaling can be also determined to complete the georectification process. …

Research On Advanced Soft Computing And Its Applications (Introduction To The Special Issue), Vilem Novak, Irina Perfilieva, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

The main objective for the research presented in this special issue is to advance theoretical basis in soft computing, for the purpose of improving applications.

Why is this theoretical research needed? Because soft computing in general (and intelligent control and decision making in particular) are, in many aspects, still an art. To make this methodology easier to apply, we must use the experience of successful applications of fuzzy control, decision making or classification and extract formal rules that would capture this experience. To be able to do that efficiently, we must understand why some versions of soft computing methodology turned …

Towards More Realistic (E.G., Non-Associative) And- And Or-Operations In Fuzzy Logic, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Interval Computations Related To Privacy In Statistical Databases, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

We show that the need to maintain privacy in statistical databases naturally leads to interval computations, and provide feasible algorithms for the corresponding interval computation problems.

From [0,1]-Based Logic To Interval Logic (From Known Description Of All Possible [0,1]-Based Logical Operations To A Description Of All Possible Interval-Based Logical Operations), Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

Since early 1960s, we have a complete description of all possible [0,1]-based logical operations, namely of "and"-operations (t-norms) and of "or"-operations (t-conorms). In some real-life situations, intervals provide a more adequate way of describing uncertainty, so we need to describe interval-based logical operations. Usually, researchers followed a pragmatic path and simply derived these operations from the [0,1]-based ones. From the foundational viewpoint, it is desirable not to a priori restrict ourselves to such derivative operations but, instead, to get a description of all interval-based operations which satisfy reasonable properties.

Such description is presented in this paper. It turns out that …

Kolmogorov Complexity And Chaotic Phenomena, Vladik Kreinovich, Isaak 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, ...).

Specifically, in addition to the equations, physicists use the following additional difficult-to-formalize property: that the initial conditions and the value of the parameters must not be abnormal. We will describe a natural formalization of this property, and show that this formalization in good accordance with theoretical physics. At present, this formalization has been mainly applied to the foundations of physics. However, potentially, more practical …

Fuzzy Measures And Integrals As Aggregation Operators: Solving The Commensurability Problem, Francois Modave, Vladik Kreinovich

Departmental Technical Reports (CS)

The aim of this paper is to shed some light on the use of fuzzy measures and integrals as aggregation operators in multicriteria decision making. These techniques have been widely used on an ad hoc basis, but with no axiomatization. It is possible to obtain preference representation theorems in multicriteria decision making problems, relying on a formal parallelism between decision under uncertainty and multicriteria decision making. Though, it raises some commensurability problems. In this paper, we show how to obtain an axiomatization of multicriteria decision making problems, in a very natural way, and we show how to solve the commensurability …

Main Ideas Behind Owa Lead To A Universal And Optimal Approximation Scheme, Ronald R. Yager, Vladik Kreinovich

Departmental Technical Reports (CS)

Ordered Weighted Averaging (OWA) operators have been successfully applied in many practical problems. We explain this empirical success by showing that these operators are indeed guaranteed to work (i.e., are universal), and that these operators are the best to use (in some reasonable sense).

Selecting A Fuzzy Logic Operation From The Dnf-Cnf Interval: How Practical Are The Resulting Operations?, I. B. Turksen, A. Esper, K. Patel, Scott A. Starks, Vladik Kreinovich

Departmental Technical Reports (CS)

In classical (two-valued) logic, CNF and DNF forms of each propositional formula are equivalent to each other. In fuzzy logic, CNF and DNF forms are not equivalent, they form an interval that contains the fuzzy values of all classically equivalent propositional formulas. If we want to select a single value from this interval, then it is natural to select a linear combination of the interval's endpoints. In particular, we can do that for CNF and DNF forms of "and" and "or", thus designing natural fuzzy analogues of classical "and" and "or" operations. The problem with thus selected "and" and "or" …

Why Is Selecting The Simplest Hypothesis (Consistent With Data) A Good Idea? A Simple Explanation, Vladik Kreinovich, Luc Longpre, Scott Ferson, Lev Ginzburg

Departmental Technical Reports (CS)

No abstract provided.

From Computation With Guaranteed Intervals To Computation With Confidence Intervals: A New Application Of Fuzzy Techniques, Vladik Kreinovich, Hung T. Nguyen, Scott Ferson, Lev Ginzburg

Departmental Technical Reports (CS)

Traditional interval computations provide an estimate for the result y=f(x1,...,xn) of data processing when we know intervals X1,...,Xn that are guaranteed to contain the (unknown) actual values of the quantities x1,...,xn. Often, in addition to these guaranteed intervals, we have confidence intervals for these quantities, i.e., intervals Xi that contain the corresponding values xi with a certain probability. It is desirable, based on the confidence intervals for xi, to produce the resulting confidence interval for y. It turns out that the formulas for computing such resulting confidence interval are closely related with the formulas for processing fuzzy numbers by using …

Interval Mathematics For Analysis Of Multiresolutional Systems, Vladik Kreinovich, Richard Alo

Departmental Technical Reports (CS)

The more complex the problem, the more complex the system necessary for solving this problem. For very complex problems, it is no longer possible to design the corresponding system on a single resolution level, it becomes necessary to have multiresolutional systems. When analyzing such systems -- e.g., when estimating their performance and/or their intelligence -- it is reasonable to use the multiresolutional character of these systems: first, we analyze the system on the low-resolution level, and then we sharpen the results of the low-resolution analysis by considering higher-resolution representations of the analyzed system. The analysis of the low-resolution level provides …

Range Estimation Is Np-Hard For Epsilon-Square Accuracy And Feasible For Epsilon To The Power Of 2-Delta, Vladik Kreinovich

Departmental Technical Reports (CS)

The basic problem of interval computations is: given a function f(x1,...,xn) and n intervals [xi-,xi+], find the (interval) range Y of the given function on the given intervals. It is known that even for quadratic polynomials f(x1,...,xn), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound "epsilon" on the width of the input intervals tends to 0. We show that for small c>0, if we want to compute the range with an accuracy c times epsilon squared, then the problem is still NP-hard; on …

Computing Variance For Interval Data Is Np-Hard, Scott Ferson, Lev Ginzburg, Vladik Kreinovich, Luc Longpre, Monica Aviles

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 lower bound V- on the variance of interval data. We also provide a feasible algorithm that computes V+ under reasonable easily verifiable conditions.

On Efficient Representation Of Expert Knowledge By Fuzzy Logic: Towards An Optimal Combination Of Granularity And Higher-Order Approaches, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

A natural approach to designing an intelligent system is to incorporate expert knowledge into this system. One of the main approaches to translating this knowledge into computer-understandable terms is the approach of fuzzy logic. It has led to many successful applications, but in several aspects, the resulting computer representation is somewhat different from the original expert meaning. Two related approaches have been used to make fuzzy logic more adequate in representing expert reasoning: granularity and higher-order approaches. Each approach is successful in some applications where the other approach did not succeed so well; it is therefore desirable to combine these …

Exact Bounds On Sample Variance Of Interval Data, Scott Ferson, Lev Ginzburg, Vladik Kreinovich, Monica Aviles

Departmental Technical Reports (CS)

We provide a feasible (quadratic time) algorithm for computing the lower bound on the sample variance V of interval data. The problem of computing the upper bound on V is, in general, NP-hard. We provide a feasible algorithm that computes the upper bound on V for many reasonable situations.

Detecting And Locating Curved Cracks In Thin Plates By Lamb Wave Reflection: Validated Geometric Approach, Roberto A. Osegueda, Vladik Kreinovich

Departmental Technical Reports (CS)

Lamb waves propagate through a thin plate, and thus, provide a way of scanning this plate and detecting cracks and other faults. The equations describing these waves are rather complex, and, as a result, it is difficult to extract, from the received signal, the location of the fault. Recently, a new geometric approach has been proposed which allows, for linear cracks, to determine the presence and the location of a crack by using only the geometry of wave propagation. In this paper, we extend this approach to a more realistic case of curved cracks, and apply interval techniques to provide …

Optimization Techniques Under Uncertain Criteria, And Their Possible Use In Computerized Education, Vladik Kreinovich, Richard Alo

Departmental Technical Reports (CS)

The existing successful automated computerized systems more or less simulate the way successful human teachers teach. However, computerized systems provide more individualized options that traditional classroom education, and it is desirable to use this additional freedom to further improve the education success rate. In this papers, we briefly overview the experience of a successful Russian training system, and explain how general techniques of optimization under uncertainty can be used to optimize the content development.

On The Optimal Choice Of Quality Metric In Image Compression, Olga Kosheleva, Vladik Kreinovich, Yeung Yam

Departmental Technical Reports (CS)

No abstract provided.

Extending Direct Manipulation In A Text Editor, David G. Novick, Francisco Romero, Edgar Rene Saenz, Armando Sandoval

Departmental Papers (CS)

This paper describes the implementation of a prototype text editor that incorporates conversation-like features through the direct-manipulation modality. In this way, traditional direct-manipulation interaction techniques such as direct reference via pointing can be extended to include techniques more commonly associated with human conversation, such as negotiation of reference. The paper illustrates the use of the prototype with an extended example, and discusses research issues raised by the implementation.

Open-Ended Configurations Of Radio Telescopes: Towards Optimal Design, Vladik Kreinovich, Scott A. Starks, Olga Kosheleva, Andrei Finkelstein

Departmental Technical Reports (CS)

The quality of radio astronomical images drastically depends on where we place the radio telescopes. During the design of the Very Large Array, it was empirically shown that the power law design, in which n-th antenna is placed at a distance n^b from the center, leads to the best image quality. In this paper, we provide a theoretical justification for this empirical fact.

Was There Satan's Face In The World Trade Center Fire? A Geometric Analysis, Vladik Kreinovich, Dima Iourinski

Departmental Technical Reports (CS)

Some photos of the 2001 World Trade Center fire reveal a "face" in the smoke which was interpreted, by some people, as the face of Satan. Most journalists believe, however, that the visible smoke configuration can be explained by natural processes, and that the visible "face" is similar to animal shapes that are sometimes observed in the clouds. In this paper, we present a simple geometric analysis that supports this natural-process explanation.

Open-Ended Configurations Of Radio Telescopes: Geometrical Analysis, Vladik Kreinovich, Scott A. Starks, Dima Iourinski, Olga Kosheleva, Andrei Finkelstein

Departmental Technical Reports (CS)

No abstract provided.

On Symmetric Solution Sets, Goetz Alefeld, Vladik Kreinovich, Guenter Mayer

Departmental Technical Reports (CS)

Given an n x n interval matrix [A] and an interval vector [b] with n components we present an overview on existing results on the solution set S of linear systems of equations Ax=b with symmetric matrices A from [A] and vectors b from [b]. Similarly we consider the set E of eigenpairs associated with the symmetric matrices A from [A]. We report on characterizations of S by means of inequalities, by means of intersection of sets, and by an approach which is generalizable to more general dependencies of the entries. We also recall two methods for enclosing S by …

Probability Of Implication, Logical Version Of Bayes Theorem, And Fuzzy Logic Operations, Hung T. Nguyen, Masao Mukaidono, Vladik Kreinovich

Departmental Technical Reports (CS)

Logical inference starts with concluding that if B implies A, and B is true, then A is true as well. To describe probabilistic inference rules, we must therefore define the probability of an implication "A if B". There exist two different approaches to defining this probability, and these approaches lead to different probabilistic inference rules: We may interpret the probability of an implication as the conditional probability P(A|B), in which case we get Bayesian inference. We may also interpret this probability as the probability of the material implication "A or not B", in which case we get different inference rules. …