Computer Engineering Commons^™

Adding Constraints -- A (Seemingly Counterintuitive But) Useful Heuristic In Solving Difficult Problems, Olga Kosheleva, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Intuitively, the more constraints we impose on a problem, the more difficult it is to solve it. However, in practice, difficult-to-solve problems sometimes get solved when we impose additional constraints and thus, make the problems seemingly more complex. In this methodological paper, we explain this seemingly counter-intuitive phenomenon, and we show that, dues to this explanation, additional constraints can serve as a useful heuristic in solving difficult problems.

Mamdani Approach To Fuzzy Control, Logical Approach, What Else?, Samuel Bravo, Jaime Nava

Departmental Technical Reports (CS)

In fuzzy control, two approaches are mainly used: Mamdani's approach, in which we represent the knowledge base as a disjunction of statements Ai(x) & Bi(u) corresponding to individual rules, and logical approach, in which the knowledge base is represented as a conjunction of the rules themselves Ai(x) --> Bi(u). Both approaches are known not to be perfect, so a natural question arises: what other approaches are possible? In this paper, we describe all possible approaches; alternative approaches use an "exclusive or" operation and correspond, e.g., to the fuzzy transform idea.

From Program Synthesis To Optimal Program Synthesis, Joaquin Reyna

Departmental Technical Reports (CS)

Fusing Continuous And Discrete Data, On The Example Of Merging Seismic And Gravity Models In Geophysics, Omar Ochoa, Aaron Velasco, Vladik Kreinovich

Departmental Technical Reports (CS)

Towards Optimal Placement Of Bio-Weapon Detectors, Chris Kiekintveld, Octavio Lerma

Departmental Technical Reports (CS)

Biological weapons are difficult and expensive to detect. Within a limited budget, we can afford a limited number of bio-weapon detector stations. It is therefore important to find the optimal locations for such stations. A natural idea is to place more detectors in the areas with more population -- and fewer in desert areas, with fewer people. However, such a commonsense analysis does not tell us how many detectors to place where. To decide on the exact placement of bio-weapon detectors, we formulate the placement problem in precise terms, and come up with an (almost) explicit solution to the resulting …

How To Tell When A Product Of Two Partially Ordered Spaces Has A Certain Property: General Results With Application To Fuzzy Logic, Francisco Zapata, Olga Kosheleva, Karen Villaverde

Departmental Technical Reports (CS)

Towards Optimal Sensor Placement In Multi-Zone Measurements, Octavio Lerma, Craig Tweedie, Vladik Kreinovich

Departmental Technical Reports (CS)

In multi-zone areas, where the boundaries change with time, it is desirable to place sensors in such a way that the boundary is covered at all times. In this paper, we describe the optimal sensor placement with this property. In this optimal placement, sensors are placed along a see-saw trajectory going between the current location of the boundary and its farthest future location.

Computing The Range Of Variance-To-Mean Ratio Under Interval And Fuzzy Uncertainty, Sio-Long Lo, Gang Xiang

Departmental Technical Reports (CS)

In many practical problems such as radar imaging, it is useful to compute the variance-to-mean ratio. The need is important because for the sum of k identical independent signal components, both the variance and the mean are multiplied by k, so this ratio is independent on k and thus, provides useful information about the components. In practice, we only know the samples values with uncertainty. It is therefore necessary to compute the variance-to-mean ratio under this uncertainty. In this paper, we present efficient algorithms for computing this ratio under interval and fuzzy uncertainty.

Towards Chemical Applications Of Dempster-Shafer-Type Approach: Case Of Variant Ligands, Jaime Nava

Departmental Technical Reports (CS)

Why Curvature In L-Curve: Combining Soft Constraints, Uram Anibal Sosa Aguirre, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In solving inverse problems, one of the successful methods of determining the appropriate value of the regularization parameter is the L-curve method of combining the corresponding soft constraints, when we plot the curve describing the dependence of the logarithm $x$ of the mean square difference on the logarithm $y$ of the mean square non-smoothness, and select a point on this curve at which the curvature is the largest. This method is empirically successful, but from the theoretical viewpoint, it is not clear why we should use curvature and not some other criterion. In this paper, we show that reasonable scale-invariance …

How To Bargain: An Interval Approach, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

Why L2 Topology In Quantum Physics, Chris Culellar, Evan Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

It is known that in quantum mechanics, the set S of all possible states coincides with the set of all the complex-valued functions f(x) for which the integral of |f(x)|² is 1. From the mathematical viewpoint, this set is a unit sphere in the space L² of all the functions for which this integralis finite. Because of this mathematical fact, usually the set S is considered with the topology induced by L², i.e., topology in which the basis of open neighborhood of a state f is formed by the open balls. This topology seem to work …

Cleanjava: A Formal Notation For Functional Program Verification, Yoonsik Cheon, Cesar Yeep, Melisa Vela

Departmental Technical Reports (CS)

Unlike a Hoare-style program verification, a functional program verification supports forward reasoning by viewing a program as a mathematical function from one program state to another and proving its correctness by essentially comparing two mathematical functions, the function computed by the program and its specification. Since it requires a minimal mathematical background and reflects the way programmers reason about the correctness of a program informally, it can be taught and practiced effectively. However, there is no formal notation supporting the functional program verification. In this paper, we propose a formal notation for writing functional program specifications for Java programs. The …

Power Vs. Performance Evaluation Of Synthetic Aperture Radar Image-Formation Algorithms And Implementations For Embedded Hec Environments (Ongoing Study), Ricardo Portillo, Sarala Arunagiri, Patricia J. Teller

Departmental Technical Reports (CS)

The continuing miniaturization and parallelization of processing hardware has facilitated the development of mobile and field-deployable systems that can accommodate terascale processing within once prohibitively small size and weight constraints. Unfortunately, the added computational capability of these small systems often comes at the cost of larger power demands, an already strained resource in these embedded systems. This study explores the power issues in a specific type of field-deployable system, Mobile Radar. Specifically, we focus on a computationally intensive phase of Synthetic Aperture Radar, Image Formation (IF), and evaluate performance tradeoffs in terms of time-to-solution, output image quality, and power consumption …

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 …