Computer Science Department

Abstracts of 2004 Reports

Technical Report UTEP-CS-04-42, December 2004

Updated version UTEP-CS-04-42a, February 2005

To Properly Reflect Physicists' Reasoning about Randomness, We Also Need a Maxitive (Possibility) Measure

Andrei M. Finkelstein, Olga Kosheleva, Vladik Kreinovich, Scott A. Starks, and Hung T. Nguyen

Published in *Proceedings of the 2005 IEEE International
Conference on Fuzzy Systems FUZZ-IEEE'2005*, Reno, Nevada, May 22-25,
2005, pp. 1044-1049.

According to the traditional probability theory, events with a positive but very small probability can occur (although very rarely). For example, from the purely mathematical viewpoint, it is possible that the thermal motion of all the molecules in a coffee cup goes in the same direction, so this cup will start lifting up.

In contrast, physicists believe that events with extremely small probability cannot occur. In this paper, we show that to get a consistent formalization of this belief, we need, in addition to the original probability measure, to also consider a maxitive (possibility) measure.

Original file in Compressed PostScript and
in pdf

updated file in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-41, December 2004

Updated version UTEP-CS-04-41a, July 2005

Interval Versions of Statistical Techniques with Applications to Environmental Analysis, Bioinformatics, and Privacy in Statistical Databases

Vladik Kreinovich, Luc Longpre, Scott A. Starks, Gang Xiang, Jan Beck, Raj Kandathi, Asis Nayak, Scott Ferson, and Janos Hajagos

Published in *Journal of Computational and Applied
Mathematics*, 2007, Vol. 199, No. 2, pp. 418-423.

In many areas of science and engineering, it is desirable to estimate statistical characteristics (mean, variance, covariance, etc.) under interval uncertainty. For example, we may want to use the measured values x(t) of a pollution level in a lake at different moments of time to estimate the average pollution level; however, we do not know the exact values x(t) -- e.g., if one of the measurement results is 0, this simply means that the actual (unknown) value of x(t) can be anywhere between 0 and the detection limit DL. We must therefore modify the existing statistical algorithms to process such interval data.

Such a modification is also necessary to process data from statistical databases, where, in order to maintain privacy, we only keep interval ranges instead of the actual numeric data (e.g., a salary range instead of the actual salary).

Most resulting computational problems are NP-hard -- which means, crudely speaking, that in general, no computationally efficient algorithm can solve all particular cases of the corresponding problem. In this paper, we overview practical situations in which computationally efficient algorithms exist: e.g., situations when measurements are very accurate, or when all the measurements are done with one (or few) instruments.

As a case study, we consider a practical problem from bioinformatics: to discover the genetic difference between the cancer cells and the healthy cells, we must process the measurements results and find the concentrations c and h of a given gene in cancer and in healthy cells. This is a particular case of a general situation in which, to estimate states or parameters which are not directly accessible by measurements, we must solve a system of equations in which coefficients are only known with interval uncertainty. We show that in general, this problem is NP-hard, and we describe new efficient algorithms for solving this problem in practically important situations.

Original file in Compressed PostScript and
in pdf.

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-40, December 2004

Monte-Carlo-Type Techniques for Processing Interval Uncertainty, and Their Geophysical and Engineering Applications

Matthew G. Averill, Kate C. Miller, G. Randy Keller, Vladik Kreinovich, Jan Beck, Roberto Araiza, Roberto Torres, and Scott A. Starks

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 is the upper bound D on the measurement error, so when the measured value is X, we conclude that x is in [X-D,X+D]. For this interval uncertainty, the resulting velocity accuracy is, qualitatively, in much better accordance with geophysics.

Interval uncertainty naturally appears in other applications as well. In this paper, we describe Monte-Carlo-Type techniques for processing interval uncertainty, and their geophysical and engineering applications.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-39, December 2004

Updated version UTEP-CS-04-39a, August 2005

From Intervals to Domains: Towards a General Description of Validated Uncertainty, with Potential Applications to Geospatial and Meteorological Data

Vladik Kreinovich, Olga Kosheleva, Scott A. Starks, Kavitha Tupelly, Gracaliz P. Dimuro, Antonio Carlos da Rocha Costa, and Karen Villaverde

Published in *Journal of Computational and Applied
Mathematics*, 2007, Vol. 199, No. 2, pp. 411-417.

When physical quantities xi are numbers, then the corresponding measurement accuracy can be usually represented in interval terms, and interval computations can be used to estimate the resulting uncertainty in y=f(x1,...,xn).

In some practical problems, we are interested in more complex structures such as functions, operators, etc. Examples: we may be interested in how the material strain depends on the applied stress, or in how a physical quantity such as temperature or velocity of sound depends on a 3-D point.

For many such structures, there are ways to represent uncertainty, but usually, for each new structure, we have to perform a lot of complex analysis from scratch. It is desirable to come up with a general methodology that would automatically produce a natural description of validated uncertainty for all physically interesting situations (or at least for as many such situations as possible). In this talk, we describe the foundations for such a methodology; it turns out that this problem naturally leads to the technique of domains first introduced by D. Scott in the 1970s.

In addition to general domain techniques, we also describe applications to geospatial and meteorological data.

Original file in Compressed PostScript and
in pdf;

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-38, December 2004

The Multi-Layered Interval Categorizer Tesselation-Based Model

Marilton S. de Aguiar, Gracaliz P. Dimuro, Antonio C. da R. Costa, Rafael K. S. Silva, Fabia A. da Costa, and Vladik Kreinovich

Published in
Cirano Iochpe and Gilberto Camara (eds.),
*IFIP WG2.6 Proceedings of the 6th Brazilian Symposium on
Geoinformatics Geoinfo'2004*,
Campos do Jordao, Brazil, November 22-24, 2004,
pp. 437-454. ISBN 3901882200

Technical Report UTEP-CS-04-37, December 2004

Short version UTEP-CS-04-37a, April 2005

Updated version UTEP-CS-04-37b, August 2005

Interval-Type and Affine Arithmetic-Type Techniques for Handling Uncertainty in Expert Systems, with Applications to Geoinformatics and Computer Security

Martine Ceberio, Vladik Kreinovich, Sanjeev Chopra, Luc Longpre, Hung T. Nguyen, Bertram Ludaescher, and Chitta Baral

Short version published in the *Proceedings of the 17th World
Congress of the International Association for Mathematics and
Computers in Simulation IMACS'2005*, Paris, France, July 11-15,
2005; full paper published in *Journal of Computational and
Applied Mathematics*, 2007, Vol. 199, No. 2, pp. 403-410.

Expert knowledge consists of statements Sj (facts and rules). The expert's degree of confidence in each statement Sj can be described as a (subjective) probability (some probabilities are known to be independent). Examples: if we are interested in oil, we should look at seismic data (confidence 90%); a bank A trusts a client B, so if we trust A, we should trust B too (confidence 99%). If a query Q is deducible from facts and rules, what is our confidence p(Q) in Q? We can describe Q as a propositional formula F in terms of Sj; computing p(Q) exactly is NP-hard, so heuristics are needed.

Traditionally, expert systems use technique similar to straightforward interval computations: we parse F and replace each computation step with corresponding probability operation. Problem: at each step, we ignore the dependence between the intermediate results Fj; hence intervals are too wide. Example: the estimate for P(A\/~A) is not 1. Solution: similarly to affine arithmetic, besides P(Fj), we also compute P(Fj & Fi) (or P(Fj & ... & Fk)), and on each step, use all combinations of l such probabilities to get new estimates. Results: e.g., P(A\/~A) is estimated as 1.

Original file in Compressed PostScript and
in pdf.

Short version in Compressed PostScript and
in pdf.

Revised version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-36, December 2004

Advanced Relation Model for Genome Sequence Visualization (ARM 4 GSV): Exploratory Visualization Examples

Brian J. d'Auriol and Kavitha Tupelly

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 the earlier work, is discussed. Applications of the ARM 4 GSV to codon usage distribution and close inversion distribution are discussed. These applications are accompanied by many visualization figures of a 269 base RNA molecule, a part of the Hepatitis C virus NS5 gene, Locus AY769711. Our presentation illustrates the extent and flexibility of our approach. We conclude by observing that our objectives of showing the potential usefulness of our proposed visualization model are met.

Technical Report UTEP-CS-04-35, November 2004

Foundations of Statistical Processing of Set-Valued Data: Towards Efficient Algorithms

Hung T. Nguyen, Vladik Kreinovich, and Gang Xiang

Published in *Proceedings of the Fifth International
Conference on Intelligent Technologies InTech'04*,
Houston, Texas, December 2-4, 2004.

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 statistics to statistics of such set-valued data, and describe how this foundation can lead to efficient algorithms for computing the corresponding set-valued statistics.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-34, November 2004

Updated version UTEP-CS-04-34a, April 2006

Expert System-Type Approach to Voice Disorders: Scheduling Botulinum Toxin Treatment for Adductor Spasmodic Dysphonia

Anthony P. Salvatore, Amitava Biswas, Vladik Kreinovich, Bertha Manriquez, Michael P. Cannito, and Robert J. Sinard

Short version published in *Proceedings of the Fifth International
Conference on Intelligent Technologies InTech'04*,
Houston, Texas, December 2-4, 2004; full paper published in
*Journal of
Advanced Computational Intelligence and Intelligent Informatics*,
2006, Vol. 10, No. 3, pp. 332-338.

One of the most debilitating disorders is adductor spasmodic dysphonia (ADSD), a voice disorder caused by involuntary movements of the muscles of the larynx (voice box). For treating ADSD, botulinum toxin (BT) injections turned out to be very useful. However, the effects of BT are highly variable, so at present, there is no objective criterion of when such a BT treatment is necessary. It is therefore desirable to develop such a criterion.

In this paper, we show that traditional statistical techniques are unable to generate such a criterion, while a natural expert system approach seems to be capable of generating reasonably simple rules that determine when a BT treatment is necessary.

Original file in Compressed PostScript and
in pdf;

updated file in pdf.

Technical Report UTEP-CS-04-33, November 2004

Updated version UTEP-CS-04-33a, April 2005

Random Interval Arithmetic is Closer to Common Sense: An Observation

Rene Alt, Jean-Luc Lamotte, and Vladik Kreinovich

Published in the *Proceedings of the
17th World Congress of the
International Association for Mathematics and Computers in
Simulation IMACS'2005*, Paris, France, July 11-15, 2005.

From the commonsense viewpoint, if on a bridge whose weight we know with an accuracy of 1 ton, we place a car whose weight we know with an accuracy of 5 kg, then the accuracy with which we know the overall weight of a bridge with a car on it should still be 1 ton. This is what an engineer or a physicist would say. Alas, this is not so in traditional interval arithmetic. In this paper, we show that, in contrast to traditional interval arithmetic, the random interval arithmetic (proposed by the first two authors) actually has this important property.

Original file in Compressed PostScript and
in pdf;

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-32, October 2004

Updated version UTEP-CS-04-32b, April 2005

Towards an Optimal Approach to Soft Constraint Problems

Martine Ceberio and Vladik Kreinovich

Published in the *Proceedings of the
17th World Congress of the
International Association for Mathematics and Computers in
Simulation IMACS'2005*, Paris, France, July 11-15, 2005.

In traditional constraint satisfaction, constraints are ``hard'' in the sense that we need to satisfy them all. In many practical situations, however, constraints are "soft" in the sense that if we are unable to satisfy some of them, the corresponding solution is still practically useful. In such situations, it is desirable to satisfy as many high-priority constraints as possible. In this paper, we describe an optimal algorithm for solving the corresponding soft constraint problem.

Original file in Compressed PostScript and
in pdf

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-31, September 2004

Updated version UTEP-04-31a, March 2005

Fast Algorithm for Computing the Upper Endpoint of Sample Variance for Interval Data: Case of Sufficiently Accurate Measurements

Gang Xiang

Published in *Reliable Computing*, 2006, Vol. 12, No. 1,
pp. 59-64.

When we have n results x1,...,xn of repeated measurement of the same quantity, the traditional statistical approach usually starts with computing their sample average E and their sample variance V. Often, due to the inevitable measurement uncertainty, we do not know the exact values of the quantities, we only know the intervals [xi] of possible values of xi. In such situations, for different possible values xi from [xi], we get different values of the variance. We must therefore find the range [V] of possible values of V. It is known that in general, this problem is NP-hard. For the case when the measurements are sufficiently accurate (in some precise sense), it is known that we can compute the interval [V] in quadratic time O(n^2). In this paper, we describe a new algorithm for computing [V] that requires time O(n log(n)) (which is much faster than O(n^2)).

Original file in Compressed PostScript and
in pdf;

updated file in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-30, September 2004

A Model of Computer Science Graduate Admissions Decisions

Nigel Ward

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.

Technical Report UTEP-CS-04-29, September 2004

Updated version UTEP-CS-04-29a, November 2004

Final version UTEP-CS-04-29b, April 2006

Testing Hypotheses on Simulated Data: Why Traditional Hypotheses-Testing Statistics are Not Always Adequate for Simulated Data, and How to Modify Them

Richard Alo, Vladik Kreinovich, and Scott A. Starks

Short version published in *Proceedings of the Fifth International
Conference on Intelligent Technologies InTech'04*,
Houston, Texas, December 2-4, 2004; full paper published in
*Journal of
Advanced Computational Intelligence and Intelligent Informatics*,
2006, Vol. 10, No. 3, pp. 260-264.

To check whether a new algorithm is better, researchers use traditional statistical techniques for hypotheses testing. In particular, when the results are inconclusive, they run more and more simulations (n2>n1, n3>n2, ..., nm) until the results become conclusive. In this paper, we point out that these results may be misleading. Indeed, in the traditional approach, we select a statistic and then choose a threshold for which the probability of this statistic "accidentally" exceeding this threshold is smaller than, say, 1%. It is very easy to run additional simulations with ever-larger n. The probability of error is still 1% for each ni, but the probability that we reach an erroneous conclusion for at least one of the values ni increases as m increases. In this paper, we design new statistical techniques oriented towards experiments on simulated data, techniques that would guarantee that the error stays under, say, 1% no matter how many experiments we run.

Original file in Compressed PostScript and
in pdf;

Updated version in Compressed PostScript and
in pdf;

Final version in pdf.

Technical Report UTEP-CS-04-28, September 2004

Updated version UTEP-CS-04-28a, November 2004

Computing the Cube of an Interval Matrix is NP-Hard

Olga Kosheleva, Vladik Kreinovich, Guenter Mayer, and Hung T. Nguyen

Published in *Proceedings of the 2005 ACM Symposium on Applied
Computing*, Santa Fe, New Mexico, March 13-17, 2005,
pp. 1449-1453.

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 prove that the problems of computing the exact ranges for the product of three matrices -- and for the third power of a matrix -- are NP-hard.

Original file in Compressed PostScript and
in pdf;

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-27, September 2004

Updated version UTEP-CS-04-27a, December 2004

Final version UTEP-CS-04-27b, February 2005

Exact Bounds for Interval and Fuzzy Functions under Monotonicity Constraints, with Potential Applications to Biostratigraphy

Emil Platon, Kavitha Tupelly, Vladik Kreinovich, Scott A. Starks, and Karen Villaverde

Published in *Proceedings of the 2005 IEEE International
Conference on Fuzzy Systems FUZZ-IEEE'2005*, Reno, Nevada, May 22-25,
2005, pp. 891-896.

The age of fossil species in samples recovered from a well that penetrates an undisturbed sequence of sedimentary rocks increases with depth. The results of biostratigraphic analysis of such a sequence consist of several age-depth values -- both known with interval (or fuzzy) uncertainty -- and we would like to find, for each possible depth, the interval of the possible values of the corresponding age. A similar problem of bounding an intervally (fuzzily) defined function under monotonicity constraint occurs in many other application areas. In this paper, we provide an efficient algorithm for solving this problem.

Original file in Compressed PostScript and
in pdf.

Updated version in Compressed PostScript and
in pdf.

Final version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-26, August 2004

Updated Version UTEP-CS-04-26a, November 2004

Probabilistic Approach to Trust: Ideas, Algorithms, And Simulations

Pattama Jaksurat, Eric Freudenthal, Martine Ceberio, and Vladik Kreinovich

Published in *Proceedings of the Fifth International
Conference on Intelligent Technologies InTech'04*,
Houston, Texas, December 2-4, 2004.

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 track of trust probabilities, so that we should only delegate to agents whose trust is above a certain threshold. In this paper, we present efficient algorithms for handling such probabilities.

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-25, August 2004

Final version UTEP-CS-04-25a, June 2005

Computing Best-Possible Bounds for the Distribution of a Sum of Several Variables is NP-Hard

Vladik Kreinovich and Scott Ferson

Published in *International Journal of Approximate
Reasoning*, 2006, Vol. 41, pp. 331-342.

In many real-life situations, we know the probability distribution of two random variables x1 and x2, but we have no information about the correlation between x1 and x2; what are the possible probability distributions for the sum x1+x2? This question was originally raised by A. N. Kolmogorov. Algorithms exist that provide best-possible bounds for the distribution of x1+x2; these algorithms have been implemented as a part of the efficient software for handling probabilistic uncertainty. A natural question is: what if we have several (n>2) variables with known distribution, we have no information about their correlation, and we are interested in possible probability distribution for the sum y=x_1+...+xn? Known formulas for the case n=2 can be (and have been) extended to this case. However, as we prove in this paper, not only are these formulas not best-possible anymore, but in general, computing the best-possible bounds for arbitrary n is an NP-hard (computationally intractable) problem.

Original file in Compressed PostScript and
in pdf;

Final version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-24, August 2004

Updated version UTEP-CS-04-24a, April 2005

Final version UTEP-CS-04-24b, June 2005

Why Product of Probabilities (Masses) for Independent Events? A Remark

Vladik Kreinovich and Scott Ferson

Published in *International Journal of Pure and Applied
Mathematics*, 2005, Vol. 22, No. 3, pp. 341-347.

For independent events A and B, the probability P(A&B) is equal to the product of the corresponding probabilities: P(A&B)=P(A)*P(B). It is well known that the product f(a,b)=a*b has the following property: once P(A1)+...+P(An)=1 and P(B1)+...+P(Bm)=1, the probabilities P(Ai&Bj)=f(P(Ai),P(Bj)) also add to 1: f(P(A1),P(B1))+...+f(P(An),P(Bm))=1. We prove that the product is the only function that satisfies this property, i.e., that if, vice versa, this property holds for some function f(a,b), then this function f is the product. This result provided an additional explanation of why for independent events, we multiply probabilities (or, in the Dempster-Shafer case, masses).

In this paper, we strengthen this result by showing that it holds for arbitrary (not necessarily continuous) functions f(a,b).

Original file in Compressed PostScript and
in pdf;

Updated version in Compressed PostScript and
in pdf;

Final version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-23, August 2004

Updated version UTEP-CS-04-23c, December 2005

Monte-Carlo-Type Techniques for Processing Interval Uncertainty, and Their Potential Engineering Applications

V. Kreinovich, J. Beck, C. Ferregut, A. Sanchez, G. R. Keller, M. Averill, and S. A. Starks

Original version published in *Proceedings of the Workshop on Reliable Engineering
Computing*,
Savannah, Georgia, September 15-17, 2004, pp. 139-160; detailed version
published in *Reliable Computing*, 2007, Vol. 13, No. 1, pp.
25-69.

In engineering applications, we need to make decisions
under uncertainty. Traditionally, in engineering,
statistical methods are used, methods
assuming that we know the probability distribution of different
uncertain parameters.
Usually, we can safely
linearize the dependence of the desired quantities *y* (e.g., stress
at different structural points) on the uncertain parameters *xi* -
thus enabling sensitivity analysis. Often, the number *n*
of uncertain parameters is huge, so
sensitivity analysis leads to a lot of computation time.
To speed up the processing, we propose to use special
Monte-Carlo-type simulations.

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-22, August 2004

Non-Lexical Conversational Sounds in American English

Nigel Ward

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 across contexts; and so the meanings of conversational grunts are largely a product of sound symbolism. This analysis is compatible with acoustic and cognitive factors which are present in the conversational contexts where grunts occur.

Technical Report UTEP-CS-04-21, August 2004

Generating Properties for Runtime Monitoring from Software Specification Patterns

Oscar Mondragon, Ann Q. Gates, and Oleg Sokolsky

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 properties. The paper describes the mapping that translates FIL formulas into MEDL formulas and demonstrates its correctness.

Technical Report UTEP-CS-04-20b, June 2005

Towards Combining Probabilistic and Interval Uncertainty in Engineering Calculations: Algorithms for Computing Statistics under Interval Uncertainty, and Their Computational Complexity

V. Kreinovich, G. Xiang, S. A. Starks, L. Longpre, M. Ceberio, R. Araiza, J. Beck, R. Kandathi, A. Nayak, R. Torres, and J. Hajagos

Published in *Reliable Computing*, 2006, Vol. 12, No. 6, pp.
471-501.

In many engineering applications, we have to combine probabilistic and interval uncertainty. 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 measure the values with interval uncertainty. We must therefore modify the existing statistical algorithms to process such interval data.

In this paper, we provide a survey of algorithms for computing various statistics under interval uncertainty and their computational complexity. The survey includes both known and new algorithms.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-20, July 2004

Towards Combining Probabilistic and Interval Uncertainty in Engineering Calculations

S. A. Starks, V. Kreinovich, L. Longpre, M. Ceberio, G. Xiang, R. Araiza, J. Beck, R. Kandathi, A. Nayak, and R. Torres

Published in *Proceedings of the Workshop on Reliable Engineering
Computing*,
Savannah, Georgia, September 15-17, 2004, pp. 193-213.

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.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-19, July 2004

Updated version UTEP-CS-04-19a, November 2004

Checking if There Exists a Monotonic Function That is Consistent with the Measurements: An Efficient Algorithm

Kavitha Tupelly, Vladik Kreinovich, and Karen Villaverde

Published in *Reliable Computing*,
2005, Vol. 11, No. 4, pp. 291-312.

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 this paper, we extend this algorithm to a more
general (and more realistic) situation when both *xi* and
*yi* are
known with interval uncertainty.

Original file in Compressed PostScript and
in pdf.

Updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-18, June 2004

GEON: Geophysical Data Add the 3rd Dimension in Geospatial Studies

R. Aldouri, G. R. Keller, A. Gates, J. Rasillo, L. Salayandia, V. Kreinovich, J. Seeley, P. Taylor, and S. Holloway

Published in *Proceedings of the ESRI International User
Conference 2004*, San Diego, California,
August 9-13, 2004, Paper 1898.

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 create a raster image for more analysis and interpretation. New tools are under development to allow a user to upload their own data sets in text format that will use ArcGIS tools to combine these data with other datasets, create map displays, or create a raster image.

Technical Report UTEP-CS-04-17, May 2004

Using 1-D Radar Observations to Detect a Space Explosion Core Among the Explosion Fragments: Sequential and Distributed Algorithms

P. Debroux, J. Boehm, F. Modave, V. Kreinovich, G. Xiang, J. Beck, K. Tupelly, R. Kandathi, L. Longpre, and K. Villaverde

Published in *Proceedings of the 11th IEEE
Digital Signal Processing Workshop*, Taos, New Mexico, August 1-4,
2004, pp. 273-277.

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.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-16, May 2004

Using FFT-Based Data Processing Techniques to Characterize Asphaltic Concrete Mixtures

S. A. Starks, V. Kreinovich, R. Araiza, S. Nazarian, J. Adidhela

Published in *Proceedings of the 11th IEEE
Digital Signal Processing Workshop*, Taos, New Mexico, August 1-4,
2004, pp. 241-245.

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. Thus, instead of performing expensive measurements for different
frequencies, we can measure the dependence of *E* on moderate
frequencies *f* for different temperatures, and then combine
the resulting curves into a single "master" curve. In this paper, we
show how DSP techniques can help to automate this "combination".

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-15, May 2004

Geometry of Protein Structures. I. Why Hyperbolic Surfaces are a Good Approximation for Beta-Sheets

Boguslaw Stec and Vladik Kreinovich

Published in *Geombinatorics*, 2005, Vol. 15, No. 1, pp.
18-27.

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. In this paper, we show that, under reasonable assumptions, these second order surfaces are indeed the best approximating family for beta-sheets.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-14, May 2004

Application of Kolmogorov Complexity to Advanced Problems in Mechanics

Vladik Kreinovich and Isaak A. Kunin

To appear in: *Proceedings of the
Advanced Problems in Mechanics Conference APM'04*
St. Petersburg, Russia, June 24-July 1, 2004

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.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-13, May 2004

Updated version UTEP-CS-04-13a, September 2004

Second revision UTEP-CS-04-13b, October 2004

Final version UTEP-CS-04-13c, December 2004

Towards Applying Computational Complexity to Foundations of Physics

Vladik Kreinovich and Andrei M. Finkelstein

Published in *Notes of Mathematical Seminars of St. Petersburg
Department of Steklov Institute of Mathematics*, 2004, Vol. 316,
pp. 63-110; reprinted in
*Journal of Mathematical Sciences*, 2006, Vol. 134, No. 5,
pp. 2358-2382.

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.

Original file in Compressed PostScript and
in pdf;

updated file in Compressed PostScript and
in pdf;

second revision in Compressed PostScript and
in pdf

final version in Compressed PostScript and
in pdf

Technical Report UTEP-CS-04-12, April 2004

Towards a General Methodology for Designing Sub-Noise Measurement Procedures

R. Osegueda, G. R. Keller, S. A. Starks, R. Araiza, Dm. Bizyaev, and V. Kreinovich

Published in *Proceedings of 10th
IMEKO TC7 International Symposium*, Saint-Petersburg,
Russia, June 30-July 2, 2004, Vol. 1, pp. 59-64.

In many practical situations,
the measurement result *z* depends not only on the
measured value *x*,
but also on the parameters *s* describing the experiment's setting and
on the values of some auxiliary quantities *y*; the
dependence *z=f(x,s,y)* of *z* on *x*, *s*,
and *y* is usually known. In the
ideal case when we know the exact value of the auxiliary parameter
*y*, we can solve the above equation and find the desired
value *x*.
In many real-life situations, we only know *y* with some uncertainty,
and this uncertainty leads to additional uncertainty in *x*.

If we are trying to reconstruct *x* based on a *single* measurement
result, then, of course, the measurement error in *y* leads to the
corresponding measurement error in *x* - and, unless we perform more
accurate measurements, we cannot improve *x*'s accuracy.

In many practical situations, however, if we have *several*
measurement results corresponding to different values of *t* and/or
*y*, we can reconstruct *x* with a much higher accuracy -
because we can combine these measurement results in such a way that
the influence of *y* drastically decreases. As a result, we get a
*sub-noise* measurement accuracy, the accuracy that is much better than
the accuracy with which we know *y*.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-11, April 2004

Group-Theoretic Approach as a General Framework for Sensors, Neural Networks, Fuzzy Control, and Genetic Boolean Networks

Hung T. Nguyen, Vladik Kreinovich, Chitta Baral, and Valery D. Mazin

Published in *Proceedings of 10th
IMEKO TC7 International Symposium*, Saint-Petersburg,
Russia, June 30-July 2, 2004, Vol. 1, pp. 65-70.

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 approximate description of the real-life gene interaction. In reality, the interaction may be more complex. How can we extend these results to more realistic continuous models of gene interaction?

In this paper, we show that the Post class approach can be viewed as a particular case of a general group-theoretic framework that has already led to a successful justification of empirical formulas from such areas of signal processing as sensor analysis, neural networks, fuzzy techniques, etc. Because of this relation, we suggest group-theoretic approach as a framework for describing gene interaction in a more realistic way.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-10, April 2004

Updated version UTEP-CS-04-10a, April 2005

The Interval Categorizer Tesselation-Based Model for High Perfomance Computing

Marilton S. de Aguiar, Gracaliz P. Dimuro, Antonio C. da R. Costa, Rafael K. S. Silva, and Vladik Kreinovich

Short version published in *Proceedings of the
Workshop on State-of-the-Art in Scientific Computing PARA'04*, Lyngby,
Denmark, June 20-23, 2004; extended version published in
Jack Dongarra, Kaj Madsen, and Jerzy Wasniewski (eds.),
*PARA'04 Workshop on State-of-the-Art in Scientific Computing*,
Springer Lecture Notes in Computer Science,
2006, Vol. 3732, pp. 83-92.

The paper presents the results obtained by an implementation of the interval tessellation-based model for categorization of geographic regions according the analysis of the relief function declivity, called ICTM. The analysis of the relief declivity, which is embedded in the rules of the model ICTM, categorizes each tessellation cell, with respect to the whole considered region, according to the (positive, negative, null) signal of the declivity of the cell. Such information is represented in the states assumed by the cells of the model. The overall configuration of such cells allows the division of the region into sub-regions of cells belonging to the same category, that is, presenting the same declivity signal. In order to control the errors coming from the discretization of the region into tessellation cells, or resulting from numerical computations, interval techniques are used.

Original file in PostScript;

updated file in pdf

Technical Report UTEP-CS-04-09, April 2004

Modelling Measurement Processes as Timed Information Processes in Simplex Domains

G. P. Dimuro, A. C. R. Costa, and V. Kreinovich

Published in *Proceedings of 10th
IMEKO TC7 International Symposium*, Saint-Petersburg,
Russia, June 30-July 2, 2004, Vol. 1, pp. 71-76.

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 process is presented to imllustrate the approach.

Technical Report UTEP-CS-04-08, April 2004

Probabilities, Intervals, What Next? Extension of Interval Computations to Situations with Partial Information about Probabilities

Vladik Kreinovich, Gennady N. Solopchenko, Scott Ferson, Lev Ginzburg, and Richard Alo

Published in *Proceedings of 10th
IMEKO TC7 International Symposium*, Saint-Petersburg,
Russia, June 30-July 2, 2004, Vol. 1, pp. 137-142.

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 for this error; hence, after the measurement, the only information that we have about xi is that it belongs to the interval [xi]=[Xi-Di,Xi+Di]. In this case, it is important to find the range [y] of all possible values of y=f(x1,...,xn) when xi is in [xi].

We start with a brief overview of the
corresponding *interval computation* problems.
We then discuss what to do when, in
addition to the upper bounds Di, we have some partial
information about the probabilities of different values of Dxi.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-07, February 2004

updated version UTEP-CS-04-07a, April 2005

long version UTEP-CS-04-07b, May 2005

On the Use of Intervals in Scientific Computing: What is the Best Transition from Linear to Quadratic Approximation?

Martine Ceberio, Vladik Kreinovich, and Lev Ginzburg

Short version published in *Proceedings of the
Workshop on State-of-the-Art in Scientific Computing PARA'04*, Lyngby,
Denmark, June 20-23, 2004, Vol. 1, pp. 43-49; extended version published in
Jack Dongarra, Kaj Madsen, and Jerzy Wasniewski (eds.),
*PARA'04 Workshop on State-of-the-Art in Scientific Computing*,
Springer Lecture Notes in Computer Science,
2006, Vol. 3732, pp. 75-82.

In many problems from science and engineering, the measurements are reasonably accurate, so we can use linearization (= sensitivity analysis) to describe the effect of measurement errors on the result of data processing. In many practical cases, the measurement accuracy is not so good, so, to get a good estimate of the resulting error, we need to take quadratic terms into consideration - i.e., in effect, approximate the original algorithm by a quadratic function. The problem of estimating the range of a quadratic function is NP-hard, so, in the general case, we can only hope for a good heuristic. Traditional heuristic is similar to straightforward interval computations: we replace each operation with numbers with the corresponding operation of interval arithmetic (or of the arithmetic that takes partial probabilistic information into consideration). Alternatively, we can first diagonalize the quadratic matrix -- and then apply the same approach to the result of diagonalization. Which heuristic is better? We show that sometimes, the traditional heuristic is better; sometimes, the new approach is better; asymptotically, which heuristic is better depends on how fast, when sorted in decreasing order, the eigenvalues decrease.

Original file in Compressed PostScript and
in pdf;

Updated file in Compressed PostScript and
in pdf;

Long version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-06, February 2004

From Intervals to? Towards a General Description of Validated Uncertainty

Vladik Kreinovich, Gracaliz P. Dimuro, and Antonio Carlos da Rocha Costa

Published as a Technical Report of the Catholic University of Pelotas, Brazil, January 2004.

In many real-life situations, we are interested in the physical quantities that are difficult or even impossible to measure directly. To estimate the value of such quantity y, we measure the values of auxiliary quantities x1,...,xn that are related to y by a known functional relation y=f(x1,...,xn), and we then use the results Xi of measuring xi to find the desired estimate Y=f(X1,..,Xn). Due to measurement errors, the measured values Xi are slightly different from the actual (unknown) values xi; as a result, our estimate Y is different from the actual value y=f(x1,...,xn) of the desired quantity.

When xi and y are numbers, then the measurement accuracy can be usually represented in interval terms, and interval computations can be used to estimate the resulting uncertainty in y. In some real-life problems, what we are interested in is more complex than a number. For example, we may be interested in the dependence of the one physical quantity x1 on another one x2: we may be interested in how the material strain depends on the applied stress, or in how the temperature depends on a point in 3-D space; in all such cases, what we are interested in is a function. We may be interested in even more complex structures: e.g., in quantum mechanics, measuring instruments are described by operators in a Hilbert space, so if we want to have a precise description of an actual (imperfect) measuring instrument, what we are interested in is an operator.

For many of such mathematical structures, researchers have developed ways to represent uncertainty, but usually, for each new structure, we have to perform a lot of complex analysis from scratch. It is desirable to come up with a general methodology that would automatically produce a natural description of validated uncertainty for all physically interesting situations (or at least for as many such situations as possible). In this paper, we produce the foundations for such a methodology; it turns out that this problem naturally leads to the technique of domains first introduced by D. Scott in the 1970s.

File in Compressed PostScript and in pdf.

Technical Report UTEP-CS-04-05, February 2004

Geometric Approach to Detecting and Locating Cracks in Thin Plates by Lamb Wave Reflection: Case of Moving Transducer

Jose Rodrigo Mares, Roberto Osegueda, Nagaswaroopa Kaukuri, and Vladik Kreinovich

Published in: Tribikram Kundu (ed.), Health Monitoring and Smart Nondestructive Evaluation of Structural and Biological Systems III, Proceedings of the SPIE/International Society for Optical Engineering, Vol. 5394, San Diego, CA, March 14-18, 2004, pp. 385-398.

This paper portrays work for the development of a Lamb wave scanning method for the detection of defects in thin plates. The approach requires the generation of an ultrasonic A0 and S0-mode Lamb wave using an incident transmitter excited with a tone burst centered at a near non-dispersive frequency. With a fixed relative separation both transmitter and receiving transducer remotely scan a specific line section of the plate. The arrival time information coming from incident and reflected waves contain information associated with the location of reflection surfaces or potential flaws. The Hilbert-Huang transform is applied to the intrinsic mode functions which permit the computation of the signal energy as a function of time, proportional to the square of amplitude of the analytical signal. The arrival times and amplitudes of the notch-reflected energy are used to calculate, by means of two geometric methods, the coordinates of the source of the reflections. The resulting coordinates outline the extent and relative direction of notches in two different scenarios. One is having notches in a 0 to 22.5 degree orientation in respect to the far edge of the plate and two with notches of various sizes at a single rivet hole. Results of experiments conducted on 1.6 mm thick Aluminum square plates, with the arrangement of notches as described, compare favorably with the actual notches.

Technical Report UTEP-CS-04-04, February 2004

Updated version UTEP-CS-04-04a, April 2005

Updated version UTEP-CS-04-04b, May 2005

New Algorithms for Statistical Analysis of Interval Data

Gang Xiang, Scott A. Starks, Vladik Kreinovich, and Luc Longpre

Short version published in *Proceedings of the
Workshop on State-of-the-Art in Scientific Computing PARA'04*, Lyngby,
Denmark, June 20-23, 2004, Vol. 1, pp. 123-129; extended version published in
Jack Dongarra, Kaj Madsen, and Jerzy Wasniewski (eds.),
*PARA'04 Workshop on State-of-the-Art in Scientific Computing*,
Springer Lecture Notes in Computer Science,
2006, Vol. 3732, pp. 189-196.

It is known that in general, statistical analysis of interval data is an NP-hard problem: even computing the variance of interval data is, in general, NP-hard. Until now, only one case was known for which a feasible algorithm can compute the variance of interval data: the case when all the measurements are accurate enough -- so that even after the measurement, we can distinguish between different measured values Xi. In this paper, we describe several new cases in which feasible algorithms are possible -- e.g., the case when all the measurements are done by using the same (not necessarily very accurate) measurement instrument -- or at least a limited number of different measuring instruments.

Original file in Compressed PostScript and
in pdf;

first updated version in Compressed
PostScript andin pdf;

second updated version in Compressed
PostScript andin pdf

Technical Report UTEP-CS-04-03, February 2004

Updated version UTEP-CS-04-03a, April 2004

Interval-Valued and Fuzzy-Valued Random Variables: From Computing Sample Variances to Computing Sample Covariances

Jan B. Beck, Vladik Kreinovich, and Berlin Wu

Published in: M. Lopez, M. A. Gil, P. Grzegorzewski, O. Hrynewicz,
and J. Lawry (eds.), *Soft Methodology and Random Information
Systems*, Springer-Verlag, 2004, pp. 85-92.

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 computes this range [C](x,y) for the case when the measurements are accurate enough -- so that the intervals corresponding to different measurements do not intersect much.

Original file in Compressed PostScript and
in pdf;

updated version in Compressed PostScript and
in pdf.

Technical Report UTEP-CS-04-02, February 2004

Updated version UTEP-CS-04-02a, March 2004

Second revision UTEP-CS-04-02b, May 2008

Final version UTEP-CS-04-02c, July 2008

Toward Formalizing Non-Monotonic Reasoning In Physics: The Use of Kolmogorov Complexity

Vladik Kreinovich

Short version published in: Leonid Sheremetov and Matias Alvarado (eds.),
*Proceedings of the Workshops on Intelligent Computing WIC'04
associated with the Mexican International Conference on Artificial
Intelligence MICAI'04*,
Mexico City, Mexico, April 26-27, 2004, pp. 187-194; a detailed version to
appear in *Revista Iberoamericana de Inteligencia Artificial*

When a physicist writes down equations, or formulates a theory in any other terms, he usually means not only that these equations are true for the real world, but also that the model corresponding to the real world is "typical" among all the solutions of these equations. This type of argument is used when physicists conclude that some property is true by showing that it is true for "almost all" cases. There are formalisms that partially capture this type of reasoning, e.g., techniques based on the Kolmogorov-Martin-Lof definition of a random sequence. The existing formalisms, however, have difficulty formalizing, e.g., the standard physicists' argument that a kettle on a cold stove cannot start boiling by itself, because the probability of this event is too small.

We present a new formalism that can formalize this type of reasoning. This formalism also explains "physical induction" (if some property is true in sufficiently many cases, then it is always true), and many other types of physical reasoning.

Original file in Compressed PostScript and
in pdf;

updated file in Compressed PostScript and
in pdf;

second revision in Compressed PostScript and
in pdf;

final version in Compressed PostScript and
in pdf

Technical Report UTEP-CS-04-01, January 2004

Updated version UTEP-CS-04-01a, May 2004

Fuzzy and Probabilistic Models of Association Information in Sensor Networks

Leon Reznik and Vladik Kreinovich

Published in:
*Proceedings of the International IEEE Conference on
Fuzzy Systems FUZZ-IEEE'2004*, Budapest, Hungary, July 25-29,
2004.

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.

Original file in pdf;

updated version in pdf