Digital Commons Network^™

Fast Symmetric Graph Drawing: Theory And Realization, R. T. Pacheco, J. B. Manning

Computer Science Technical Reports

This thesis explores the computational techniques necessary to efficiently realize certain optimal algorithms for the production of drawings which exhibit maximum axial and rotational symmetries of abstract graphs.

The problem of geometric symmetry detection for general graphs has been shown to be NP-complete. However, optimal algorithms have recently been established for the detection of symmetry in trees, outerplanar graphs, and embedded planar graphs. This thesis focuses on the utilization of these algorithms to efficiently produce maximally symmetric drawings of graphs from the classes of symmetric trees and outerplanar graphs.

The construction of symmetric tree drawings is presented first. Following a …

Rapid Display Of Radiographic Images, Jerome R. Cox Jr., Stephen M. Moore, Robert A. Whitman, G. James Blaine, R. Gilbert Jost, L. Magnus Karlsson, Thomas L. Monsees, Gregory L. Hansen, Timothy C. David

All Computer Science and Engineering Research

The requirements for the rapid display of radiographic images exceed the capabilities of widely available display, computer and communication technologies. Computed radiography captures data with a resolution of about four megapixels. Large format displays are available that can present over four megapixels. One megapixel displays are practical for use in combination with large format displays and in areas where the viewing task does not require primary diagnosis. This paper describes an electronic radiology system that approximates the highest quality systems, but through the use of several interesting techniques allows the possibility of its widespread installation throughout hospitals. The techniques uses …

A Robust Approach To Human-Computer Interface Design Using The Taguchi Method, Billie Mitchell Reed

Engineering Management & Systems Engineering Theses & Dissertations

The application of Dr. Genichi Taguchi's approach for design optimization, called Robust Design, to the design of human-computer interface software is investigated. The Taguchi Method is used to select a near optimum set of interface design alternatives to improve user acceptance of the resulting interface software product with minimum sensitivity to uncontrollable noise caused by human behavioral characteristics.

Design alternatives for interaction with personal micro-computers are identified. Several important and representative alternatives are chosen as design parameters for the Taguchi matrix experiment. A noise field with three human behavioral characteristics as noise factors were chosen as a representative noise array. …

Fast Parallel Algorithms For Basic Problems, Zhaofang Wen

Computer Science Theses & Dissertations

Parallel processing is one of the most active research areas these days. We are interested in one aspect of parallel processing, i.e. the design and analysis of parallel algorithms. Here, we focus on non-numerical parallel algorithms for basic combinatorial problems, such as data structures, selection, searching, merging and sorting. The purposes of studying these types of problems are to obtain basic building blocks which will be useful in solving complex problems, and to develop fundamental algorithmic techniques.

In this thesis, we study the following problems: priority queues, multiple search and multiple selection, and reconstruction of a binary tree from its …

An Nc Algorithm For Scheduling Unit-Time Jobs With Arbitrary Release Times And Deadlines, Greg N. Frederickson, Susan H. Rodger

Department of Computer Science Technical Reports

No abstract provided.

Philco: Some Recollections Of The Philco Transac S-2000, Saul Rosen

Department of Computer Science Technical Reports

No abstract provided.

Porting Ncube Packages To Ipsc/860 And Ipsc/2 Hypercubes, Jingwen Wang, Mo Mu

Department of Computer Science Technical Reports

No abstract provided.

Ambivalent Data Structures For Dynamic 2-Edge-Connectivity And K Smallest Spanning Trees, Greg N. Frederickson

Department of Computer Science Technical Reports

No abstract provided.

Negotiating And Supporting Interdependent Data In Very Large Federated Database Systems, Ahmed K. Elmagarmid, James G. Mullen

Department of Computer Science Technical Reports

No abstract provided.

Design And Implementation Of A Distributed System With Dynamic Resource Allocation Based Upon Bidding Schemes, Dan C. Marinescu, Kenneth Wenstrup, Patrick Davis

Department of Computer Science Technical Reports

No abstract provided.

Smili-Visualization Of Asynchronous Massively Parallel Programs, Rashi Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyse the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMil...l (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

Comparison Of Three Axiomatic Systems For Csp, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

Currently software engineering practices use relatively few formal methods. However, formal methods can be used to find errors earlier in the software cycle and hence reduce software cost. One useful formal method is program verification. The axiomatic approach to program verification uses assertions to characterize properties of program variables and relationships between them at various stages of program execution. In order to verify these assertions, axioms or inference rules are needed for each statement as well as some statement-independent inference rules. The message passing and nondeterminism of a distributed programming language present special difficulties. This paper examines and compares three …

Smili-Visualization Of Asynchronous Massively Parallel Programs, Rashi Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyse the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMil...l (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

Comparison Of Three Axiomatic Systems For Csp, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

Currently software engineering practices use relatively few formal methods. However, formal methods can be used to find errors earlier in the software cycle and hence reduce software cost. One useful formal method is program verification. The axiomatic approach to program verification uses assertions to characterize properties of program variables and relationships between them at various stages of program execution. In order to verify these assertions, axioms or inference rules are needed for each statement as well as some statement-independent inference rules. The message passing and nondeterminism of a distributed programming language present special difficulties. This paper examines and compares three …

Performance Experiments And Optimizations Of Pde Sparse Solvers On Hypercubes,, Mo Mu, John R. Rice, Jingwen Wang

Department of Computer Science Technical Reports

No abstract provided.

Fundamental Techniques For Geometric And Solid Modeling, Christoph M. Hoffmann, George Vanĕček

Department of Computer Science Technical Reports

No abstract provided.

A Sixteen-Valued Algorithm For Test Generation In Combinational Circuits, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

A 16-valued logic system for testing combinational circuits is presented. This logic system has been used to develop SIMPLE, an efficient test generation algorithm for single stuck-at faults. The proposed scheme for testing stuck-at faults is based on imposing all the constraints that must be satisfied in order to sensitize a path from a fault site to a primary output. Consequently all deterministic implications are fully considered prior to the enumeration process. The resulting ability to identify inconsistencies prior to enumeration improves the possibility of quicker identification of redundant faults. In order to prune the search space we have introduced …

Corrigendum To "Taxonomies Of Model-Theoretically Defined Topological Properties", Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

An error has been found in the cited paper; namely, Theorem 3.1 is false.

Dna Mapping Algorithms: Abstract Data Types - Concepts And Implementation, Will Gillett, Liz Hanks

All Computer Science and Engineering Research

The conceptual aspects of and the implementation details of a set of self-identifying abstract data types (ADT) are described. Each of the ADTs constitutes a specific class of object, upon which a set of well-defined access functions is available. The intent of these ADTs is to supply a paradigm in which a class of object is available for manipulation, but in which the underlying implementation is hidden from the application programmer. Specific ADTs are the described in some detail. The tagged architecture used to achieve the self-identifying property of the ADTs is presented, and a set of required system-backbone access …

The Difficulty Of Random Attribute Noise, Sally A. Goldman, Robert H. Sloan

All Computer Science and Engineering Research

This paper studies the robustness of pac learning algorithms when the instance space is {0,1}n, and the examples are corrupted by purely random noise affecting only the instances (and not the labels). In the past, conflicting results on this subject have been obtained-- the "best agreement" rule can only tolerate small amounts of noise, yet in some cases large amounts of noise can be tolerated. We show the truth lies somewhere between the two alternatives. For uniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that pac learns monomial …

Computational Learning Theory Lecture Notes For Cs 582 Spring Semester, 1991, Sally A. Goldman

All Computer Science and Engineering Research

This manuscript is a compilation of lecture notes from the graduate level course CS 582, "Computational Learning Theory," I taught at Washington University in the spring of 1991. Students taking the course were assumed to have background in the design and analysis of algorithms as well as good mathematical background. Given that there is no text available on this subject, the course material was drawn from recent research papers. I selected the first twelve topics and the remainder were selected by the students from a list of provided topics. This list of topics is given at the end of these …

A Variable-Free Logic For Mass Terms, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

This paper presents a logic appropriate for mass terms, that is, a logic that does not presuppose interpretation in discrete models. Models may range from atomistic to atomless. This logic is a generalization of the author's work on natural language reasoning. The following claims are made for this logic. First, absence of variables makes it simpler than more conventional formalizations based on predicate logic. Second, capability to deal effectively with discrete terms, and in particular with singular terms, can be added to the logic, making it possible to reason about discrete entities and mass entities in a uniform manner. Third, …

Hidden Markov Model For Visual Guidance Of Robot Motion In Dynamic Environment, Qiuming Zhu

Computer Science Faculty Publications

Models and control strategies for dynamic obstacle avoidance in visual guidance of mobile robot are presented. Characteristics that distinguish the visual computation and motion-control requirements in dynamic environments from that in static environments are discussed. Objectives of the vision and motion planning are formulated as: 1) finding a collision-free trajectory that takes account of any possible motions of obstacles in the local environment; 2) such a trajectory should be consistent with a global goal or plan of the motion; and 3) the robot should move at as high a speed as possible, subject to its kinematic constraints. A stochastic motion-control …

Time Delay Neural Networks And Speech Recognition: Context Independence Of Stops In Different Vowel Environments, Gregory Andrew Makowski

Masters Theses

A series of speech recognition experiments was conducted to investigate time-dynamic speech recognition of stop consonants invariant of vowel environment using data from six talkers. The speech preprocessing was based on previous studies investigating acoustic characteristics which correlate to the place of articulation (Blumstein and Stevens 1979). The place of articulation features were statistically abstracted using four moments and the energy level of the speech sample.

Both statistical and neural network pattern recognition methods were used. Statistical methods included linear and quadratic discriminant functions, maximum likelihood estimator (MLE) and K-nearest neighbors (KNN). The neural network approach used was Time Delay …

A Visualization Model For Massively Parallel Algorithms, R. Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyze the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMILI (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

One-Sided Error Probabalistic Inductive Interface And Reliable Frequency Identification, Efim Kinber, Thomas Zeugmann

School of Computer Science & Engineering Faculty Publications

For EX- and BC-type identification, one-sided error probabilistic inference and reliable frequency identification on sets of functions are introduced. In particular, we relate the one to the other and characterize one-sided error probabilistic inference to exactly coincide with reliable frequency identification, on any setM. Moreover, we show that reliable EX and BC-frequency inference forms a new discrete hierarchy having the breakpoints 1, l/2, l/3, ...

An Ada Based Expert System For The Ada Version Of Satool Ii, Min-Fuh Shyong

Theses and Dissertations

This thesis continues the work of implementing the expert system for the Ada version of SAtool II, an software design requirement analysis tool. The background, history, design process together with the design results and validation of the implementation with Ada and CLIPS/Ada is presented.

Connectionist Expert System With Adaptive Learning Capability, B. T. Low, Hochung Lui, Ah-Hwee Tan, Hoonheng Teh

Research Collection School Of Computing and Information Systems

A neural network expert system called adaptive connectionist expert system (ACES) which will learn adaptively from past experience is described. ACES is based on the neural logic network, which is capable of doing both pattern processing and logical inferencing. The authors discuss two strategies, pattern matching ACES and rule inferencing ACES. The pattern matching ACES makes use of past examples to construct its neural logic network and fine-tunes itself adaptively during its use by further examples supplied. The rule inferencing ACES conceptualizes new rules based on the frequencies of use on the rule-based neural logic network. A new rule could …

A Tale Of Two Mathematicians, Robert Brabenec

ACMS Conference Proceedings 1991

The goal of this paper is to identify some of the discoveries in mathematics during the period from 1820 to 1875 that have profoundly changed the nature of mathematics. To provide a context for this, the author compares some results of mathematics before the year 1820 with those present after 1875. And to humanize this, the author discusses the details of the life and times of two mathematicians, one who was active before 1820 and one who was active after 1875.

Cantor's Concept Of Infinity: Implications Of Infinity For Contingence, Bruce A. Hedman

ACMS Conference Proceedings 1991

Georg Cantor (1845-1918) was a devout Lutheran whose explicit Christian beliefs shaped his philosophy of science. Joseph Dauben has traced the impact Cantor's Christian convictions had on the development of transfinite set theory. In this paper I propose to examine how Cantor's transfinite set theory has contributed to an increasingly contingent world view in modern science. The contingence of scientific theories is not just a cautious tentativeness, but arises out of the actual state of the universe itself. The mathematical entities Cantor studied, transfinite numbers, he admitted were fraught with paradoxes. But he believed that they were grounded in a …