Computer Science Department

Abstracts of 2009 Reports

Technical Report UTEP-CS-09-39, December 2009

Updated version UTEP-CS-09-39b, April 2011

Fuzzy Transforms of Higher Order Approximate Derivatives: A Theorem

Irina Perfilieva and Vladik Kreinovich

Published in *Fuzzy Sets and Systems*, 2011, Vol. 180, No.
1, pp. 55-68.

In many practical applications, it is useful to represent a function f(x) by its *fuzzy transform*, i.e., by the "average" values
over different
elements of a *fuzzy partition* A_{1}(x), ..., A_{n}(x) (for
which A_{i}(x) >= 0 and A_{1}(x) + ... + A_{n}(x) = 1). It is known
that when we increase the number n of the partition elements
A_{i}(x), the resulting approximation get closer and closer to the
original function: for each value x_{0}, the values F_{i}
corresponding to the function A_{i}(x) for which A_{i}(x_{0}) > 0 tend to
f(x_{0}).

In some applications, if we approximate the function f(x) on each
element A_{i}(x) not by a *constant* but by a *polynomial*
(i.e., use a fuzzy transform of a *higher order*), we get an
even better approximation to f(x).

In this paper, we show that such fuzzy transforms of higher order
(and even sometimes the original fuzzy transforms) not only
approximate the function f(x) itself, they also approximate its
derivative(s). For example, we have F_{i}'(x_{0}) --> f'(x_{0})$.

Original file in pdf

Updated version pdf

Technical Report UTEP-CS-09-38, December 2009

Discrete Taylor Series as a Simple Way to Predict Properties of Chemical Substances like Benzenes and Cubanes

Jaime Nava, Vladik Kreinovich, Guillermo Restrepo, and Douglas J. Klein

Published in *Journal of Uncertain Systems*, 2010, Vol. 4,
No. 4, pp. 270-290.

In many applications, we have numerous molecules that are obtained from a "template" molecule like benzene C6H6 or cubane C8H8 by replacing some of its hydrogen atoms with other atoms or atom groups (called ligands). Depending on how many original atoms are replaced and which ones are replaced, we obtain a large number of different chemical substances. It is desirable to be able, based on the measurements performed on a small number of such substances, to accurately predict the characteristics (such as energy) of all similar substances.

Such predictions are very important, since, e.g. cubanes, while kinetically stable, are highly explosive. As a result, at present, they are actively used as high-density, high-energy fuels and explosives, and researchers are investigating the potential of using cubanes (and similarly high-energy molecules) in medicine and nanotechnology.

In a 2007 paper in the Journal of Mathematical Chemistry, one of the authors (DJK) showed that accurate predictions can be obtained by using the ideas of the famous MIT mathematician Gian-Carlo Rota on partially ordered sets. In this paper, we show that similar predictions can be made by using much simpler Taylor series techniques.

Technical Report UTEP-CS-09-37, December 2009

Revised version UTEP-CS-09-37a, January 2010

Estimating Information Amount under Uncertainty: Algorithmic Solvability and Computational Complexity

Vladik Kreinovich and Gang Xiang

Published in *International Journal of General Systems*, 2010, Vol. 39, No. 4,
pp. 349-378.

Measurement results (and, more generally, estimates) are never absolutely accurate: there is always an uncertainty, the actual value x is, in general, different from the estimate X. Sometimes, we know the probability of different values of the estimation error dx=X-x, sometimes, we only know the interval of possible values of dx, sometimes, we have interval bounds on the cdf of dx. To compare different measuring instruments, it is desirable to know which of them brings more information - i.e., it is desirable to gauge the amount of information. For probabilistic uncertainty, this amount of information is described by Shannon's entropy; similar measures can be developed for interval and other types of uncertainty. In this paper, we analyze the computational complexity of the problem of estimating information amount under different types of uncertainty.

Original file in pdf

Updated version in pdf

Technical Report UTEP-CS-09-36, December 2009

First updated version UTEP-09-36a, May 2010

Second updated version UTEP-09-36c, July 2010

From Computing Sets of Optima, Pareto Sets, and Sets of Nash Equilibria to General Decision-Related Set Computations

Vladik Kreinovich and Bartlomej Jacek Kubica

Published in *Journal of Universal Computer Science*,
2010, Vol. 16, No. 18, pp. 2657-2685.

Several algorithms have been proposed to compute sets of optima, Pareto sets, sets of Nash equilibria. In this paper, we present a general algorithm for decision-related set computations that includes all these algorithms as particular cases.

To make our algorithm understandable to people working in optimization and in game theory, we also provide motivations and explanations for our formalizations of the corresponding problems and for the related notions of computable mathematics.

Original file in pdf

First updated version in pdf

Second updated version in pdf

Technical Report UTEP-CS-09-35, December 2009

Checking Design Constraints at Run-time Using OCL and AspectJ

Yoonsik Cheon, Carmen Avila, Steve Roach, and Cuauhtemoc Munoz.

Design decisions and constraints of a software system can be specified precisely using a formal notation such as the Object Constraint Language (OCL). However, they are not executable, and assuring the conformance of an implementation to its design is hard. The inability of expressing design constraints in an implementation and checking them at runtime invites, among others, the problem of design drift and corrosion. We propose runtime checks as a solution to mitigate this problem. The key idea of our approach is to translate design constraints written in a formal notation such as OCL into aspects that, when applied to a particular implementation, check the constraints at run-time. Our approach enables runtime verification of design-implementation conformance and detects design corrosion. The approach is modular and plug-and-playable; the constraint checking logic is completely separated from the implementation modules which are oblivious of the former. We believe that a significant portion of constraints translation can be automated.

Technical Report UTEP-CS-09-34, November 2009

Revised version UTEP-CS-09-34b, June 2011

Model Fusion under Probabilistic and Interval Uncertainty, with Application to Earth Sciences

Omar Ochoa, Aaron A. Velasco, Christian Servin, and Vladik Kreinovich

Conference version published in: Michael Beer, Rafi L. Muhanna,
and Robert L. Mullen (Eds.), *Proceedings of the 4th
International Workshop on Reliable Engineering Computing
REC'2010*, Singapore, March 3-5, 2010, pp. 81-100; journal
version published in *International Journal of Reliability
and Safety*, 2012, Vol. 6, No. 1-3, pp. 167-187.

One of the most important studies of the earth sciences is that of the Earth's interior structure. There are many sources of data for Earth tomography models: first-arrival passive seismic data (from the actual earthquakes), first-arrival active seismic data (from the seismic experiments), gravity data, and surface waves. Currently, each of these datasets is processed separately, resulting in several different Earth models that have specific coverage areas, different spatial resolutions and varying degrees of accuracy. These models often provide complimentary geophysical information on earth structure (P and S wave velocity structure).

Combining the information derived from each requires a joint inversion approach. Designing such joint inversion techniques presents an important theoretical and practical challenge. While such joint inversion methods are being developed, as a first step, we propose a practical solution: to fuse the Earth models coming from different datasets. Since these Earth models have different areas of coverage, model fusion is especially important because some of the resulting models provide better accuracy and/or spatial resolution in some spatial areas and in some depths while other models provide a better accuracy and/or spatial resolution in other areas or depths.

The models used in this paper contain measurements that have not only different accuracy and coverage, but also different spatial resolution. We describe how to fuse such models under interval and probabilistic uncertainty.

The resulting techniques can be used in other situations when we need to merge models of different accuracy and spatial resolution.

Original file in pdf

updated version in pdf

Technical Report UTEP-CS-09-33, September 2009

Revised version UTEP-CS-09-33a, April 2010

How to Relate Spectral Risk Measures and Utilities

Songsak Sriboonchitta, Hung T. Nguyen, and Vladik Kreinovich

Short version published in *Proceedings of the Third Conference
of Thailand Econometric Society*, Chiang Mai, Thailand,
January 7-8, 2010, pp. 8-19; detailed version published in
*International Journal of Intelligent Technologies and Applied
Statistics*, 2010, Vol. 3, No. 2, pp. 141-158.

Traditional decision theory describes human behavior and human preferences in terms of utility functions. In the last decades, it was shown that in many economic situations, a reasonable description of the actual decisions can be found if we use a different approach -- of spectral risk measures. In each of these approaches, we first need to empirically find the corresponding function: utility function in the traditional approach and the weighting function for spectral risk measures. Since both approaches provide a reasonable description of the same actual behavior (in particular, of the same actual economic behavior), it is desirable to be able, given utility function, to find an appropriate weighting function (and vice versa). Some empirical rules for such transition have been proposed; these rules are purely heuristic and approximate, they are not theoretically justified. In the present paper, we recall how both the utility and the risk measure approaches can be reformulated in statistical terms, and use these reformulations to provide a statistically justified transition between utility and weighting functions.

Original file in pdf;

updated file in pdf

Technical Report UTEP-CS-09-32, October 2009

Automating Java Program Testing Using OCL and AspectJ

Yoonsik Cheon and Carmen Avila

Random testing can eliminate subjectiveness in constructing test data and increase the diversity of test data. However, one difficult problem is to construct test oracles that decide test results---test failures or successes. Assertions can be used as test oracles and are most effective when derived from formal specifications such as OCL constraints. If fully automated, random testing can reduce the cost of testing dramatically. In this paper we propose an approach for automating Java program testing by combining random testing and OCL. The key idea of our approach is to use OCL constraints as test oracles by translating them to runtime checks written in AspectJ. We realize our approach by adapting existing frameworks for translating OCL to AspectJ and assertion-based random testing. We evaluate the effectiveness of our approach through case studies and experiments. Our approach can detect errors in both implementations and OCL constraints and provide a practical means for using OCL in design and programming.

File in PDF and in Compressed Postscript

Technical Report UTEP-CS-09-31, September 2009

Revised version UTEP-CS-09-31a, December 2009

Symmetries: A General Approach to Integrated Uncertainty Management

Vladik Kreinovich, Hung T. Nguyen, and Songsak Sriboonchitta

Published in: Van-Nam Huynh et al. (eds.), *Integrated Uncertainty Management and
Applications*, Springer-Verlag, Berlin, Heidelberg, 2010, Vol. AISC 68, pp. 141-152.

We propose to use symmetries as a general approach to maintaining different types of uncertainty, and we show how the symmetry approach can help, especially in in economics-related applications.

Original file UTEP-CS-09-31 in pdf

revised version UTEP-CS-09-31a in pdf

Technical Report UTEP-CS-09-30ab, July 2011

Scale-Invariant Approach to Multi-Criterion Optimization under Uncertainty, with Applications to Optimal Sensor Placement, in Particular, to Sensor Placement in Environmental Research

Aline Jaimes, Craig Tweedy, Vladik Kreinovich, and Martine Ceberio

Published in *International Journal of Reliability and
Safety*, 2012, Vol. 6, No. 1-3, pp. 188-203.

Technical Report UTEP-CS-09-30a, December 2009

Optimal Sensor Placement in Environmental Research: Designing a Sensor Network under Uncertainty

Aline Jaimes, Craig Tweedy, Tanja Magoc, Vladik Kreinovich, and Martine Ceberio

Published in: Michael Beer, Rafi L. Muhanna, and
Robert L. Mullen (Eds.), *Proceedings of the 4th International
Workshop on Reliable Engineering Computing REC'2010*,
Singapore, March 3-5, 2010, pp. 255-267.

One of our main challenges in meteorology and environment research is that in many important remote areas, sensor coverage is sparse, leaving us with numerous blind spots. Placement and maintenance of sensors in these areas are expensive. It is therefore desirable to find out how, within a given budget, we can design a sensor network are important activities was developing reasonable techniques for sensor that would provide us with the largest amount of useful information while minimizing the size of the "blind spot" areas which is not covered by the sensors.

This problem is very difficult even to formulate in precise terms because of the huge uncertainty. There are two important aspects of this problem: (1) how to best distribute the sensors over the large area, and (2) what is the best location of each sensor in the corresponding zone. There is some research on the first aspect of the problem.

In this paper, we illustrate the second aspect of the problem, on the example of optimal selection of locations for the Eddy towers, an important micrometeorological instrument.

Technical Report UTEP-CS-09-30, September 2009

First updated version UTEP-09-30c, January 2010

Second updated version UTEP-09-30d, April 2010

Selecting the Best Location for a Meteorological Tower: A Case Study of Multi-Objective Constraint Optimization

Aline Jaimes, Craig Tweedy, Tanja Magoc, Vladik Kreinovich, and Martine Ceberio

Short version published in: Martine Ceberio (ed.), *Abstracts of
the Second Workshop on Constraint Programming and Decision Making
CoProD'09*, El Paso, Texas, November 9-10, 2009, pp. 56-60; a
more detailed versions published in *Proceedings of the IEEE
World Congress on Computational Intelligence WCCI'2010*,
Barcelona, Spain, July 18-23, 2010, pp. 2355-2361, *Journal of
Uncertain Systems*, 2010, Vol. 4, No. 4, pp. 261-269, and in:
Martine Ceberio and Vladik Kreinovich (eds.), *Constraint
Programming and Decision Making*, Springer Verlag, Berlin,
Heidelberg, 2014, pp. 61-66.

Using the problem of selecting the best location for a meteorological tower as an example, we show that in multi-objective optimization under constraints, the traditional weighted average approach is often inadequate. We also show that natural invariance requirements lead to a more adequate approach -- a generalization of Nash's bargaining solution.

Original file in pdf

First updated version in pdf

Second updated version in pdf

Technical Report UTEP-CS-09-29b, April 2010

Why Polynomial Formulas in Soft Computing, Decision Making, etc.?

Olga Kosheleva, Martine Ceberio, and Vladik Kreinovich

Published in *Proceedings of the World Congress on
Computational Intelligence*,
Barcelona, Spain, July 18-23, 2010, pp. 3310-3314.

We show that in many application areas including soft constraints reasonable requirements of scale-invariance lead to polynomial formulas for combining degrees (of certainty, of preference, etc.)

Technical Report UTEP-CS-09-29, September 2009

Why Tensors?

Olga Kosheleva, Martine Ceberio, and Vladik Kreinovich

Preliminary version published in: Martine Ceberio (ed.), *Abstracts of the Second Workshop on
Constraint Programming and Decision Making CoProD'09*, El Paso,
Texas, November 9-10, 2009, pp. 20-23; final version published in:
Martine Ceberio and Vladik Kreinovich (eds.), *Constraint
Programming and Decision Making*, Springer Verlag, Berlin,
Heidelberg, 2014, pp. 75-78.

We show that in many application areas including soft constraints reasonable requirements of scale-invariance lead to polynomial (tensor-based) formulas for combining degrees (of certainty, of preference, etc.)

Technical Report UTEP-CS-09-28, September 2009

Continuous If-Then Statements Are Computable

Martine Ceberio and Vladik Kreinovich

Preliminary version published in: Martine Ceberio (ed.), *Abstracts of the Second Workshop on
Constraint Programming and Decision Making CoProD'09*, El Paso, Texas,
November 9-10, 2009, pp. 11-14; final version published in:
Martine Ceberio and Vladik Kreinovich (eds.), *Constraint
Programming and Decision Making*, Springer Verlag, Berlin,
Heidelberg, 2014, pp. 15-18.

.

In many practical situations, we must compute the value of an if-then expression
f(x) defined as "if c(x) >= 0 then f_{+}(x) else f_{-}(x)", where
f_{+}(x), f_{-}(x), and c(x) are computable functions. The value
f(x) cannot be computed directly,
since in general, it is not possible to check whether a given real number c(x)
is non-negative or non-positive. Similarly, it is not possible to compute the
value f(x) if the if-then function is discontinuous, i.e., when
f_{+}(x_{0}) =/= f_{-}(x_{0})
for some x_{0} for which c(x_{0}) = 0.

In this paper, we show that if the if-then expression is continuous, then we can effectively compute f(x).

Technical Report UTEP-CS-09-27, August 2009

"Weird" Fuzzy Notations: An Algebraic Interpretation

Vladik Kreinovich

Published in *Applied Mathematical Sciences*, 2010, Vol. 4, pp. 431-434.

Traditionally, fuzzy logic used non-standard notations like
m_{1}/x_{1} + ... + m_{n}/x_{n}
for a function that attains the value m_{1} at x_{1}, ..., and
the value m_{n} at x_{n}. In this paper, we provide an algebraic
explanation for these notations.

Technical Report UTEP-CS-09-26, August 2009

Diagonalization is Also Practically Useful: A Geometric Idea

Martine Ceberio and Vladik Kreinovich

Published in *Geombinatorics*, 2010,
Vol. 20, No. 1, pp. 15-20.

Technical Report UTEP-CS-09-25, August 2009

Symmetry Between True, False, and Uncertain: An Explanation

Eulalia Szmidt and Vladik Kreinovich

Published in *Notes on Intuitionistic Fuzzy Sets*, 2009,
Vol. 15, No. 4, pp. 1-8.

In intuitionistic fuzzy sets, there is a natural symmetry between degrees of truth and falsity. As a result, for such sets, natural similarity measures are symmetric relative to an exchange of true and false values. It has been recently shown that among such measures, the most intuitively reasonable are the ones which are also symmetric relative to an arbitrary permutation of degrees of truth, falsity, and uncertainty. This intuitive reasonableness leads to a conjecture that such permutations are not simply mathematical constructions, that these permutations also have some intuitive sense. In this paper, we show that each such permutation can indeed be represented as a composition of intuitively reasonable operations on truth values.

Technical Report UTEP-CS-09-24, August 2009

On the Use of Abstract Workflows to Capture Scientific Process Provenance

Paulo Pinheiro da Silva, Leonardo Salayandia, Nicholas Del Rio, Ann Q. Gates

Capturing provenance about artifacts produced by distributed scientific processes is a challenging task. For example, one approach to facilitate the execution of a scientific process in distributed environments is to break down the process into components and to create workflow specifications to orchestrate the execution of these components. However, capturing provenance in such an environment, even with the guidance of orchestration logic, is difficult because of important details that may be hidden by the component abstractions. In this paper, we show how to use abstract workflows to systematically enhance scientific processes to capture provenance at appropriate levels of detail. Abstract workflows lack the specification of an orchestration logic to execute a scientific process, and instead, are intended to document scientific processes as understood by scientists. Hence, abstract workflows can be specifically designed to capture the details of scientific processes that are relevant to the scientist with respect to provenance. In addition, abstract workflows are coupled with a representation of provenance that can accommodate distributed provenance-generating source code. We also show how the approach described in this paper has been used for capturing provenance for scientific processes in the Earth science, environmental science and solar physics domains.

Technical Report UTEP-CS-09-23, July 2009

Revised version UTEP-CS-09-23a, September 2009

Astronomical Tests of Relativity: Beyond Parameterized Post-Newtonian Formalism (PPN), to Testing Fundamental Principles

Vladik Kreinovich

Published in: Sergei Klioner, P. Ken Seidelmann, and
Michael H. Soffel (eds.), *Relativity in Fundamental Astronomy,
Proceedings of IAU Symposium No. 261*, Cambridge University Press,
Cambridge, UK, 2009, pp. 56-61.

By the early 1970s, the improved accuracy of astrometric and time measurements enabled researchers not only to experimentally compare relativistic gravity with the Newtonian predictions, but also to compare different relativistic gravitational theories (e.g., the Brans-Dicke Scalar-Tensor Theory of Gravitation). For this comparison, Kip Thorne and others developed the Parameterized Post-Newtonian Formalism (PPN), and derived the dependence of different astronomically observable effects on the values of the corresponding parameters.

Since then, all the observations have confirmed General Relativity. In other words, the question of which relativistic gravitation theory is in the best accordance with the experiments has been largely settled. This does not mean that General Relativity is the final theory of gravitation: it needs to be reconciled with quantum physics (into quantum gravity), it may also need to be reconciled with numerous surprising cosmological observations, etc. It is therefore reasonable to prepare an extended version of the PPN formalism, that will enable us to test possible quantum-related modifications of General Relativity.

In particular, we need to include the possibility of violating fundamental principles that underlie the PPN formalism but that may be violated in quantum physics, such as scale-invariance, T-invariance, P-invariance, energy conservation, spatial isotropy violations, etc. In this paper, we present the first attempt to design the corresponding extended PPN formalism, with the (partial) analysis of the relation between the corresponding fundamental physical principles.

Original file in pdf,

Updated version in pdf

Technical Report UTEP-CS-09-22, July 2009

A Note on the Expected Depth of a Leaf in a PATRICIA Trie

Luc Longpre

Technical Report UTEP-CS-09-21, July 2009

Updated version UTEP-CS-09-21b, May 2010

Metrization Theorem for Space-Times: From Urysohn's Problem Towards Physically Useful Constructive Mathematics

Vladik Kreinovich

Published in: Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig (eds.), Fields of Logic and Computation, Lecture Notes in Computer Science, Vol. 6300, Springer-Verlag, Berlin, 2010, pp. 470-487.

In the early 1920s, Pavel Urysohn proved his famous lemma (sometimes referred to as "first non-trivial result of point set topology"). Among other applications, this lemma was instrumental in proving that under reasonable conditions, every topological space can be metrized.

A few years before that, in 1919, a complex mathematical theory was experimentally proven to be extremely useful in the description of real world phenomena: namely, during a solar eclipse, General Relativity theory -- that uses pseudo-Riemann spaces to describe space-time -- has been (spectacularly) experimentally confirmed. Motivated by this success, Urysohn started working on an extension of his lemma and of the metrization theorem to (causality-)ordered topological spaces and corresponding pseudo-metrics. After Urysohn's early death in 1924, this activity was continued in Russia by his student Vadim Efremovich, Efremovich's student Revolt Pimenov, and by Pimenov's students (and also by H. Busemann in the US and by E. Kronheimer and R. Penrose in the UK). By the 1970s, reasonably general space-time versions of Urysohn's lemma and metrization theorem have been proven.

However, these 1970s results are not constructive. Since one of the main objectives of this activity is to come up with useful applications to physics, we definitely need constructive versions of these theorems -- versions in which we not only claim the theoretical existence of a pseudo-metric, but we also provide an algorithm enabling the physicist to generate such a metric based on empirical data about the causality relation. An additional difficulty here is that for this algorithm to be useful, we need a physically relevant constructive description of a causality-type ordering relation.

In this paper, we propose such a description and show that for this description, a combination of the existing constructive ideas with the known (non-constructive) proof leads to successful constructive space-time versions of the Urysohn's lemma and of the metrization theorem.

Original file in pdf

updated version in pdf

Technical Report UTEP-CS-09-20, June 2009

Revised version UTEP-CS-09-20a, June 2012

Equations Without Equations: Challenges on a Way to a More Adequate Formalization of Causality Reasoning in Physics

Roberto Araiza, Vladik Kreinovich, and Juan Ferret

Published in *Proceedings of the Workshop on Informatics and
Information
Technologies in Education: Theory, Applications, Didactics*,
Novosibirsk, Russia, September 26-29, 2012, Vol. 1, pp.
7-19.

Not all mathematical solutions to physical equations are physically meaningful: e.g., if we reverse all the molecular velocities in a breaking cup, we get pieces self-assembling into a cup. The resulting initial conditions are "degenerate": once we modify them, self-assembly stops. So, in a physical solution, the initial conditions must be "non-degenerate".

A challenge in formalizing this idea is that it depends on the representation. Example 1: we can use the Schroedinger equation to represent the potential field V(x)=F(f,...) as a function of the wave function f(x,t) and its derivatives. The new equation dF/dt=0 is equivalent to the Schroedinger equation, but now V(x) is in the initial conditions.

Example 2: for a general scalar field f, we describe a new equation which is satisfied if f satisfies the Euler-Lagrange equations for some Lagrangian L. So, similarly to Wheeler's cosmological "mass without mass", we have "equations without equations".

Thus, when formalizing physical equations,
we must not only describe them in *a* mathematical form,
we must also select *one*
of the mathematically equivalent forms.

Original file in pdf

Updated version in pdf

Technical Report UTEP-CS-09-19, June 2009

Looking for Entropy Rate Constancy in Spoken Dialog

Alejandro Vega and Nigel G. Ward

The entropy constancy principle describes the tendency for information in language to be conveyed at a constant rate. We explore the possible role of this principle in spoken dialog, using the ``summed entropy rate,'' that is, the sum of the entropies of the words of both speakers per second of time. Using the Switchboard corpus of casual dialogs and a standard ngram language model to estimate entropy, we examine patterns in entropy rate over time and the distribution of entropy across the two speakers. The results show effects that can be taken as support for the principle of constant entropy, but also indicate a need for better language models and better techniques for estimating non-lexical entropy.

Technical Report UTEP-CS-09-18, June 2009

Measurement's result and its error as fuzzy variables: background and perspectives

Gennady N. Solopchenko, Konstantin K. Semenov, Vladik Kreinovich, and Leon Reznik

Short version published in the *Proceedings of the 9th International Symposium on
Measurement Technology and Intelligent Instruments
ISMTII'2009*, St. Petersburg, Russia, June 28 - July 2, 2009, pp. 4-132 -
4-136; full version published in *Key Engineering Materials*,
2010, Vol. 437, pp. 487-491.

The possibility of using fuzzy variables for describing measurands and their error characteristics is investigated. The elementary arithmetic operations within the limits of such representation are considered.

Technical Report UTEP-CS-09-17, June 2009

First updated version UTEP-CS-09-17d, May 2011

Second updated version UTEP-CS-09-17e, June 2011

Towards an (Even More) Natural Probabilistic Interpretation of Fuzzy Transforms (and of Fuzzy Modeling)

Irina Perfilieva and Vladik Kreinovich

Published in *Advances in Fuzzy Systems*, Vol. 2011,
Article ID 719256, doi:10.1155/2011/719256.

In many practical applications, it turns out to be useful to use the
notion of fuzzy transform: once we have non-negative
functions A_{1}(x), ...,
A_{n}(x), with A_{1}(x) + ... +
A_{n}(x) = 1, we can
then represent each function f(x) by the coefficients
F_{i} which are defined as the ratio of two integrals: of
f(x) * A_{i}(x) and of A_{i}(x).
Once we know the coefficients F_{i}, we can
(approximately) reconstruct the original function f(x) as
F_{1} * A_{1}(x) + ... +
F_{n} * A_{n}(x).
The original motivation for
this transformation came from fuzzy modeling, but the transformation
itself is a purely mathematical transformation. Thus, the empirical
successes of this transformation suggest that this transformation
can be also interpreted in more traditional (non-fuzzy) mathematics
as well.

Such an interpretation is presented in this paper. Specifically, we show that the 2002 probabilistic interpretation of fuzzy modeling by Sanchez et al. can be modified into a natural probabilistic explanation of fuzzy transform formulas.

Original file in pdf and
in Compressed Postscript;

first updated version in pdf;

second updated version in pdf

Technical Report UTEP-CS-09-16a, May 2009

Final version UTEP-CS-09-16b, November 2009

A Broad Prospective on Fuzzy Transforms: From Gauging Accuracy of Quantity Estimates to Gauging Accuracy and Resolution of Measuring Physical Fields

Vladik Kreinovich and Irina Perfilieva

A short version was published in *Abstracts of the 10th International
Student Conference on Applied Mathematics and Informatics ISCAMI*, Malenovice,
Czech Republic, May 13-15, 2009; full paper published in
*Neural Network World*, 2010, Vol. 20, No. 1, pp. 7-25.

Fuzzy transform is a new type of function transforms that has been
successfully used in different application. In this paper, we
provide a broad prospective on fuzzy transform. Specifically, we
show that fuzzy transform naturally appears when, in addition to
*measurement* uncertainty, we also encounter another type of
*localization* uncertainty: that the measured value may come not
only from the desired location *x*, but also from the nearby
locations.

Original file in pdf

updated version in pdf

Technical Report UTEP-CS-09-16, May 2009

Revised version UTEP-CS-09-16c, November 2009

From Gauging Accuracy of Quantity Estimates to Gauging Accuracy and Resolution of Measuring Physical Fields

Vladik Kreinovich and Irina Perfilieva

Published in Roman Wyrzykowski, Jack Dongarra,
Konrad Kzrczewski, and Jerzy Wasniewski (eds.),
*Proceedings of the Eighth International Conference on Parallel
Processing and Applied Mathematics PPAM'2009*, Wroclaw, Poland,
September 13-16, 2009, Springer Lecture Notes in Computer
Science, 2010, Vol. 6608, pp. 456-465.

For a numerical physical quantity v, because of the measurement imprecision, the measurement result V is, in general, different from the actual value v of this quantity. Depending on what we know about the measurement uncertainty d = V - v, we can use different techniques for dealing with this imprecision: probabilistic, interval, etc.

When we measure the values v(x) of physical fields at different locations x (and/or different moments of time), then, in addition to the same measurement uncertainty, we also encounter another type of localization uncertainty: that the measured value may come not only from the desired location x, but also from the nearby locations.

In this paper, we discuss how to handle this additional uncertainty.

Original file in pdf and
in Compressed Postscript;

revised version in pdf.

Technical Report UTEP-CS-09-15, May 2009

Towards Dynamical Systems Approach to Fuzzy Clustering

Vladik Kreinovich and Olga Kosheleva

Published in: Dmitri A. Viattchenin (ed.), *Developments in Fuzzy
Clustering*, Vever Publ., Minsk, Belarus, 2009, pp. 10-35.

In many application areas, there is a need for clustering, and there is a need to take fuzzy uncertainty into account when clustering. Most existing fuzzy clustering techniques are based on the idea that an object belongs to a certain cluster if this object is close to a typical object from this cluster. In some application areas, however, this idea does not work well. One example of such application is clustering in education that is used to convert a detailed number grade into a letter grade.

In such application, it is more appropriate to use clustering techniques which are based on a different idea: that an object tends to belong to the same cluster as its nearest neighbor. In this paper, we explain the relationship between this idea and dynamical systems, and we discuss how fuzzy uncertainty can be taken into account in this approach to clustering.

File in pdf and in Compressed Postscript

Technical Report UTEP-CS-09-14, May 2009

Analysis of Information and Computation in Physics Explains Cognitive Paradigms: from Full Cognition to Laplace Determinism to Statistical Determinism to Modern Approach

Vladik Kreinovich, Roberto Araiza, and Juan Ferret

To appear in: Gordana Dodig-Crnkovic and Mark Burgin (eds.),
*Information and Computation*, World Scientific, Singapore,
2011, pp. 203-223.

In this paper, we analyze the problem of prediction in physics from the computational viewpoint. We show that physical paradigms like Laplace determinism, statistical determinism, etc., can be naturally explained by this computational analysis. In our explanations, we use the notions of the Algorithmic Information Theory such as Kolmogorov complexity and algorithmic randomness, as well as the novel, more physics-oriented variants of these notions.

File in pdf and in Compressed Postscript

Technical Report UTEP-CS-09-13, May 2009

Preliminary Assessment of Attitudes towards Mathematics for a Non-STEM Section of Computational Computer Science Zero

Milijana Suskavcevic, Olga Kosheleva, Ann Gates, and Eric Freudenthal

Technical Report UTEP-CS-09-12, March 2009

Experiments in teaching an engaging and demystifying introduction to algorithms: Installment 1: Huffman Codes

Alan Siegel and Eric Freudenthal

As is well known -- the Huffman algorithm is a remarkably simple, and is a wonderfully illustrative example of the greedy method in algorithm design. However, the Huffman problem, which is to design an optimal binary character code (or an optimal binary tree with weighted leaves) is intrinsically technical, and its specification is ill-suited for students with modest mathematical sophistication.

This difficulty is circumvented by introducing an alternative 'precursor' problem that is easy to understand, and where this understanding can lead to student-devised solutions: how to merge k sorted lists of varying length together as efficiently as possible. Once students have solved this problem, they are better prepared to understand Huffman problem can be trivially reduced to it, and thus and why their merging algorithm solves it. Even the correctness argument is simplified by this approach.

Technical Report UTEP-CS-09-11, March 2009

Stochastic Volatility Models and Financial Risk Measures: Towards New Justifications

Hung T. Nguyen, Vladik Kreinovich, and Songsak Sriboonchitta

Published in the *Proceedings of the 2009 Singapore
Economic Review Conference*, Singapore, August 6-8, 2009.

We provide theoretical justifications for the empirical successes of (1) the asymmetric heteroskedasticity models of stochastic volatility in mathematical finance and (2) Wang's distorted probability risk measures in actuarial and investment sciences, using a unified framework of symmetry groups.

File in pdf and in Compressed Postscript

Technical Report UTEP-CS-09-10, March 2009

Guesstimation: A New Justification of the Geometric Mean Heuristic

Olga Kosheleva and Vladik Kreinovich

Published in *Applied Mathematical Sciences*, 2009, Vol. 3, No. 47,
pp. 2335-2342.

In many practical situations in which the only information we have about the quantity x is that its value is within an interval [x,X], a reasonable estimate for this quantity is the geometric mean of the bounds, i.e., the square root of the product x*X. In this paper, we provide a new justification for this geometric mean heuristic.

File in pdf and in Compressed Postscript

Technical Report UTEP-CS-09-09, March 2009

Propitious Checkpoint Intervals to Improve System Performance

Sarala Arunagiri, John T. Daly, and Patricia J. Teller

The large scale of current and next-generation massively parallel processing (MPP) systems presents significant challenges related to fault tolerance. For applications that perform periodic checkpointing, the choice of the checkpoint interval, the period between checkpoints, can have a significant impact on the execution time of the application and the number of checkpoint I/O operations performed by the application. These two metrics determine the frequency of checkpoint I/O operations performed by the application, and thereby, the contribution of the checkpoint operations to the I/O bandwidth demand made by the application. In a computing environment where there are concurrent applications competing for access to the network and storage resources, the I/O demand of each application is a crucial factor in determining the throughput of the system. Thus, in order to achieve a good overall system throughput, it is important for the application programmer to choose a checkpoint interval that balances the two opposing metrics - the number of checkpoint I/O operations and the application execution time. Finding the optimal checkpoint interval that minimizes the wall clock execution time, has been a subject of research over the last decade. In this paper, we present a simple, elegant, and accurate analytical model of a complementary performance metric - the aggregate number of checkpoint I/O operations. We model this and present the optimal checkpoint interval that minimizes the total number of checkpoint I/O operations. We present extensive simulation studies that validate our analytical model. Insights provided by this model, combined with existing models for wall clock execution time, facilitate application programmers in making a well informed choice of checkpoint interval leading to an appropriate trade off between execution time and number of checkpoint I/O operations. We illustrate the existence of such propitious checkpoint intervals using parameters of four MPP systems, SNL's Red Storm, ORNL's Jaguar, LLNL's Blue Gene/L (BG/L), and a theoretical Petaflop system.

Technical Report UTEP-CS-09-08, February 2009

A New Justification of Wang Transform Operator in Financial Risk Analysis

Vladik Kreinovich, Hung T. Nguyen, and Songsak Sriboonchitta

To appear in *International Journal of Intelligent Technologies and Applied
Statistics*

One of the most widely used (and most successful) methods for pricing financial and insurance instruments under risk is the Wang transform method. In this paper, we provide a new explanation for the empirical success of Wang's method -- by providing a new simpler justification for the Wang transform.

File in pdf and in Compressed Postscript

Technical Report UTEP-CS-09-07, January 2009

Updated version UTEP-CS-09-07a

Towards Neural-Based Understanding of the Cauchy Deviate Method for Processing Interval and Fuzzy Uncertainty

Vladik Kreinovich and Hung T. Nguyen

Published in *Proceedings of the 2009 World Congress of the International
Fuzzy Systems
Association IFSA*, Lisbon, Portugal, July 20-24, 2009, pp. 1264-1269.

One of the most efficient techniques for processing interval and fuzzy data is a Monte-Carlo type technique of Cauchy deviates that uses Cauchy distributions. This technique is mathematically valid, but somewhat counterintuitive. In this paper, following the ideas of Paul Werbos, we provide a natural neural network explanation for this technique.

Original file in pdf and
in Compressed Postscript

Updated version in pdf and
in Compressed Postscript

Technical Report UTEP-CS-09-06, January 2009

Quantum Computing as a Particular Case of Computing With Tensors

Martine Ceberio and Vladik Kreinovich

One of the main potential applications of uncertainty in computations is quantum computing. In this paper, we show that the success of quantum computing can be explained by the fact that quantum states are, in effect, tensors.

File in pdf and in Compressed Postscript

Technical Report UTEP-CS-09-05c, December 2009

Updated version UTEP-CS-09-05cb, July 2011

Towards Optimal Effort Distribution in Process Design under Uncertainty, with Application to Education

Olga Kosheleva and Vladik Kreinovich

Conference version published in: Michael Beer, Rafi L. Muhanna, and
Robert L. Mullen (Eds.), *Proceedings of the 4th International
Workshop on Reliable
Engineering Computing REC'2010*, Singapore, March 3-5, 2010,
pp. 509-525; journal version published in
*International Journal of Reliability and Safety*, 2012,
Vol. 6, No. 1-3, pp. 148-166.

In most application areas, we need to take care of several (reasonably independent) participants. For example, in controlling economics, we must make sure that all the economic regions prosper. In controlling environment, we want to guarantee that all the geographic regions have healthy environment. In education, we want to make sure that all the students learn all the needed knowledge and skills.

In real life, the amount of resources is limited, so we face the problem of "optimally" distributing these resources between different objects.

What is a reasonable way to formalize "optimally"? For each of the participants,
preferences can be described by *utility functions*: namely, an action is
better if its expected utility is larger. It is natural to require that the
resulting group preference has the following property: if two actions has the
same quality for all participants, then they are equivalent for the group as
well. It turns out that under this requirement, the utility function of a
group is a linear combination of individual utility functions.

To solve the resulting optimization problem, we need to know, for each participant, the utility resulting from investing effort in this participant. In practice, we only know this value with (interval) uncertainty. So, for each distribution of efforts, instead of a single value of the group utility, we only have an interval of possible values. To compare such intervals, we use Hurwicz optimism-pessimism criterion well justified in decision making.

In the talk, we propose a solution to the resulting optimization problem.

Original file in pdf

Updated version in pdf

Technical Report UTEP-CS-09-05, January 2009

Updated version UTEP-CS-09-05a, April 2009

What is the Best Way to Distribute Efforts Among Students: Towards Quantitative Approach to Human Cognition

Olga Kosheleva and Vladik Kreinovich

Short version published in the *Proceedings of the 28th North
American Fuzzy Information Processing Society Annual Conference
NAFIPS'09*, Cincinnati, Ohio, June 14-17, 2009; full version
published in *Applied Mathematical Sciences*, 2010, Vol.
4, No. 9, pp. 417-429.

In a typical class, we have students at different levels of knowledge, student with different ability to learn the material. In the ideal world, we should devote unlimited individual attention to all the students and make sure that everyone learns all the material. In real life, our resources are finite. Based on this finite amount of resources, what is the best way to distribute efforts between different students?

Even when we know the exact way each student learns, the answer depends on what is the objective of teaching the class. This can be illustrated on two extreme example: If the objective is to leave no student behind, then in the optimal resource arrangement all the effort goes to weak students who are behind, while more advanced students get bored. If the effort is to increase the school's rating by increasing the number of graduates who are accepted at top universities, then all the effort should go to the advanced students while weak students fail.

An additional difficulty is that in reality, we do not have exact information about the cognitive ability of each student, there is a large amount of uncertainty. In this talk, we analyze the problem of optimal resource distribution under uncertainty.

Original file in pdf and
in Compressed Postscript

Updated version in pdf and
in Compressed Postscript

Technical Report UTEP-CS-09-04, January 2009

Updated version UTEP-CS-09-04a, March 2009

Empirical Formulas for Economic Fluctuations: Towards A New Justification

Tanja Magoc and Vladik Kreinovich

Published in the *Proceedings of
the 28th North American
Fuzzy Information Processing Society Annual Conference NAFIPS'09*,
Cincinnati, Ohio, June 14-17, 2009.

To avoid crisis developments, it is important to make financial decisions based on the models which correct predict the probabilities of large-scale economic fluctuations. At present, however, most financial decisions are based on Gaussian random-walk models, models which are known to underestimate the probability of such fluctuations. There exist better empirical models for describing these probabilities, but economists are reluctant to use them since these empirical models lack convincing theoretical explanations. To enhance financial stability and avoid crisis situations, it is therefore important to provide theoretical justification for these (more) accurate empirical models. Such a justification is provided in this paper.

Original file in pdf and
in Compressed Postscript

Updated version in pdf and
in Compressed Postscript

Technical Report UTEP-CS-09-03b, June 2009

Engineering Design under Imprecise Probabilities: Computational Complexity

Vladik Kreinovich

To appear in *Cubo, A Mathematical Journal*, 2011, Vol.
13, No. 1, pp. 103-123.

Technical Report UTEP-CS-09-03, January 2009

Updated version UTEP-CS-09-03a, April 2009

Expert Knowledge Is Needed for Design under Uncertainty: For p-Boxes, Backcalculation is, in General, NP-Hard

Vladik Kreinovich

Published in the *Proceedings of
the 28th North American
Fuzzy Information Processing Society Annual Conference NAFIPS'09*,
Cincinnati, Ohio, June 14-17, 2009.

In engineering design problems, we want to make sure that a certain
quantity c of the designed system lies within given bounds -- or
at least that the probability of this quantity to be outside these
bounds does not exceed a given threshold. We may have several such
requirements -- thus the requirement can be formulated as bounds
on the cumulative
distribution function F(x) of the quantity c; such bounds are
known as a *p-box*.

The value of the desired quantity c depends on the design
parameters a and the parameters b characterizing the
environment: c=f(a,b). To achieve the design goal, we need to find
the design parameters a for which the distribution F(x) for
c=f(a,b) is within the given bounds for all possible values of the
environmental variables b. The problem of computing such $a$ is
called *backcalculation*. For b, we also have ranges with
different probabilities -- i.e., also a p-box. Thus, we have
backcalculation problem for p-boxes.

For p-boxes, there exist efficient algorithms for finding a design $a$ that satisfies the given constraints. The next natural question is to find a design that satisfies additional constraints: on the cost, on the efficiency, etc. In this paper, we prove that that without expert knowledge, the problem of finding such a design is computationally difficult (NP-hard). We show that this problem is NP-hard already in the simplest possible linearized case, when the dependence c=f(a,b) is linear. Thus, expert (fuzzy) knowledge is needed to solve design problems under uncertainty.

Updated version in pdf and
in Compressed Postscript

Technical Report UTEP-CS-09-02, January 2009

Asymmetric Heteroskedasticity Models: A New Justification

Songsak Sriboonchitta and Vladik Kreinovich

To appear in *International Journal of Intelligent Technologies and Applied
Statistics*

Most existing econometric models such as ARCH(q) and GARCH(p,q) take into account heteroskedasticity (non-stationarity) of time series. However, the original ARCH(q) and GARCH(p,q) models do not take into account the asymmetry of the market's response to positive and to negative changes. Several heuristic modifications of ARCH(q) and GARCH(p,q) models have been proposed that take this asymmetry into account. These modifications turned out to be very adequate and efficient in describing the econometric time series. In this paper, we propose a justification of these heuristic modifications -- and thus, an explanation of their empirical efficiency.

File in pdf and in Compressed Postscript

Technical Report UTEP-CS-09-01, January 2009

A Possible Way to Avoid Heat Death

Nitaya Buntao, Narunchara Katemee, and Vladik Kreinovich

Published in *Journal of Uncertain Systems*, 2010, Vok. 4,
No. 4, pp. 250-256.

A disturbing consequence of the traditional thermodynamics is the
possibility of *heat death*, when the Universe arrives at the
state with the largest possible value of the entropy and all the
processes will stop. In this paper, we show that one possible way to
avoid this consequence is to consider situations in which the
entropy never attains its maximum -- and thus, the heat death state
is not possible. We show that such situations can have physical
sense -- e.g., they naturally appear in boostrap models.

File in pdf and in Compressed Postscript