Computer Engineering Commons^™

A New Answer To Pauli's Question: Almost All Quantum States Can Be Uniquely Determined By Measuring Location And Momentum, Don Jackson, Olga Kosheleva

Departmental Technical Reports (CS)

In classical mechanics, we can uniquely reconstruct the state of each particle by measuring its spatial location and momentum. In his 1958 paper, W. Pauli, one of the founders of quantum mechanics, conjectured that the same should be true in the quantum case as well: that every quantum state can be uniquely determined by measuring spatial location and momentum. This conjecture was disproven: there are pairs of physically different states that cannot be distinguished if we only measure special location and momentum. A natural question is: how frequent are such pairs? In this paper, we show that almost all quantum …

Visualization Queries, Nicholas Del Rio, Paulo Pinheiro Da Silva

Departmental Technical Reports (CS)

This paper introduces the notion of a query that describes a visualization request in terms of a universe of concepts, which includes but is not limited to Views, Operators, and Parameters. In the presence of specifications based on these concepts, users may be able to request for what properties they want to see in their visualizations (i.e., the graphical analogues of some dataset) without having to specify how to generate them, and more importantly, without being fully aware of a wide range of toolkit specific implementation details. The result of a query is a visualization that satisfies declarative user-defined criteria …

Uncertainty In Partially Ordered Sets As A Natural Generalization Of Intervals: Negative Information Is Sufficient, Positive Is Not, David Mireles, Olga Kosheleva

Departmental Technical Reports (CS)

In many real-life applications, we have an ordered set: a set of all space-time events, a set of all alternatives, a set of all degrees of confidence. In practice, we usually only have a partial information about an element x of this set. This partial information includes positive knowledge: that a <= x or x <= a for some known a, and negative knowledge: that it is not true that a <= x or x <= a for some known a. In the case of a total order, the set of all elements satisfying this partial information is an interval. We show that in the general case of a partial order, the corresponding analogue of an interval is a convex set. We also show that in general, to describe partial knowledge, it is sufficient to have only negative information about x but it is not sufficient to have only positive information.

Why Feynman Path Integration?, Jaime Nava, Juan Ferret, Vladik Kreinovich, Gloria Berumen, Sandra Griffin, Edgar Padilla

Departmental Technical Reports (CS)

To describe physics properly, we need to take into account quantum effects. Thus, for every non-quantum physical theory, we must come up with an appropriate quantum theory. A traditional approach is to replace all the scalars in the classical description of this theory by the corresponding operators. The problem with the above approach is that due to non-commutativity of the quantum operators, two mathematically equivalent formulations of the classical theory can lead to different (non-equivalent) quantum theories. An alternative quantization approach that directly transforms the non-quantum action functional into the appropriate quantum theory, was indeed proposed by the Nobelist Richard …

Expanding Algorithmic Randomness To The Algebraic Approach To Quantum Physics: Kolmogorov Complexity And Quantum Logics, Vladik Kreinovich

Departmental Technical Reports (CS)

Physicists usually assume that events with a very small probability cannot occur. Kolmogorov complexity formalizes this idea for non-quantum events. We show how this formalization can be extended to quantum events as well.

Strings Lead To Lattice-Type Causality, Francisco Zapata, Essau Ramirez, Joel A. Lopez, Olga Kosheleva

Departmental Technical Reports (CS)

Traditional causality relation of special relativity is a lattice in the simplest case of 1-D space (2-D space-time), but it is no longer a lattice in the actual 3-D space (and 4-D space-time). We show that if we take into account effects of string theory, then we get a lattice-type causality relation even for the 4-D space-time.

Towards Simpler Description Of Properties Like Commutativity And Associativity: Using Expression Fragments, Shubhra Datta, Valeria Fierro, Krasen Petrov, Jessica Romo, Gesuri Ramirez, Cesar Valenzuela

Departmental Technical Reports (CS)

Properties like commutativity and associativity are very important in many applications. To make detecting these properties easier, it is desirable to reformulate them in the simplest possible way. A known way to simplify these descriptions is to use postfix notations, in which there is no need to use parentheses. We show that some of these properties can be further simplified if we represent them as equalities not between well-defined expressions, but as equalities between expression fragments.

Equivalence Of Gian-Carlo Rota Poset Approach And Taylor Series Approach Extended To Variant Ligands, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, molecules can be obtained from a "template" molecule like benzene by replacing some of its hydrogen atoms with ligands (other atoms or atom groups). There can be many possible replacements of this type. To avoid time-consuming testing of all possible replacements, it is desirable to test some of the replacements and then extrapolate to others -- so that only the promising molecules, for which the extrapolated values are desirable, will have to be synthesized and tested.

Towards A Fast, Practical Alternative To Joint Inversion Of Multiple Datasets: Model Fusion, Omar Ochoa, Aaron A. Velasco, Christian Servin

Departmental Technical Reports (CS)

In many areas of science and engineering, we have different sources of data. For example, in geophysics, there are many sources of data for Earth models: first-arrival passive seismic data (from the actual earthquakes), first-arrival controlled-source seismic data (from the seismic experiments), gravity data, etc.

A Use Case-Guided Comparison Of Opm And Pml, Paulo Pinheiro Da Silva, Steve Roach

Departmental Technical Reports (CS)

The World Wide Web Consortium (W3C) Provenance Incubator Group has the goal of providing "a state-of-the art understanding ... in the area of provenance for Semantic Web technologies." To enhance the mutual understanding of language capabilities, the group is attempting to map several of the existing provenance languages such as Provenir, PREMIS, and the Proof Markup Language (PML) into the provenance language the Open Provenance Model (OPM). OPM is intended to be a precise inter-lingua for exchanging provenance information. This article contributes to the understanding of the capabilities of OPM and PML by establishing a set of six common and …

A Tutorial On Functional Program Verification, Yoonsik Cheon, Melisa Vela

Departmental Technical Reports (CS)

This document gives a quick tutorial introduction to a functional program verification. In the functional program verification, a program is viewed as a mathematical function from one program state to another, and proving its correctness is essentially comparing two mathematical functions, the function computed by the program and the specification of the program, called an intended function. The reader is assumed to have some programming experience and to be familiar with such mathematical concepts as sets and functions.

From Interval And Probabilistic Granules To Granules Of Higher Order, Vladik Kreinovich

Departmental Technical Reports (CS)

Constructive mathematics, mathematics in which the existence of an object means that that we can actually construct this object, started as a heavily restricted version of mathematics, a version in which many commonly used mathematical techniques (like the Law of Excluded Middle) were forbidden to maintain constructivity. Eventually, it turned out that not only constructive mathematics is not a weakened version of the classical one -- as it was originally perceived -- but that, vice versa, classical mathematics can be viewed as a particular (thus, weaker) case of the constructive one. Crucial results in this direction were obtained by M. …

Visualization To Support The Discovery Of Prosodic Contours Related To Turn-Taking, Nigel Ward, Joshua L. Mccartney

Departmental Technical Reports (CS)

Some meaningful prosodic patterns can be usefully represented with pitch contours, however the development of such descriptions is a labor-intensive process. To assist in the discovery of contours, visualization tools may be helpful. Edlund et al. (2009) presented the idea of superimposing hundreds of pitch curves from a corpus as a way to see the overall patterns. In this paper we refine and extend this method and illustrate its utility in the discovery of a prosodic cue to back-channels in Chinese. We also discuss issues in relating a contour-based description to one in terms of a conjunction of features, and …

Computing Standard-Deviation-To-Mean And Variance-To-Mean Ratios Under Interval Uncertainty Is Np-Hard, Sio-Long Lo

Departmental Technical Reports (CS)

Once we have a collection of values x1, ..., ,xn corresponding a class of objects, a usual way to decide whether a new object with the value x of the corresponding property belongs to this class is to check whether the value x belongs to interval [E - k0 * s, E + k0 * s], where E = (1/n) * (x1 + ... + xn) is the sample mean, V = s^2 = (1/n) * ((x1 - E)^2 + ... + (xn - E)^2) is the sample variance, and the parameter k0 is determined by the degree of confidence …

Cantor's Paradise Regained: Constructive Mathematics From Brouwer To Kolmogorov To Gelfond, Vladik Kreinovich

Departmental Technical Reports (CS)

Constructive mathematics, mathematics in which the existence of an object means that that we can actually construct this object, started as a heavily restricted version of mathematics, a version in which many commonly used mathematical techniques (like the Law of Excluded Middle) were forbidden to maintain constructivity. Eventually, it turned out that not only constructive mathematics is not a weakened version of the classical one -- as it was originally perceived -- but that, vice versa, classical mathematics can be viewed as a particular (thus, weaker) case of the constructive one. Crucial results in this direction were obtained by M. …

Constraint-Related Reinterpretation Of Fundamental Physical Equations Can Serve As A Built-In Regularization, Vladik Kreinovich, Juan Ferret, Martine Ceberio

Departmental Technical Reports (CS)

Many traditional physical problems are known to be ill-defined: a tiny change in the initial condition can lead to drastic changes in the resulting solutions. To solve this problem, practitioners regularize these problem, i.e., impose explicit constraints on possible solutions (e.g., constraints on the squares of gradients). Applying the Lagrange multiplier techniques to the corresponding constrained optimization problems is equivalent to adding terms proportional to squares of gradients to the corresponding optimized functionals. It turns out that many optimized functionals of fundamental physics already have such squares-of-gradients terms. We therefore propose to re-interpret these equations -- by claiming that they …

Studies In The Use Of Time Into Utterance As A Predictive Feature For Language Modeling, Nigel Ward, Alejandro Vega

Departmental Technical Reports (CS)

In (Ward and Vega 2008) we examined how how word probabilities vary with time into utterance, and proposed a method for using this information to improve a language model. In this report we examine some ancillary issues in the modeling and exploitation of these regularities.

Functional Specification And Verification Of Object-Oriented Programs, Yoonsik Cheon

Departmental Technical Reports (CS)

One weakness of Hoare-style verification techniques based on first-order predicate logic is that reasoning is backward from postconditions to preconditions. A natural, forward reasoning is possible by viewing a program as a mathematical function that maps one program state to another. This functional program verification technique requires a minimal mathematical background as it uses equational reasoning based on sets and functions. Thus, it can be easily taught and used in practice. In this paper, we formalize a functional program specification and verification technique and extend it for object-oriented programs. Our approach allows one to formally specify and verify the behavior …

Why Ellipsoid Constraints, Ellipsoid Clusters, And Riemannian Space-Time: Dvoretzky's Theorem Revisited, Karen Villaverde, Olga Kosheleva, Martine Ceberio

Departmental Technical Reports (CS)

In many practical applications, we encounter ellipsoid constraints, ellipsoid-shaped clusters, etc. A usual justification for this ellipsoid shape comes from the fact that many real-life quantities are normally distributed, and for a multi-variate normal distribution, a natural confidence set (containing the vast majority of the objects) is an ellipsoid. However, ellipsoid appear more frequently than normal distributions (which occur in about half of the cases). In this paper, we provide a new justification for ellipsoids based on a known mathematical result -- Dvoretzky's Theorem.

Towards An Efficient Bisection Of Ellipsoids, Paden Portillo, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Constraints are often represented as ellipsoids. One of the main advantages of such constrains is that, in contrast to boxes, over which optimization of even quadratic functions is NP-hard, optimization of a quadratic function over an ellipsoid is feasible. Sometimes, the area described by constrains is too large, so it is reasonable to bisect this area (one or several times) and solve the optimization problem for all the sub-areas. Bisecting a box, we still get a box, but bisecting an ellipsoid, we do not get an ellipsoid. Usually, this problem is solved by enclosing the half-ellipsoid in a larger ellipsoid, …

From Computing Sets Of Optima, Pareto Sets, And Sets Of Nash Equilibria To General Decision-Related Set Computations, Vladik Kreinovich

Departmental Technical Reports (CS)

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.

Minimum Description Length (Mdl) Principle As A Possible Approach To Arc Detection, Jan Beck, David Nemir, Vladik Kreinovich

Departmental Technical Reports (CS)

Detecting arcing faults is an important but difficult-to-solve practical problem. In this paper, we show how the Minimum Description Length (MDL) Principle can help in solving this problem.

Optimal Prices In The Presence Of Discounts: A New Economic Application Of Choquet Integrals, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

In many real-life situations, there are ``package deals'', when customers who buy two or more different items get a special discount. For example, when planning a trip, a deal including airfare and hotel costs less than the airfare and hotel on their own; there are often also special deals when we combine airfare with car rental, and deals that cover all three items plus tickets to local tourist attractions, etc.

Usually, there are several such deals with different combinations and different discounts. What if we plan to buy several different copies of each item: e.g., we plan a group tour …

Spatial Resolution For Processing Seismic Data: Type-2 Methods For Finding The Relevant Granular Structure, Vladik Kreinovich, Jaime Nava, Rodrigo Romero, Julio Olaya, Aaron A. Velasco, Kate C. Miller

Departmental Technical Reports (CS)

One of the main methods of determining the Earth structure is the analysis of the seismic data. Based on the seismic data, we produce a 3-D map describing the density at different locations on different depths. Due to incomplete coverage and measurement uncertainty, this map provides only an approximate description of the actual density distribution. For example, based on the seismic data, it is impossible to distinguish between the densities at two nearby points. In other words, what we actually reconstruct is not a function of 3 variables, but rather values determined on the appropriate spatial granules. Because of this …

How To Describe Spatial Resolution: An Approach Similar To The Central Limit Theorem, Omar Ochoa, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

For spatially distributed quantities v(x), there are two main reasons why the measured value is different from the actual value. First, the sensors are imprecise, so the measured value is slightly different from the actual one. Second, sensors have a finite {\it spatial resolution}: they do not simply measure the value at a single point, they are "blurred", i.e., affected by the values of the nearby points as well. It is known that uncertainty can be often described by the Gaussian distribution. This possibility comes from the Central Limit Theorem, according to which the sum of many independent small measurement …

Toward Computing An Optimal Trajectory For An Environment-Oriented Unmanned Aerial Vehicle (Uav) Under Uncertainty, Jerald Brady, Octavio Lerma, Vladik Kreinovich, Craig Tweedie

Departmental Technical Reports (CS)

Over the past decade a few but increasing number of researchers have begun using Unmanned Aerial Vehicles (UAVs) to expand and improve upon existing remote sensing capabilities in the Arctic. Due to the limited flight time, it is important to make sure that the UAV follows an optimal trajectory -- in which it cover all the points from a given area within the smallest possible trajectory length. Under the usual assumptions that we cover a rectangular area and that each on-board sensor covers all the points with a given radius r, we describe the optimal trajectory. A more complex optimal …

Towards A More Adequate Defuzzification Of Interval-Valued Fuzzy Sets, Vladik Kreinovich, Van Nam Huynh, Yoshiteru Nakamori

Departmental Technical Reports (CS)

It is known that interval-valued fuzzy sets [m(x)] provide a more adequate description of expert uncertainty than the more traditional "type-1" (number-valued) fuzzy techniques. Specifically, an interval-valued fuzzy set can be viewed as a class of possible fuzzy sets m(x) from [m(x)]. In this case, as a result of defuzzification, it is natural to return the range [u] of all possible values u(m) that can be obtained by defuzzifying membership functions m(x) from this class. In practice, it is reasonable to restrict ourselves only to fuzzy numbers m(x), i.e., to "unimodal" fuzzy sets. Under this restriction, in general, we get …

How To Define A Confidence Set For Functions: A New Justification Of The Area Method, Vladik Kreinovich, Gang Xiang, Michael Oberguggenberger

Departmental Technical Reports (CS)

Due to uncertainty, in many problems, we only know the probability of different values. In such situations, we need to make decisions based on these probabilities: e.g., we must tell the user which values are possible and which are not. Often -- e.g., for a normal distribution -- the probability density is everywhere positive, so, theoretically, all real values are possible. In practice, it is usually safe to assume that values whose probability is very small are not possible. For a single variable, this idea is described by a confidence interval C, the interval for which the probability to be …

Femprof: Advancing Females To The Professoriate In Computing, Nestor J. Rodriguez, Richard A. Alo, Sarah Hug, Sangeeta Gad, Nayda Santiago, Gladys O. Ducodray

Departmental Technical Reports (CS)

Considering both the percentage of science and engineering PhDs awarded to women in the twenty year period 1974-2004 and the data from the National Science 2006 Survey of Earned Doctorates 1974-2004, the U.S. National Academies noted that women in 2004 have attained equality with men in their representation in the Social Sciences and Life Sciences but are still lagging in Physical and Computing Sciences and Engineering. In the top 50 engineering departments in the U.S., women earn one-fourth of the PhDs granted in Chemical Engineering and 15% in engineering overall (Handelsman et al, 2005). Although women constitute about half of …

How To Relate Fuzzy And Owa Estimates, Tanja Magoc, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we have several estimates x1, ..., xn of the same quantity x, i.e., estimates for which x1 ~ x, x2 ~ x, ..., and xn ~ x. It is desirable to combine (fuse) these estimates into a single estimate for x. From the fuzzy viewpoint, a natural way to combine these estimates is: (1) to describe, for each x and for each i, the degree mu(xi - x) to which x is close to xi, (2) to use a t-norm ("and"-operation) to combine these degrees into a degree to which x is consistent with all n …