Computer Engineering Commons^™

Evaluation Of Hf Rfid For Implanted Medical Applications, Eric Freudenthal, David Herrera, Frederick Kautz, Carlos Natividad, Alexandria Ogrey, Justin Sipla, Abimael Sosa, Carlos Betancourt, Leonardo Estevez

Departmental Technical Reports (CS)

Low cost HF RFID scanner subsystems that both deliver power and provide high bandwidth bidirectional communication channels have recently become available. These devices are anticipated to become ubiquitous in next-generation cell phones and enable a wide range of emerging e-commerce applications.

This paper considers the use of HF RFID to power and communicate with implantable medical devices. We successfully communicated with ten transponders that were implanted at three locations within a human cadaver. In this paper, we present measurements collected from four of these transponders that represent a wide range of transponder sizes. We also describe how RFID for medical …

Computing At Least One Of Two Roots Of A Polynomial Is, In General, Not Algorithmic, Vladik Kreinovich

Departmental Technical Reports (CS)

In our previous work, we provided a theoretical explanation for an empirical fact that it is easier to find a unique root than the multiple roots. In this short note, we strengthen that explanation by showing that finding one of many roots is also difficult.

Any (True) Statement Can Be Generalized So That It Becomes Trivial: A Simple Formalization Of D. K. Faddeev's Belief, Vladik Kreinovich

Departmental Technical Reports (CS)

In his unpublished lectures on general algebra, a well-known algebraist D. K. Faddeev expressed a belief that every true mathematical statement can be generalized in such a way that it becomes trivial. To the best of our knowledge, this belief has never been formalized before. In this short paper, we provide a simple formalization (and proof) of this belief.

A Quick Tutorial On Jet, Yoonsik Cheon

Departmental Technical Reports (CS)

JET is an automated unit testing tool for Java classes annotated with JML specifications; JML is a formal interface specification language for Java to document the behavior of Java classes and interfaces. JET tests each method of the class under test separately. For each method, it generates a collection of test data, executes them, and decides test results (i.e., pass/fail) by using JML specifications as test oracles, thereby fully automating unit testing of Java classes. This document gives a quick tutorial introduction to JET.

Abstraction In Assertion-Based Test Oracles, Yoonsik Cheon

Departmental Technical Reports (CS)

Assertions can be used as test oracles. However, writing effective assertions of right abstraction levels is difficult because on the one hand, detailed assertions are preferred for through testing (i.e., to detect as many errors as possible), but on the other hand abstract assertions are preferred for readability, maintainability, and reusability. As assertions become a practical tool for testing and debugging programs, this is an important and practical problem to solve for the effective use of assertions. We advocate the use of model variables---specification-only variables of which abstract values are given as mappings from concrete program states---to write abstract assertions …

On Probability Of Making A Given Decision: A Theoretically Justified Transition From Interval To Fuzzy Uncertainty, Van Nam Huynh, Yoshiteru Nakamori, Francois Modave

Departmental Technical Reports (CS)

In practice, it is often necessary to make a decision under uncertainty.

In the case of interval uncertainty, for each alternative i, instead of the exact value vi of the objective function, we only have an interval of possible values. In this case, it is reasonable to assume that each value vi is uniformly distributed on the corresponding interval, and to take the probability that vi is the largest as the probability of selecting the i-th alternative.

In some practical situations, we have fuzzy uncertainty, i.e., for every alternative i, we have a fuzzy number describing the value of the …

Detecting Duplicates In Geoinformatics: From Intervals And Fuzzy Numbers To General Multi-D Uncertainty, Scott A. Starks, Luc Longpre, Roberto Araiza, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

Geospatial databases generally consist of measurements related to points (or pixels in the case of raster data), lines, and polygons. In recent years, the size and complexity of these databases have increased significantly and they often contain duplicate records, i.e., two or more close records representing the same measurement result. In this paper, we address the problem of detecting duplicates in a database consisting of point measurements. As a test case, we use a database of measurements of anomalies in the Earth's gravity field that we have compiled.

In our previous papers, we have proposed a new fast (O(n log(n))) …

Towards Optimal Scheduling For Global Computing Under Probabilistic, Interval, And Fuzzy Uncertainty, With Potential Applications To Bioinformatics, Roberto Araiza, Michela Taufer, Ming-Ying Leung

Departmental Technical Reports (CS)

In many practical situations, in particular in many bioinformatics problems, the amount of required computations is so huge that the only way to perform these computations in reasonable time is to distribute them between multiple processors. The more processors we engage, the faster the resulting computations; thus, in addition to processor exclusively dedicated to this job, systems often use idle time on other processors. The use of these otherwise engaged processors adds additional uncertainty to computations.

How should we schedule the computational tasks so as to achieve the best utilization of the computational resources? Because of the presence of uncertainty, …

Computing Statistical Characteristics When We Know Probabilities With Interval Or Fuzzy Uncertainty: Computational Complexity, Gang Xiang, Jim W. Hall

Departmental Technical Reports (CS)

In traditional statistics, we usually assume that we know the exact probability distributions. In practice, we often only know the probabilities with interval uncertainty.

The main emphasis on taking this uncertainty into account has been on situations in which we know a cumulative distribution function (cdf) with interval uncertainty. However, in some cases, we know the probability density function (pdf) with interval uncertainty. We show that in this situations, the exact range of some statistical characteristics can be efficiently computed. Surprisingly, for some other characteristics, similar statistical problems which are efficiently solvable for interval-valued cdf become computationally difficult (NP-hard) for …

When Are Two Wave Functions Distinguishable: A New Answer To Pauli's Question, With Potential Applications To Quantum Cosmology, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditional quantum mechanics (QM) predicts probabilities of different events. If we describe an elementary particle, then, experimentally, these probabilities mean that if we repeat the same measurement procedure with multiple particles in the same state, the resulting sequence of measurement results will be random w.r.t. the corresponding probability measure. In quantum cosmology, QM is used to describe the world as a whole; we have only one copy of the world, so multiple measurements are impossible. How to interpret these probabilities?

In this paper, we use the approach of the algorithmic information theory to come up with a reasonable interpretation. This …

Interval Computations As An Important Part Of Granular Computing: An Introduction, Vladik Kreinovich

Departmental Technical Reports (CS)

This chapter provides a general introduction to interval computations, especially to interval computations as an important part of granular computing. This introduction is aimed at researchers who would like to learn more - and eventually to use - the main ideas and techniques of granular computing.

We explain how intervals naturally appear in data processing, which techniques exist for processing intervals, and how these techniques have been historically developed.

Generating Linear Temporal Logic Formulas For Pattern-Based Specifications, Salamah Salamah, Vladik Kreinovich, Ann Q. Gates

Departmental Technical Reports (CS)

Software property classifications and patterns, i.e., high-level abstractions that describe program behavior, have been used to assist practitioners in specifying properties. The Specification Pattern System (SPS) provides descriptions of a collection of patterns. Each pattern is associated with a scope that defines the extent of program execution over which a property pattern is considered. Based on a selected pattern, SPS provides a specification for each type of scope in multiple formal languages including Linear Temporal Logic (LTL). The Property Specification tool (Prospec) extends SPS by introducing the notion of Composite Propositions (CP), that classify sequential and concurrent behavior over pattern …

Architectural Assertions: Checking Architectural Constraints At Run-Time, Hyotaeg Jung, Carlos E. Rubio-Medrano, Eric Wong, Yoonsik Cheon

Departmental Technical Reports (CS)

The inability to express architectural concepts and constraints explicitly in implementation code invites the problem of architectural drift and corrosion. We propose runtime checks as a solution to mitigate this problem. The key idea of our approach is to express architectural constraints or properties in an assertion language and use the runtime assertion checker of the assertion language to detect any violations of the constraints. The architectural assertions are written in terms of architectural concepts such as components, connectors, and configurations, and thus they can be easily mapped to or traced back to the original high-level constraints written in an …

Set-Valued Extensions Of Fuzzy Logic: Classification Theorems, Gilbert Ornelas, Vladik Kreinovich

Departmental Technical Reports (CS)

Experts are often not 100% confident in their statements. In traditional fuzzy logic, the expert's degree of confidence in each of his or her statements is described by a number from the interval [0,1]. However, due to similar uncertainty, an expert often cannot describe his or her degree by a single number. It is therefore reasonable to describe this degree by, e.g., a set of numbers. In this paper, we show that under reasonable conditions, the class of such sets coincides either with the class of all 1-point sets (i.e., with the traditional fuzzy set set of all numbers), or …

Under Interval And Fuzzy Uncertainty, Symmetric Markov Chains Are More Difficult To Predict, Roberto Araiza, Gang Xiang, Olga Kosheleva, Damjan Skulj

Departmental Technical Reports (CS)

Markov chains are an important tool for solving practical problems. In particular, Markov chains have been successfully applied in bioinformatics. Traditional statistical tools for processing Markov chains assume that we know the exact probabilities p(i,j) of a transition from the state i to the state j. In reality, we often only know these transition probabilities with interval (or fuzzy) uncertainty. We start the paper with a brief reminder of how the Markov chain formulas can be extended to the cases of such interval and fuzzy uncertainty.

In some practical situations, there is another restriction on the Markov chain--that this Markov …

Fitting A Normal Distribution To Interval And Fuzzy Data, Gang Xiang, Vladik Kreinovich, Scott Ferson

Departmental Technical Reports (CS)

In traditional statistical analysis, if we know that the distribution is normal, then the most popular way to estimate its mean a and standard deviation s from the data sample x1,...,xn is to equate a and s to the arithmetic mean and sample standard deviation of this sample. After this equation, we get the cumulative distribution function F(x)=F0((x-a)/s) of the desired distribution.

In many practical situations, we only know intervals [xi] that contain the actual (unknown) values of xi or, more generally, a fuzzy number that describes xi. Different values of xi lead, in general, to different values of F(x). …

Throttling I/O Streams To Accelerate File-I/O Performance, Seetharami Seelam, Andre Kerstens, Patricia J. Teller

Departmental Technical Reports (CS)

To increase the scale and performance of scientific applications, scientists commonly distribute computation over multiple processors. Often without realizing it, file I/O is parallelized with the computation. An implication of this I/O parallelization is that multiple compute tasks are likely to concurrently access the I/O nodes of an HPC system. When a large number of I/O streams concurrently access an I/O node, I/O performance tends to degrade. In turn, this impacts application execution time.

This paper presents experimental results that show that controlling the number of synchronous file-I/O streams that concurrently access an I/O node can enhance performance. We call …

Von Mises Failure Criterion In Mechanics Of Materials: How To Efficiently Use It Under Interval And Fuzzy Uncertainty, Gang Xiang, Andrzej Pownuk, Olga Kosheleva, Scott A. Starks

Departmental Technical Reports (CS)

One of the main objective of mechanics of materials is to predict when the material experiences fracture (fails), and to prevent this failure. With this objective in mind, it is desirable to use {it ductile} materials, i.e., materials which can sustain large deformations without failure. Von Mises criterion enables us to predict the failure of such ductile materials. To apply this criterion, we need to know the exact stresses applied at different directions. In practice, we only know these stresses with interval or fuzzy uncertainty. In this paper, we describe how we can apply this criterion under such uncertainty, and …

Towards A General Description Of Interval Multiplications: Algebraic Analysis And Its Relation To T-Norms, Olga Kosheleva, Guenter Mayer, Vladik Kreinovich

Departmental Technical Reports (CS)

It is well known that interval computations are very important, both by themselves (as a method for processing data known with interval uncertainty) and as a way to process fuzzy data. In general, the problem of computing the range of a given function under interval uncertainty is computationally difficult (NP-hard). As a result, there exist different methods for estimating such a range: some methods require a longer computation time and lead to more accurate results, other methods lead to somewhat less accurate results but are much faster than the more accurate techniques. In particular, different methods exist for interval multiplication, …

Towards Combining Probabilistic, Interval, Fuzzy Uncertainty, And Constraints: On The Example Of Inverse Problem In Geophysics, George R. Keller, Scott A. Starks, Aaron Velasco, Matthew Averill, Roberto Araiza, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In many real-life situations, we have several types of uncertainty: measurement uncertainty can lead to probabilistic and/or interval uncertainty, expert estimates come with interval and/or fuzzy uncertainty, etc. In many situations, in addition to measurement uncertainty, we have prior knowledge coming from prior data processing, prior knowledge coming from prior interval constraints. In this paper, on the example of the seismic inverse problem, we show how to combine these different types of uncertainty.

Decomposable Aggregability In Population Genetics And Evolutionary Computations: Algorithms And Computational Complexity, Vladik Kreinovich, Max Shpak

Departmental Technical Reports (CS)

Many dynamical systems are decomposably aggregable in the sense that one can divide their (micro)variables x1,...,xn into several (k) non-overlapping blocks and find combinations y1,...,yk of variables from these blocks (macrovariables) whose dynamics depend only on the initial values of the macrovariables. For example, the state of a biological population can be described by listing the frequencies xi of different genotypes i; in this example, the corresponding functions fi(x1,...,xn) describe the effects of mutation, recombination, and natural selection in each generation.

Another example of a system where detecting aggregability is important is a one that describes the dynamics of an …

Why Intervals? Why Fuzzy Numbers? Towards A New Justification, Vladik Kreinovich

Departmental Technical Reports (CS)

The purpose of this paper is to present a new characterization of the set of all intervals (and of the corresponding set of fuzzy numbers). This characterization is based on several natural properties useful in mathematical modeling; the main of these properties is the necessity to be able to combine (fuse) several pieces of knowledge.

Fern: An Updatable Authenticated Dictionary Suitable For Distributed Caching, Eric Freudenthal, David Herrera, Steve Gutstein, Ryan Spring, Luc Longpre

Departmental Technical Reports (CS)

Fern is an updatable cryptographically authenticated dictionary developed to propagate identification and authorization information within and among distributed systems. Conventional authenticated dictionaries permit authorization information to be disseminated by untrusted proxies, however these proxies must maintain full duplicates of the dictionary structure. In contrast, Fern incrementally distributes components of its dictionary as required to satisfy client requests and thus is suitable for deployments where clients are likely to require only a small fraction of a dictionary's contents and connectivity may be limited.

When dictionary components must be obtained remotely, the latency of lookup and validation operations is dominated by communication …

Adding Constraints To Situations When, In Addition To Intervals, We Also Have Partial Information About Probabilities, Martine Ceberio, Vladik Kreinovich, Gang Xiang, Scott Ferson, Cliff Joslyn

Departmental Technical Reports (CS)

In many practical situations, we need to combine probabilistic and interval uncertainty. For example, we need to compute statistics like population mean E=(x1+...+xn)/n or population variance V=(x1^2+...+xn^2)/n-E^2 in the situations when we only know intervals [xi] of possible values of xi. In this case, it is desirable to compute the range of the corresponding characteristic.

Some range computation problems are NP-hard; for these problems, in general, only an enclosure is possible. For other problems, there are efficient algorithms. In many practical situations, we have additional information that can be used as constraints on possible cumulative distribution functions (cdfs). For example, …

Towards Interval Techniques For Processing Educational Data, Olga Kosheleva, Vladik Kreinovich, Luc Longpre, Mourat Tchoshanov, Gang Xiang

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 intervals (e.g., A means anything from 90 to 100). We show that the use of interval techniques leads to more adequate processing of educational data.

Random Test Data Generation For Java Classes Annotated With Jml Specifications, Yoonsik Cheon, Carlos E. Rubio-Medrano

Departmental Technical Reports (CS)

The hidden states of objects create a barrier to designing and generating test data automatically. For example, the state of an object has to be established indirectly through a sequence of method invocations. For a non-trivial class, however, it is extremely unlikely that a randomly-chosen sequence of method invocations can construct an object successfully, as each invocation has to satisfy the state invariants. Nonetheless, automated random testing can reduce the cost of testing dramatically and has potential for finding errors that are difficult to find in other ways because it eliminates the subjectiveness in constructing test data. We propose a …

Three Prosodic Features That Cue Back-Channel Feedback In Northern Mexican Spanish, Anais G. Rivera, Nigel G. Ward

Departmental Technical Reports (CS)

In order to demonstrate attentiveness during a conversation it is generally necessary for the listener to provide back-channel feedback. To some extent, the times when back-channel feedback is welcome are determined by the speaker and conveyed to the listener with prosodic cues. In this study we sought to identify the cues used for this purpose in Northern Mexican Spanish. Based on quantitative analysis of a corpus of unstructured conversations, we found three cues, of which the most common is a pitch downslope followed by a pitch rise accompanied by a rate reduction on the last syllable and a drop in …

On Decision Making Under Interval Uncertainty: A New Justification Of Hurwicz Optimism-Pessimism Approach And Its Use In Group Decision Making, Van Nam Huynh, Chenyi Hu, Yoshiteru Nakamori, Vladik Kreinovich

Departmental Technical Reports (CS)

If we know the exact consequences of each action, then we can select an action with the largest value of the objective function. In practice, we often only know these values with interval uncertainty. If two intervals intersect, then some people may prefer the alternative corresponding to the first interval, and some prefer the alternative corresponding to the second interval. How can we describe the portion of people who select the first alternative? In this paper, we provide a new theoretical justification for Hurwicz optimism-pessimism approach, and we show how this approach can be used in group decision making.

Interval Approach To Preserving Privacy In Statistical Databases: Related Challenges And Algorithms Of Computational Statistics, Luc Longpre, Gang Xiang, Vladik Kreinovich, Eric Freudenthal

Departmental Technical Reports (CS)

In many practical situations, it is important to store large amounts of data and to be able to statistically process the data. A large part of the data is confidential, so while we welcome statistical data processing, we do not want to reveal sensitive individual data. If we allow researchers to ask all kinds of statistical queries, this can lead to violation of people's privacy. A sure-proof way to avoid these privacy violations is to store ranges of values (e.g., between 40 and 50 for age) instead of the actual values. This idea solves the privacy problem, but it leads …

Use Of Deterministic Traffic Assignment Algorithms In Stochastic Networks: Analysis Of Equivalent Link Disutility Functions, Ruey L. Cheu, Vladik Kreinovich

Departmental Technical Reports (CS)

At present, in practice, most traffic assignment tasks are performed by using deterministic network (DN) models, which assume that the link travel time is uniquely determined by the link volume and link capacity. In reality, for the same link volume and link capacity, a link may have different travel times. However, the corresponding stochastic network (SN) models are not widely used because they are much more computationally complex than the DN models. In the past research, it was shown that in the important particular case, when the link travel time follows Gamma distribution, the traffic assignment problem for SN can …