Digital Commons Network^™

Simulations Between Programs As Cellular Automata, Howard A. Blair, Fred Dushin, Polar Humenn

Electrical Engineering and Computer Science - Technical Reports

We present cellular automata on appropriate digraphs and show that any covered normal logic program is a cellular automaton. Seeing programs as cellular automata shifts attention from classes of Herbrand models to orbits of Herbrand interpretations. Orbits capture both the declarative, model-theoretic meaning of programs as well as their inferential behavior. Logically and intentionally different programs can produce orbits that simulate each other. Simple examples of such behavior are compellingly exhibited with space-time diagrams of the programs as cellular automata. Construing a program as a cellular automaton leads to a general method for simulating any covered program with a Horn …

Designing Dependencies, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

Given a binary recursively enumerable relation R, one or more logic programs over a language L can be constructed and interconnected to produce a dependency relation D on selected predicates within the Herbrand base BL of L isomorphic to R. D can be, optionally, a positive, negative or mixed dependency relation. The construction is applied to representing any effective game of the type introduced by Gurevich and Harrington, which they used to prove Rabin's decision method for S2S, as the dependency relation of a logic program. We allow games over an infinite alphabet of possible moves. We use this representation …

Secure Trapdoor Hash Functions Based On Public-Key Cryptosystems, Gary R. Greenfield, Sarah Agnes Spence

Department of Math & Statistics Technical Report Series

In this paper we systematically consider examples representative of the various families of public-key cryptosystems to see if it would be possible to incorporate them into trapdoor hash functions, and we attempt to evaluate the resulting strengths and weaknesses of the functions we are able to construct. We are motivated by the following question:

Question 1.2 How likely is it that the discoverer of a heretofore unknown public-key cryptosystem could subvert it for use in a plausible secure trapdoor hash algorithm?

In subsequent sections, our investigations will lead to a variety of constructions and bring to light the non-adaptability of …

Bit-Sequences: A New Cache Invalidation Method In Mobile Environments, Jin Jing, Ahmed K. Elmagarmid, Abdelsalam Helal, Rafael Alonso

Department of Computer Science Technical Reports

No abstract provided.

Inverse Pattern Matching, Amihood Amir, Alberto Apostolico, Moshe Lewenstein

Department of Computer Science Technical Reports

No abstract provided.

Migrant Threads On Process Farms: Parallel Programming With Ariadne*, Edward Mascarenhas, Vernon Rego

Department of Computer Science Technical Reports

No abstract provided.

Lightweight Write Detection And Checkpointing For Fine-Grained Persistence, Antony L. Hosking, J. Eliot B. Moss

Department of Computer Science Technical Reports

No abstract provided.

The New Jersey Machine-Code Toolkit, Norman Ramsey, Mary F. Fernáyesndez

Department of Computer Science Technical Reports

No abstract provided.

Sliced Configuration Spaces For Curved Planar Bodies, Elisha Sacks, Chandrajit Bajaj

Department of Computer Science Technical Reports

No abstract provided.

Kenematic Tolerance Analysis, Leo Joskowicz, Elisha Sacks, Vijay Srinivasan

Department of Computer Science Technical Reports

No abstract provided.

Partitioned Data Management In Mobile Environments, Ahmed K. Elmagarmid, Jin Jing, Abdelsalam Helal, Rafael Alonso

Department of Computer Science Technical Reports

No abstract provided.

Pattern Matching Image Compression: Algorithmic And Empirical Results, Mikhail J. Atallah, Yann Génin, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Simulation Modeling Within Workflow Technology, John A. Miller, Amit P. Sheth, Krzysztof J. Kochut, Xuzhong Wang, Arun Murugan

Kno.e.sis Publications

This paper presents an approach for integrating simulation modeling and analysis capabilities within the workflow management system (WFMS) being developed in the Large Scale Distributed Information Systems (LSDIS) Lab at the University of Georgia. Simulation modeling can be used for studying the efficiency of workflow designs as well as studying the general performance and reliability of WFMSs. We also discuss the importance of using sophisticated monitoring and animation capabilities, and the use of workflow management technology to advance simulation technology itself. Finally, we demonstrate a sample simulation where tasks and task managers are simulated.

Adaptive Methods For Distributed Video Presentation, Crispin Cowan, Shanwei Cen, Jonathan Walpole, Carlton Pu

Computer Science Faculty Publications and Presentations

This paper describes problems and solutions for delivering real-time, multi-media presentations across the Internet. A key characteristic of presentations of continuous media datatypes, such as digital video and audio, is their need for predictable real-time data delivery. For example, an NTSC quality video presentation requires video frames to be displayed every 1/30th of a second. Variations in this display rate can be observable as stalls or glitches in the video stream and reduce the quality of the presentation [6]. Delivering such presentations across the Internet is difficult because highly variable band- width and latency make it difficult to predict the …

Dynamics Of Binary Liquids In Pores, J.C. Lee

Faculty Publications

A computer simulation is performed to study the dynamics of binary liquids in the pores of Vycor glasses. The pores are modeled with glass walls that form randomly interconnected tunnels. When the relaxation is probed with a particular wavelength, the time autocorrelation function depends on whether or not there is a significant periodic or quasiperiodic structure in the distribution of the walls with that wavelength. If there is not, the relaxation may be fitted as the sum of an exponential term and a nonexponential activated term. If there is, the relaxation shows a long-lasting tail that can be fitted by …

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh

Computer Science: Faculty Publications and Other Works

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of "congestion" and "dilation" measures for a set of packet paths. We give, for any constant ϵ > 0, a randomized on-line algorithm for routing any set of Npackets in O((C lg^ϵ(Nd) + D lg(Nd))/lg lg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into …

A 2-2/3 Approximation For The Shortest Superstring Problem, Chris Armen, Clifford Stein

Computer Science Technical Reports

Given a collection of strings S={s_1, ..., s_n} over an alphabet \Sigma, a superstring \alpha of S is a string containing each s_i as a substring; that is, for each i, 1<=i<=n, \alpha contains a block of |s_i| consecutive characters that match s_i exactly. The shortest superstring problem is the problem of finding a superstring \alpha of minimum length. The shortest superstring problem has applications in both data compression and computational biology. In data compression, the problem is a part of a general model of string compression proposed by Gallant, Maier and Storer (JCSS '80). Much of the recent interest in the problem is due to its application to DNA sequence assembly. The problem has been shown to be NP-hard; in fact, it was shown by Blum et al.(JACM '94) to be MAX SNP-hard. The first O(1)-approximation was also due to Blum et al., who gave an algorithm that always returns a superstring no more than 3 times the length of an optimal solution. Several researchers have published results that improve on the approximation ratio; of these, the best previous result is our algorithm ShortString, which achieves a 2 3/4-approximation (WADS '95). We present our new algorithm, G-ShortString, which achieves a ratio of 2 2/3. It generalizes the ShortString algorithm, but the analysis differs substantially from that of ShortString. Our previous work identified classes of strings that have a nested periodic structure, and which must be present in the worst case for our algorithms. We introduced machinery to descibe these strings and proved strong structural properties about them. In this paper we extend this study to strings that exhibit a more relaxed form of the same structure, and we use this understanding to obtain our improved result.

Information Retrieval, Information Structure, And Information Agents, Daniela Rus, Devika Subramanian

Computer Science Technical Reports

This paper presents a customizable architecture for software agents that capture and access information in large, heterogeneous, distributed electronic repositories. The key idea is to exploit underlying structure at various levels of granularity to build high-level indices with task-specific interpretations. Information agents construct such indices and are configured as a network of reusable modules called structure detectors and segmenters. We illustrate our architecture with the design and implementation of smart information filters in two contexts: retrieving stock market data from Internet newsgroups, and retrieving technical reports from Internet ftp sites.

An Api For Choreographing Data Accesses, Elizabeth A.M. Shriver, Leonard F. Wisniewski

Computer Science Technical Reports

Current APIs for multiprocessor multi-disk file systems are not easy to use in developing out-of-core algorithms that choreograph parallel data accesses. Consequently, the efficiency of these algorithms is hard to achieve in practice. We address this deficiency by specifying an API that includes data-access primitives for data choreography. With our API, the programmer can easily access specific blocks from each disk in a single operation, thereby fully utilizing the parallelism of the underlying storage system. Our API supports the development of libraries of commonly-used higher-level routines such as matrix-matrix addition, matrix-matrix multiplication, and BMMC (bit-matrix-multiply/complement) permutations. We illustrate our API …

Intelligent Multimedia Tutoring For Manufacturing Education, Erika Rogers, Yolanda Kennedy, T. Walton, P. Nelms, I. Sherry

Computer Science and Software Engineering

This paper describes current work on the design and implementation of intelligent multimedia tutoring modules which are intended to supplement short training courses in Nondestructive Inspection for the Boeing Defense and Space group.

Multimedia In Manufacturing Education Mime, Chris Thompson, Laurie Hodges, Wayne Daley, Erika Rogers

Computer Science and Software Engineering

This paper describes a project funded by the Technology Reinvestment Project (TRP) under the manufacturing education component (MET) to design, build, and evaluate interactive multimedia courseware for manufacturing education. Interactive multimedia is defined as the combination of computer based text, sound, graphics, animation, video, and simulation, commercial and defense industries along with a professional society are collaborating on the project in an effort to address important dual-use issues. Advanced media technologies are being exploited to create virtual, time shifted, and/or remote visits to real world manufacturing systems. The foundations for our efforts and the experiences in the first year of …

Using Passion System On Lu Factorization, Haluk Rahmi Topcuoglu, Alok Choudhary

Electrical Engineering and Computer Science - Technical Reports

Parallel I/0 subsystems are added to massively parallel computers in order to lessen I/0 bottleneck to some extent. Up to now, a few number of parallel software systems have been designed and implemented to assist programmers in I/0 intensive applications; PASSION is one of them. By providing parallel I/0 support at the language, compiler and run-time level, PASSION system explores the large design space of parallel systems. The target of this paper is to show the performance benefits of using PASSION I/0 libraries at runtime in comparison with using conventional parallel I/0 primitives for high performance parallel I/0 in LU …

A Simple Solver For Linear Equations Containing Nonlinear Operators, Norman Ramsey

Department of Computer Science Technical Reports

No abstract provided.

Blending Basic Implicit Shapes Using Trivariate Box Splines, Jörg Peters, Michael Wittman

Department of Computer Science Technical Reports

No abstract provided.

Complexity Of Sequential Pattern Matching Algorithms, Mireille Régnier, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Multi-View Access Protcols For Large-Scale Replication, Xiangning (Sean) Liu, Abdelsalam (Sumi) Helal, Bharat K. Bhargava

Department of Computer Science Technical Reports

No abstract provided.

Optimal P-Cyclic Sor For Complex Spectra, S. Galanis, A. Hadjidimos, D. Noutsos

Department of Computer Science Technical Reports

No abstract provided.

Sequence Alignment In Molecular Biology, Alberto Apostolico, Raffaele Fiancarlo

Department of Computer Science Technical Reports

No abstract provided.

Intelligent Control Of Vehicles: Preliminary Results On The Application Of Learning Automata Techniques To Automated Highway System, Cem Unsal, John S. Bay, Pushkin Kachroo

Electrical & Computer Engineering Faculty Research

We suggest an intelligent controller for an automated vehicle to plan its own trajectory based on sensor and communication data received. Our intelligent controller is based on an artificial intelligence technique called learning stochastic automata. The automaton can learn the best possible action to avoid collisions using the data received from on-board sensors. The system has the advantage of being able to work in unmodeled stochastic environments. Simulations for the lateral control of a vehicle using this AI method provides encouraging results.

Measurement Of The Bs0 Lifetime And Production Rate With Ds- ℓ+ Combinations In Z Decays, D. Buskulic, M. Thulasidas

Research Collection School Of Computing and Information Systems

A precise determination of the effective Bs0→K+K− lifetime can be used to constrain contributions from physics beyond the Standard Model in the Bs0 meson system. Conventional approaches select B meson decay products that are significantly displaced from the B meson production vertex. As a consequence, B mesons with low decay times are suppressed, introducing a bias to the decay time spectrum which must be corrected. This analysis uses a technique that explicitly avoids a lifetime bias by using a neural network based trigger and event selection. Using 1.0fb−1 of data recorded by the LHCb experiment, the effective Bs0→K+K− lifetime is …