Computer Engineering Commons^™

On The Use Of Abstract Workflows To Capture Scientific Process Provenance, Paulo Pinheiro Da Silva, Leonardo Salayandia, Nicholas Del Rio, Ann Q. Gates

Departmental Technical Reports (CS)

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 …

Diagonalization Is Also Practically Useful: A Geometric Idea, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

"Weird" Fuzzy Notations: An Algebraic Interpretation, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditionally, fuzzy logic used non-standard notations like m₁/x₁ + ... + m_n/x_n for a function that attains the value m₁ at x₁, ..., and the value m_n at x_n. In this paper, we provide an algebraic explanation for these notations.

Quantum Computations Techniques For Gauging Reliability Of Interval And Fuzzy Data, Luc Longpre, Christian Servin, Vladik Kreinovich

Departmental Technical Reports (CS)

In traditional interval computations, we assume that the interval data corresponds to guaranteed interval bounds, and that fuzzy estimates provided by experts are correct. In practice, measuring instruments are not 100% reliable, and experts are not 100% reliable, we may have estimates which are "way off", intervals which do not contain the actual values at all. Usually, we know the percentage of such outlier un-reliable measurements. However, it is desirable to check that the reliability of the actual data is indeed within the given percentage. The problem of checking (gauging) this reliability is, in general, NP-hard; in reasonable cases, there …

Square Root Of "Not": A Major Difference Between Fuzzy And Quantum Logics, Vladik Kreinovich, Ladislav J. Kohout, Eunjin Kim

Departmental Technical Reports (CS)

Many authors have mentioned the similarity between quantum logic and fuzzy logic. In this paper, we show that, in spite of this similarity, these logics are not identical. Specifically, we emphasize that while quantum logic has a special ``square root of not'' operation which is very useful in quantum computing, fuzzy logic lacks such an operation.

Probabilistic Interpretation Of Fuzzy Transforms And Fuzzy Control, Irina Perfilieva, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical applications, it turns out to be useful to use the notion of fuzzy transform: once we have non-negative functions A₁(x), ..., A_n(x), with A₁(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₁ * A₁(x) + ... + F …

Engineering Design Under Imprecise Probabilities: Computational Complexity, Vladik Kreinovich

Departmental Technical Reports (CS)

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 [Fc(x); Fc(x)] on the cumulative distribution function Fc(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; …

Measurement's Result And Its Error As Fuzzy Variables: Background And Perspectives, Gennady N. Solopchenko, Konstantin K. Semenov, Vladik Kreinovich, Leon Reznik

Departmental Technical Reports (CS)

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.

Looking For Entropy Rate Constancy In Spoken Dialog, Alejandro Vega, Nigel Ward

Departmental Technical Reports (CS)

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, …

Equations Without Equations: Challenges On A Way To A More Adequate Formalization Of Causality Reasoning In Physics, Roberto Araiza, Vladik Kreinovich, Juan Ferret

Departmental Technical Reports (CS)

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, …

From Interval Computations To Constraint-Related Set Computations: Towards Faster Estimation Of Statistics And Odes Under Interval, P-Box, And Fuzzy Uncertainty, Martine Ceberio, Vladik Kreinovich, Andrzej Pownuk, Barnabas Bede

Departmental Technical Reports (CS)

In interval computations, at each intermediate stage of the computation, we have intervals of possible values of the corresponding quantities. In our previous papers, we proposed an extension of this technique to set computations, where on each stage, in addition to intervals of possible values of the quantities, we also keep sets of possible values of pairs (triples, etc.). In this paper, we show that in several practical problems, such as estimating statistics (variance, correlation, etc.) and solutions to ordinary differential equations (ODEs) with given accuracy, this new formalism enables us to find estimates in feasible (polynomial) time.

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, Juan Ferret

Departmental Technical Reports (CS)

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.

Towards Dynamical Systems Approach To Fuzzy Clustering, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

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 …

Expert Knowledge Is Needed For Design Under Uncertainty: For P-Boxes, Backcalculation Is, In General, Np-Hard, Vladik Kreinovich

Departmental Technical Reports (CS)

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 …

What Is The Best Way To Distribute Efforts Among Students: Towards Quantitative Approach To Human Cognition, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

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 …

Empirical Formulas For Economic Fluctuations: Towards A New Justification, Tanja Magoc, Vladik Kreinovich

Departmental Technical Reports (CS)

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 …

Guesstimation: A New Justification Of The Geometric Mean Heuristic, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

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.

Stochastic Volatility Models And Financial Risk Measures: Towards New Justifications, Hung T. Nguyen, Vladik Kreinovich, Songsak Sriboonchitta

Departmental Technical Reports (CS)

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.

Propitious Checkpoint Intervals To Improve System Performance, Sarala Arunagiri, John T. Daly, Patricia J. Teller

Departmental Technical Reports (CS)

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 …

Experiments In Teaching An Engaging And Demystifying Introduction To Algorithms: Installment 1: Huffman Codes, Alan Siegel, Eric Freudenthal

Departmental Technical Reports (CS)

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 …

Fast Convolution And Fast Fourier Transform Under Interval Uncertainty, Guoqing Liu, Vladik Kreinovich

Departmental Technical Reports (CS)

Convolution y(t), defined as an integral of a(t-s)*x(s) ds, is one of the main techniques in digital signal processing. A straightforward computation of the convolution y(t) requires O(n^2) steps, where n is the number of observations x(t0),...,x(t(n-1)). It is well known that by using the Fast Fourier Transform (FFT) algorithm, we can compute convolution much faster, with computation time O(n*log(n)).

In practice, we only know the signal x(t) and the function a(t) with uncertainty; sometimes, we know them with interval uncertainty, i.e., we know intervals [x-(t),x+(t)] and [a-(t),a+(t)] that contain the actual (unknown) functions x(t) and a(t). In such situations, …

Egyptian Fractions Revisited, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

It is well known that the ancient Egyptians represented each fraction as a sum of unit fractions -- i.e., fractions with unit numerators; this is how they, e.g., divided loaves of bread. What is not clear is why they used this representation. In this paper, we propose a new explanation: crudely speaking, that the main idea behind the Egyptian fractions provides an optimal way of dividing the loaves. We also analyze the related properties of fractions.

A New Justification Of Wang Transform Operator In Financial Risk Analysis, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

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.

Asymmetric Heteroskedasticity Models: A New Justification, Songsak Sriboonchitta, Vladik Kreinovich

Departmental Technical Reports (CS)

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.

Quantum Computing As A Particular Case Of Computing With Tensors, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

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.

A Possible Way To Avoid Heat Death, Nitaya Buntao, Narunchara Katemee, Vladik Kreinovich

Departmental Technical Reports (CS)

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.

Towards Neural-Based Understanding Of The Cauchy Deviate Method For Processing Interval And Fuzzy Uncertainty, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

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.

Health Prognisis Of Electronics Via Power Profiling, Jonathan Amilcar Cervantes

Open Access Theses & Dissertations

The objective of this research is to investigate a new approach for the early detection of latent defects in electronic devices in the field. Reliability is assessed through the non-traditional approach of recording and evaluating the power profile of electronic devices within a deterministic state of operation. Traditionally, measuring the quiescent current (Iddq) of a device has been employed in manufacturing tests to detect defective parts prior to deployment to the field. However, the monitoring of the deterministic power signature (i.e. boot up or during a self-test routine) has never been exploited to monitor the health of a device in …

Design Of A Low Voltage Analog To Digital Converter, Praveen Kumar Palakurthi

Open Access Theses & Dissertations

For the past 40 years, the number of transistors per chip has been increasing at an exponential rate confirming Moore's Law regarding the growth of chip complexity. Increases in transistor count have led to enhancements in functionality and made possible products with features that were unimaginable ten years ago. Consequently, the resulting increase in digitization in all electronics, across a wide range of applications, requires the Analog-to-Digital Converters (ADCs) with a higher resolution and lower power consumption. The evolution of the integrated circuit technologies and scaling methodologies partially helps in providing faster circuits and allowing complex functionalities in a given …

Estimating Risk Under Interval Uncertainty: Sequential And Parallel Algorithms, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

In traditional econometrics, the quality of an individual investment -- and of the investment portfolio -- is characterized by its expected return and its risk (variance). For an individual investment or portfolio, we can estimate the future expected return and a future risk by tracing the returns x₁, ..., x_n of this investment (and/or similar investments) over the past years, and computing the statistical characteristics based on these returns. The return (per unit investment) is defined as the selling of the corresponding financial instrument at the ends of, e.g., a one-year period, divided by the buying price …