Computer Engineering Commons^™

Quantum Versions Of K-Csp Algorithms: A First Step Towards Quantum Algorithms For Interval-Related Constraint Satisfaction Problems, Evgeny Dantsin, Alexander Wolpert, Vladik Kreinovich

Departmental Technical Reports (CS)

In many industrial engineering problems, we must select a design, select parameters of a process, or, in general, make a decision. Informally, this decision must be optimal, the best for the users. In traditional operations research, we assume that we know the objective function f(x) whose values describe the consequence of a decision x for the user. Optimization of well-defined functions is what started calculus in the first place: once we know the objective function f(x), we can use differentiation to find its maximum, e.g., as the point x at which the derivative of f with respect to x is …

Decision Making Beyond Arrow's "Impossibility Theorem", With The Analysis Of Effects Of Collusion And Mutual Attraction, Hung T. Nguyen, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In 1951, K. J. Arrow proved that, under certain assumptions, it is impossible to have group decision making rules which satisfy reasonable conditions like symmetry. This Impossibility Theorem is often cited as a proof that reasonable group decision making is impossible.

We start our paper by remarking that Arrow's result only covers the situations when the only information we have about individual preferences is their binary preferences between the alternatives. If we follow the main ideas of modern decision making and game theory and also collect information about the preferences between lotteries (i.e., collect the utility values of different alternatives), …

Co-Generation Of Text And Graphics, David G. Novick, Brian Lowe

Departmental Papers (CS)

To reduce potential discrepancies between textual and graphical content in documentation, it is possible to produce both text and graphics from a single common source. One approach to co-generation of text and graphics uses a single logical specification; a second approach starts with CAD-based representation and produces a corresponding textual account. This paper explores these two different approaches, reports the results of using prototypes embodying the approaches to represent simple figures, and discusses issues that were identified through use of the prototypes. While it appears feasible to co-generate text and graphics automatically, the process raises deep issues of design of …

Usability Over Time, Valerie Mendoza, David G. Novick

Departmental Papers (CS)

Testing of usability could perhaps be more accurately described as testing of learnability. We know more about the problems of novice users than we know of the problems of experienced users. To understand how these problems differ, and to understand how usability problems change as users change from novice to experienced, we conducted a longitudinal study of usability among middle-school teachers creating Web sites. The study looked at the use both the use of documentation and the underlying software, tracking the causes and extent of user frustration over eight weeks. We validated a categorization scheme for frustration episodes. We found …

Root Causes Of Lost Time And User Stress In A Simple Dialog System, Nigel G. Ward, Anais G. Rivera, Karen Ward, David G. Novick

Departmental Papers (CS)

As a priority-setting exercise, we compared interactions between users and a simple spoken dialog system to interactions between users and a human operator. We observed usability events, places in which system behavior differed from human behavior, and for each we noted the impact, root causes, and prospects for improvement. We suggest some priority issues for research, involving not only such core areas as speech recognition and synthesis and language understanding and generation, but also less-studied topics such as adaptive or flexible timeouts, turn-taking and speaking rate.

Optimization And Decision Making Under Interval And Fuzzy Uncertainty: Towards New Mathematical Foundations, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

In many industrial engineering problems, we must select a design, select parameters of a process, or, in general, make a decision. Informally, this decision must be optimal, the best for the users. In traditional operations research, we assume that we know the objective function f(x) whose values describe the consequence of a decision x for the user. Optimization of well-defined functions is what started calculus in the first place: once we know the objective function f(x), we can use differentiation to find its maximum, e.g., as the point x at which the derivative of f with respect to x is …

Towards A Cross-Platform Microbenchmark Suite For Evaluating Hardware Performance Counter Data, Maria G. Aguilera, Roberto Araiza, Thientam Pham, Patricia J. Teller

Departmental Technical Reports (CS)

As useful as performance counters are, the meaning of reported aggregate event counts is sometimes questionable. Questions arise due to unanticipated processor behavior, overhead associated with the interface, the granularity of the monitored code, hardware errors, and lack of standards with respect to event definitions. To explore these issues, we are conducting a sequence of studies using carefully crafted microbenchmarks that permit the accurate prediction of event counts and investigation of the differences between hardware-reported and predicted event counts. This paper presents the methodology employed, some of the microbenchmarks developed, and some of the information uncovered to date. The information …

On Quantum Versions Of Record-Breaking Algorithms For Sat, Evgeny Dantsin, Vladik Kreinovich, Alexander Wolpert

Departmental Technical Reports (CS)

It is well known that a straightforward application of Grover's quantum search algorithm enables to solve SAT in O(2^(n/2)) steps. Ambainis (SIGACT News, 2004) observed that it is possible to use Grover's technique to similarly speed up a sophisticated algorithm for solving 3-SAT. In this note, we show that a similar speed up can be obtained for all major record-breaking algorithms for satisfiability. We also show that if we use Grover's technique only, then we cannot do better than quadratic speed up.

Discrete Conservation Of Nonnegativity For Elliptic Problems Solved By The Hp-Fem, Pavel Solin, Thomas Vejchodsky, Roberto Araiza

Departmental Technical Reports (CS)

Most results related to discrete nonnegativity conservation principles (DNCP) for elliptic problems are limited to finite differences (FDM) and lowest-order finite element methods (FEM). In this paper we confirm that a straightforward extension to higher-order finite element methods (hp-FEM) in the classical sense is not possible. We formulate a weaker DNCP for the Poisson equation in one spatial dimension and prove it using an interval computing technique. Numerical experiments related to the extension of this result to 2D are presented.

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, Chitta Baral

Departmental Technical Reports (CS)

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 …

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 C. Da Costa Rocha, Karen Villaverde

Departmental Technical Reports (CS)

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 …

Processing Educational Data: From Traditional Statistical Techniques To An Appropriate Combination Of Probabilistic, Interval, And Fuzzy Approaches, Olga Kosheleva, Martine Ceberio

Departmental Technical Reports (CS)

There are many papers that experimentally compare effectiveness of different teaching techniques. Most of these papers use traditional statistical approach to process the experimental results. The traditional statistical approach is well suited to numerical data but often, what we are processing is either intervals (e.g., A means anything from 90 to 100) or fuzzy-type perceptions, words from the natural language like "understood well" or "understood reasonably well". We show that the use of intervals and fuzzy techniques leads to more adequate processing of educational data.

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, Janos Hajagos

Departmental Technical Reports (CS)

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 …

Towards Combining Probabilistic And Interval Uncertainty In Engineering Calculations: Algorithms For Computing Statistics Under Interval Uncertainty, And Their Computational Complexity, Vladik Kreinovich, Gang Xiang, Scott A. Starks, Luc Longpre, Martine Ceberio, Roberto Araiza, J. Beck, R. Kandathi, A. Nayak, R. Torres, J. Hajagos

Departmental Technical Reports (CS)

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 …

Which Fuzzy Logic Is The Best: Pragmatic Approach (And Its Theoretical Analysis), Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

In this position paper, we argue that when we are looking for the best fuzzy logic, we should specify in what sense the best, and that we get different fuzzy logics as ``the best'' depending on what optimality criterion we use.

Kolmogorov Complexity Leads To A Representation Theorem For Idempotent Probabilities (Sigma-Maxitive Measures), Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

In many application areas, it is important to consider maxitive measures (idempotent probabilities), i.e., mappings m for which m(A U B)=max(m(A),m(B)). In his papers, J. H. Lutz has used Kolmogorov complexity to show that for constructively defined sets A, one maxitive measure - fractal dimension - can be represented as m(A)= sup{f(x): x in A}. We show that a similar representation is possible for an arbitrary maxitive measure.

If An Exact Interval Computation Problem Is Np-Hard, Then The Approximate Problem Is Also Np-Hard: A Meta-Result, Aline B. Loreto, Laira V. Toscani, Leila Robeiro, Dalcidio M. Claudio, Liara S. Leal, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

In interval computations, usually, once we prove that a problem of computing the exact range is NP-hard, then it later turns out that the problem of computing this range with a given accuracy is also NP-hard. In this paper, we provide a general explanation for this phenomenon.

Consortium Of Cise-Mii Funded Institutions: Initial Recommendations On Broadening Participation Of Hispanics, Ann Q. Gates

Departmental Technical Reports (CS)

No abstract provided.

Kaluza-Klein 5d Ideas Made Fully Geometric, Scott A. Starks, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

After the 1916 success of General relativity that explained gravity by adding time as a fourth dimension, physicists have been trying to explain other physical fields by adding extra dimensions. In 1921, Kaluza and Klein has shown that under certain conditions like cylindricity (dg_{ij}/dx^5=0), the addition of the 5th dimension can explain the electromagnetic field. The problem with this approach is that while the model itself is geometric, conditions like cylindricity are not geometric. This problem was partly solved by Einstein and Bergman who proposed, in their 1938 paper, that the 5th dimension is compactified into a small circle S^1 …

Some Usability Issues And Research Priorities In Spoken Dialog Applications, Nigel Ward, Anais G. Rivera, Karen Ward, David G. Novick

Departmental Technical Reports (CS)

As a priority-setting exercise, we examined interactions between users and a simple spoken dialog system in comparison to interactions with a human operator. Based on analysis of the observed usability differences and their root causes we propose seven priority issues for spoken dialog systems research.

Computing Best-Possible Bounds For The Distribution Of A Sum Of Several Variables Is Np-Hard, Vladik Kreinovich, Scott Ferson

Departmental Technical Reports (CS)

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 …

Why Product Of Probabilities (Masses) For Independent Events? A Remark, Vladik Kreinovich, Scott Ferson

Departmental Technical Reports (CS)

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 …

New Algorithms For Statistical Analysis Of Interval Data, Gang Xiang, Scott A. Starks, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

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 …

Use Of Maxitive (Possibility) Measures In Foundations Of Physics And Description Of Randomness: Case Study, A. M. Finkelstein, Olga Kosheleva, Vladik Kreinovich, Scott A. Starks, Hung T. Nguyen

Departmental Technical Reports (CS)

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.

From Fuzzification And Intervalization To Anglification: A New 5d Geometric Formalism For Physics And Data Processing, Scott A. Starks, Vladik Kreinovich

Departmental Technical Reports (CS)

We show that in understanding foundations of modern physics, with its 10-dimensional (and higher-dimensional) space-time models, it is very helpful to use the main ideas behind fuzzification -- extension of arithmetic operations and elementary functions from exact numbers to fuzzy numbers. The resulting formalism is, from the mathematical viewpoint, somewhat more complex than the traditional fuzzy arithmetic, but it is still much simpler than the quantum field theory -- and thus, it helps to make several important ideas from foundations of modern physics much more intuitively clear.

The Interval Categorizer Tesselation-Based Model For High Perfomance Computing, Marilton S. De Aguiar, Gracaliz P. Dimuro, Antonio C. Da Rocha Costa, Rafael K.S. Silva

Departmental Technical Reports (CS)

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 …

Random Interval Arithmetic Is Closer To Common Sense: An Observation, Rene Alt, Jean-Luc Lamotte, Vladik Kreinovich

Departmental Technical Reports (CS)

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 …

How The Concept Of Information As Average Number Of "Yes"-"No" Questions (Bits) Can Be Extended To Intervals, P-Boxes, And More General Uncertainty, Vladik Kreinovich, Gang Xiang, Scott Ferson

Departmental Technical Reports (CS)

We explain how the concept of information as average number of "yes"-"no" questions (bits) can be extended to intervals, p-boxes, and more general uncertainty.

Interval Methods: An Introduction, Luke Achenie, Vladik Kreinovich, Kaj Madsen

Departmental Technical Reports (CS)

The ongoing development of ever more advanced computers provides the potential for solving increasingly difficult computational problems. However, given the complexity of modern computer architectures, the task of realizing this potential needs careful attention. A main concern of High Performance Computing is the development of software that optimizes the performance of a given computer.

An important characteristic of the computer performance in scientific computing is the accuracy of the computation results. Often, we can estimate this accuracy by using traditional statistical techniques. However, in many practical situations, we do not know the probability distributions of different measurement, estimation, and/or roundoff …

Supporting Documentation For The Sps-Prospec Case Study, Salamah I. Salamah, Ann Q. Gates

Departmental Technical Reports (CS)

In this work, we report on the results of a case study comparing the correctness of Linear Temporal Logic (LTL)formulas generated by the Property Specification Tool Prospec and the Specification Pattern System (SPS). The report includes all the components used in the case study. In addition, this report provides a description of the use of the SPIN model checker to verify correctness of LTL specifications. Particularly, the report provides screenshots of XSPIN (SPIN�s graphical interface) and how properties (i.e., LTL formulas) can be specified and verified.