Engineering Commons^™

The Utep Corpus Of Iraqi Arabic, Nigel Ward, David G. Novick, Salamah I. Salamah

Departmental Technical Reports (CS)

The rules governing turn-taking phenomena are not well understood in general and almost completely undocumented for Arabic. As the first step to modeling these phenomena, we have collected a small corpus of Iraqi Arabic spoken dialogs. The corpus is in three parts. Part A is 110 minutes of unstructured conversations. Parts B1 and B2 are 176 minutes of direction-giving dialogs, most including a greeting phase, a smalltalk phase, a request phase, and a direction-giving phase. Parts A and B1 were recorded with 13 native speakers of Iraqi Arabic, interacting in pairs. In Part B2 the direction-getter is an American with …

Modeling Correlation And Dependence Among Intervals, Scott Ferson, Vladik Kreinovich

Departmental Technical Reports (CS)

This note introduces the notion of dependence among intervals to account for observed or theoretical constraints on the relationships among uncertain inputs in mathematical calculations. We define dependence as any restriction on the possible pairings of values within respective intervals and define nondependence as the degenerate case of no restrictions (which we carefully distinguish from independence in probability theory). Traditional interval calculations assume nondependence, but alternative assumptions are possible, including several which might be practical in engineering settings that would lead to tighter enclosures on arithmetic functions of intervals. We give best possible formulas for addition of intervals under several …

Interval-Based Robust Statistical Techniques For Non-Negative Convex Functions With Application To Timing Analysis Of Computer Chips, Michael Orshansky, Wei-Shen Wang, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In chip design, one of the main objectives is to decrease its clock cycle; however, the existing approaches to timing analysis under uncertainty are based on fundamentally restrictive assumptions. Statistical timing analysis techniques assume that the full probabilistic distribution of timing uncertainty is available; in reality, the complete probabilistic distribution information is often unavailable. Additionally, the existing alternative of treating uncertainty as interval-based, or affine, is limited since it cannot handle probabilistic information in principle. In this paper, a fundamentally new paradigm for timing uncertainty description is proposed as a way to consistently and rigorously handle partially available descriptions of …

On The Functional Form Of Convex Underestimators For Twice Continuously Differentiable Functions, Chirstodoulos A. Floudas, Vladik Kreinovich

Departmental Technical Reports (CS)

The optimal functional form of convex underestimators for general twice continuously differentiable functions is of major importance in deterministic global optimization. In this paper, we provide new theoretical results that address the classes of optimal functional forms for the convex underestimators. These are derived based on the properties of shift-invariance and sign-invariance.

Dilthey And Simmel: A Reading From/Toward Buber's Philosophy Of History, Jules Simon

Selected Works Temporary Series

No abstract provided.

Hegels Familienbegriff – Vermittelt Durch Rosenzweig: Darstellung Einer Eigentuemlichen Geschichte, Jules Simon

Selected Works Temporary Series

No abstract provided.

Swarm Intelligence: Theoretical Proof That Empirical Techniques Are Optimal, Dmitry Iourinskiy, Scott A. Starks, Vladik Kreinovich, Stephen F. Smith

Departmental Technical Reports (CS)

A natural way to distribute tasks between autonomous agents is to use swarm intelligence techniques, which simulate the way social insects (such as wasps) distribute tasks between themselves. In this paper, we theoretically prove that the corresponding successful biologically inspired formulas are indeed statistically optimal (in some reasonable sense).

Towards Optimal Techniques For Solving Global Optimization Problems: Symmetry-Based Approach, Chirstodoulos A. Floudas, Vladik Kreinovich

Departmental Technical Reports (CS)

Most techniques for solving global optimization problems have parameters that need to be adjusted to the problem or to the class of problems: for example, in gradient methods, we can select different step sizes. When we have a single parameter (or few parameters) to choose, it is possible to empirically try many values and come up with an (almost) optimal value. Thus, in such situations, we can come up with optimal version of the corresponding technique.

In other approaches, e.g., in methods like convex underestimators, instead of selecting the value of single number-valued parameter, we have select the auxiliary function. …

Interval Finite Element Methods: New Directions, Rafi Muhanna, Vladik Kreinovich, Pavel Solin, Jack Chessa, Roberto Araiza, Gang Xiang

Departmental Technical Reports (CS)

No abstract provided.

Static Timing Analysis Based On Partial Probabilistic Description Of Delay Uncertainty, Wei-Shen Wang, Vladik Kreinovich, Michael Orshansky

Departmental Technical Reports (CS)

No abstract provided.

Interview No. 1656, Robert W. Pitt

Combined Interviews

Robert Pitt was born in Detroit, MI on November 20, 1933; his family relocated a lot, he first remembers living in Portland, OR, later moved to Phoenix, AZ where he remembers the bombing of Pearl Harbor and followed the progress of World War II at home; he recounts moving to Los Angeles, CA for a year, his time as a batboy for the Los Angeles Angels and his love of baseball; he moved again to Chicago, IL to attend Morgan Park Military Academy, his father died when he was fifteen. Mr. Pitt describes time at Northwestern University in Evanston, IL …

Monte-Carlo-Type Techniques For Processing Interval Uncertainty, And Their Potential Engineering Applications, Vladik Kreinovich, J. Beck, Carlos M. Ferregut, A. Sanchez, George R. Keller, Matthew G. Averill, Scott A. Starks

Departmental Technical Reports (CS)

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.

Combining Interval, Probabilistic, And Fuzzy Uncertainty: Foundations, Algorithms, Challenges -- An Overview, Vladik Kreinovich, David J. Berleant, Scott Ferson, Weldon A. Lodwick

Departmental Technical Reports (CS)

Since the 1960s, many algorithms have been designed to deal with interval uncertainty. In the last decade, there has been a lot of progress in extending these algorithms to the case when we have a combination of interval and probabilistic uncertainty. We provide an overview of related algorithms, results, and remaining open problems.

Population Variance Under Interval Uncertainty: A New Algorithm, Evgeny Dantsin, Vladik Kreinovich, Alexander Wolper, Gang Xiang

Departmental Technical Reports (CS)

In statistical analysis of measurement results, it is often beneficial to compute the range [V] of the population variance V when we only know the intervals [Xi-Di,Xi+Di] of possible values of xi. In general, this problem is NP-hard; a polynomial-time algorithm is known for the case when the measurements are sufficiently accurate, i.e., when |Xi-Xj| >= (D_i+D_j)/n for all i =/= j. In this paper, we show that we can efficiently compute [V} under a weaker (and more general) condition |Xi-Xj| >= |D_i-D_j|/n.

Specifying And Checking Method Call Sequences Of Java Programs, Yoonsik Cheon, Ashaveena Perumandla

Departmental Technical Reports (CS)

In a pre and postconditions-style specification, it is difficult to specify the allowed sequences of method calls, referred to as protocols. The protocols are essential properties of reusable object-oriented classes and application frameworks, and the approaches based on the pre and postconditions, such as design by contracts (DBC) and formal behavioral interface specification languages (BISL), are being accepted as a practical and effective tool for describing precise interfaces of (reusable) program modules. We propose a simple extension to the Java Modeling Language (JML), a BISL for Java, to specify protocol properties in an intuitive and concise manner. The key idea …

Optimal Choice Of Granularity In Commonsense Estimation: Why Half-Orders Of Magnitude, Jerry R. Hobbs, Vladik Kreinovich

Departmental Technical Reports (CS)

It has been observed that when people make crude estimates, they feel comfortable choosing between alternatives which differ by a half-order of magnitude (e.g., were there 100, 300, or 1,000 people in the crowd), and less comfortable making a choice on a more detailed scale, with finer granules, or on a coarser scale (like 100 or 1,000). In this paper, we describe two models of choosing granularity in commonsense estimates, and we show that for both models, in the optimal granularity, the next estimate is 3-4 times larger than the previous one. Thus, these two optimization results explain the commonsense …

Computing Mean And Variance Under Dempster-Shafer Uncertainty: Towards Faster Algorithms, Vladik Kreinovich, Gang Xiang, Scott Ferson

Departmental Technical Reports (CS)

In many real-life situations, we only have partial information about the actual probability distribution. For example, under Dempster-Shafer uncertainty, we only know the masses m1,...,mn assigned to different sets S1,...,Sn, but we do not know the distribution within each set Si. Because of this uncertainty, there are many possible probability distributions consistent with our knowledge; different distributions have, in general, different values of standard statistical characteristics such as mean and variance. It is therefore desirable, given a Dempster-Shafer knowledge base, to compute the ranges of possible values of mean E and of variance V.

In their recent paper, A. T. …

Interval-Based Robust Statistical Techniques For Non-Negative Convex Functions, With Application To Timing Analysis Of Computer Chips, Michael Orshansky, Wei-Shen Wang, Martine Ceberio, Gang Xiang

Departmental Technical Reports (CS)

In chip design, one of the main objectives is to decrease its clock cycle. On the design stage, this time is usually estimated by using worst-case (interval) techniques, in which we only use the bounds on the parameters that lead to delays. This analysis does not take into account that the probability of the worst-case values is usually very small; thus, the resulting estimates are over-conservative, leading to unnecessary over-design and under-performance of circuits. If we knew the exact probability distributions of the corresponding parameters, then we could use Monte-Carlo simulations (or the corresponding analytical techniques) to get the desired …

A Fitness Function For Modular Evolutionary Testing Of Object-Oriented Programs, Yoonsik Cheon, Kim Myoung

Departmental Technical Reports (CS)

We show that encapsulation of states in object-oriented programs hinders the search for test data using evolutionary testing. In a well-designed object-oriented program the encapsulated or hidden state is accessible only through exported or public methods. As client code is oblivious to the internal state of a server object, no guidance is available to test the client code using evolutionary testing. In particular, it is difficult to determine the fitness or goodness of test data, as it may depend on the hidden internal state. However, evolutionary testing is a promising new approach whose effectiveness has been shown by several researchers. …

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 …