Physical Sciences and Mathematics Commons^™

Graph Coloring Algorithms On Random Graphs, Shi-Jen Lin

Doctoral Dissertations

"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes …

The Directed Steiner Problem On Graphs: A Simulated Annealing Approach, Lawrence Joseph Osborne

Doctoral Dissertations

"The well-known Steiner Problem on Graphs is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. In this dissertation a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. A version of annealing is developed for the Directed Steiner Problem and compared with one of the best general annealing schemes. Then a comparison is made between simulated annealing and the traditional branch and bound technique. The dual ascent algorithm of Richard T. Wong is used to …

Flower : Predicting Flowering Times Of Cereal Crops, G A B Elliott, Stephen Loss

Journal of the Department of Agriculture, Western Australia, Series 4

FLOWER is a computer program which predicts the flowering date of a given wheat or barley variety at a specified location and sowing date. Department of Agriculture agronomists, breeders and advisers are using the program to provide useful information on how the development of cereals responds to different environments across Western Australia's cereal growing areas.

Adaptation Of Lr Parsing To Production System Interpretation, Louis Paul Slothouber

Dissertations, Theses, and Masters Projects

This thesis presents such a new production system architecture, called a palimpsest parser, that adapts LR parsing technology to the process of controlled production system interpretation. Two unique characteristics of this architecture facilitate the construction and execution of large production systems: the rate at which productions fire is independent of production system size, and the modularity inherent in production systems is preserved and enhanced. In addition, individual productions may be evaluated in either a forward or backward direction, production systems can be integrated with other production systems and procedural programs, and production system modules can be compiled into libraries and …

Reliable Distributed Sorting Through The Application-Oriented Fault Tolerance Paradigm, Bruce M. Mcmillin, L. M. Ni

Computer Science Faculty Research & Creative Works

The design and implementation of a reliable version of the distributed bitonic sorting algorithm using the application-oriented fault tolerance paradigm on a commercial multicomputer is described. Sorting assertions in general are discussed and the bitonic sort algorithm is introduced. Faulty behavior is discussed and a fault-tolerant parallel bitonic sort developed using this paradigm is presented. The error coverage and the response of the fault-tolerant algorithm to faulty behavior are presented. Both asymptotic complexity and the results of run-time experimental measurements on an Ncube multicomputer are given. The authors demonstrate that the application-oriented fault tolerance paradigm is applicable to problems of …

Expectations For Associative-Commutative Unification Speedups In A Multicomputer Environment, Ralph W. Wilkerson, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

An essential element of automated deduction systems is unification algorithms which identify general substitutions and when applied to two expressions, make them identical. However, functions which are associative and commutative, such as the usual addition and multiplication functions, often arise in term rewriting systems, program verification, the theory of abstract data types and logic programming. The introduction to the associative and commutative equality axioms together with standard unification brings with it problems of termination and unreasonably large search spaces. One way around these problems is to remove the troublesome axioms from the system and to employ a unification algorithm which …

A Definition Optimization Technique Used In A Code Translation Algorithm, David M. Dejean, George Winston Zobrist

Computer Science Faculty Research & Creative Works

Data flow analysis is used to optimize variable definitions in a program that translates microprocessor object code to a higher order language. © 1989, ACM. All rights reserved.

Fault Diagnosis Using First Order Logic Tools, Ralph W. Wilkerson, Barbara A. Smith

Computer Science Faculty Research & Creative Works

An automated circuit diagnostic tool implementing R. Reiter's theory of diagnosis (1987) based on deep knowledge (i.e. knowledge based on certain design information) and using first-order logic as the representation language is discussed. In this approach, the automated diagnostician uses a description of the system structure and observations describing its performance to determine if any faults are apparent. If there is evidence that the system is faulty, the diagnostician uses the system description and observations to ascertain which component(s) would explain the behavior. In particular, Reiter's method finds all combinations of components which explain this behavior.

An Investigation Into The Use Of Prolog For Chinese-English Translation, J. W. L. Millar

Research outputs pre 2011

In order to undertake machine translation from Chinese to English, it is necessary to accomplish three tasks. Firstly, the Chinese characters need to be handled on the computer system in use - in this case an IBM PC/XT. Secondly, the grammar for the language has to be represented and here Prolog has been used with a Definite Clause Grammar. Finally, the lexicon must be stored in a manner that facilitates efficient retrieval. Arity Prolog provides a hash table that achieves this task. This report describes the current state of a project aimed at producing a Chinese English machine translation system.

The Next Generation Of Internetworking, Gurudatta M. Parulkar

All Computer Science and Engineering Research

This paper describes a research effort concerned with the design of the next generation of internet architecture, which has been necessitated by two emerging trends. First, there will be at least a few orders of magnitude increase in data rates of communication networks in the next few years. For example, researchers are already prototyping networks with data rates of up to a few hundred Mbps, and are planning networks with data rates up to a few Gbps. Second, researchers from all disciplines of science, engineering, and humanities plan to use the communication infrastructure to access widely distributed resources in order …

An Inexpensive Electronic Viewbox, J. R. Cox Jr., R. G. Jost, T. Monsees, S. Ramamurthy, M. Karlsson

All Computer Science and Engineering Research

An "electronic viewbox" is described that has been designed to meet the demand for a modestly priced soft-copy display for radiology. Issues associated with spatial resolution, intensity resolution, image magnification, user interface, digital communications and possible applications are discussed.

Signal Probabilities In And-Or Trees, Lester Lipsky, Sharad C. Seth

School of Computing: Faculty Publications

In this paper, we consider a class of AND-OR tree circuits and study their response to random-pattern inputs as the depth of the tree is allowed to increase indefinitely. Each binary input of a circuit is independently chosen to be one (zero) with probability x (1 - x). The logic of the circuit determines the probability of success (one) at the output as a monotonically increasing S-shaped function of x called the probability transfer function. The probability transfer function of an AND-OR tree is shown to have just one interior fixed point (w.r.t. changes in depth of …

Design Of Parity Testable Combinational Circuits, Bhargab B. Bhattacharya, Sharad C. Seth

School of Computing: Faculty Publications

The parity testability of a single output is related to its partition in terms of maximal supergates and then a scheme is proposed for making an untestable circuit parity testable by augmenting its maximal supergates. Only a small amount of extra logic and a single external test-mode pin is required to complete the design. The test procedure is simple and the hardware overhead is low.

A Theory Of Testability With Application To Fault Coverage Analysis, Sharad C. Seth, Vishwani Agrawal, Hassan Farhat

School of Computing: Faculty Publications

When test vectors are applied to a circuit, the fault coverage increases. The rate of increase, however, could be circuit-dependent. In fact, the actual rise of fault coverage depends on the characteristics of vectors, as well as, on the circuit. The paper shows that the average fault coverage can be computed from circuit testability. A relationship between fault coverage and circuit testability is derived. The mathematical formulation allows computation of coverage for deterministic and random vectors. Applications of this analysis include: determination of circuit testability from fault simulation, coverage prediction from testability analysis, prediction of test length, and test generation …

Testability Analysis Of Synchronous Sequential Circuits Based On Structural Data, Raghu V. Hudli, Sharad C. Seth

School of Computing: Faculty Publications

Bounds on test sequence length can be used as a testability measure. We give a procedure to compute the upper bound on test sequence length for an arbitrary sequential circuit. We prove that the bound is exact for a certain class of circuits. Three design rules are specified to yield circuits with lower test sequence bounds.

Personal Computing For The Visually Impaired, Bruce M. Mcmillin, P. Y. Mcmillin

Computer Science Faculty Research & Creative Works

The problem of providing feedback from the computer to a visually impaired user is examined. The use of traditional tactile input and output (Braille) is described. The limitations of voice output are discussed, and difficulties posed by complicated screen formats and screen review are considered.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, January 1989, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …

Automatically Generating Functional Tests From Specifications - A Knowledge Based Constraint Logical Programming Approach, Ji Chen

Computer Science Theses & Dissertations

Recent experimental results indicate that functional testing is one of the most effective methods in detecting certain classes of faults. Very little work has been done in automating functional testing. This thesis research develops a method, called hierarchical partition, for automating functional testing. The key to our approach is the utilization of a pre-existing knowledge base about the domain of discourse. Several approaches to knowledge organiza­tion are discussed along with the resulting effects on the quantity and quality of functional tests produced. This research is an application and development of Generic Constraint Logic Programming and the Knowledge Driven …

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

A Microcomputer-Based Cia System Designed To Compliment Traditional Instruction In Navy Technical Training, John M. Kaiser

CCE Theses and Dissertations

A prototype microcomputer-based CBI program was developed to provide review, structured self-study, and remediation to students undergoing initial skills training at the Naval Air Technical Training Center (NATTC), Lakehurst, NJ. The program demonstrates the capabilities of the authoring (LSAUT) and delivery (LSSTU) programs that are parts of the Language Skills Computer Aided Instruction (LSCAI) system developed by the Navy Personnel Research and Development Center and the University of Utah. A course of instruction at NATTC, Lakehurst was selected for this project on the basis of level of training, student throughput, attrition and setback rates, and category of learning objectives. Student …

Evaluation Of Concurrent Pools, David Kotz, Carla Ellis

Dartmouth Scholarship

The assignment of resources or tasks to processors in a distributed or parallel system needs to be done in a fashion that helps to balance the load and scales to large configurations. In an architectural model that distinguishes between local and remote data access, it is important to base these allocation functions on a mechanism that preserves locality and avoids high-latency remote references. This paper explores performance considerations affecting the design of such a mechanism, the Concurrent Pools data structure. We evaluate the effectiveness of three different implementations of concurrent pools under a variety of stressful workloads. Our experiments expose …

Edge Contours, Donna J. Williams

Retrospective Theses and Dissertations

The accuracy with which a computer vision system is able to identify objects in an image is heavily dependent upon the accuracy of the low level processes that identify which points lie on the edges of an object. In order to remove noise and fine texture from an image, it is usually smoothed before edge detection is performed. This smoothing causes edges to be displaced from their actual location in the image. Knowledge about the changes that occur with different degrees of smoothing (scales) and the physical conditions that cause these changes is essential to proper interpretation of the results …

Weak Bipolarizable Graphs, Stephan Olariu

Computer Science Faculty Publications

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.

Euclidean Traveling Salesman Heuristics, Ron Greenberg, Cindy Phillips, Joel Wein

Computer Science: Faculty Publications and Other Works

No abstract provided.

Teacher Utilization Of A Middle School Media Program: A Case Study, Earnestine T. Mccloud

CCE Theses and Dissertations

The goal of this research study was to determine the effectiveness of the media center within the school environment. The components of the media center program that should be strengthened were identified. The role of the media center, teachers, and staff in facilitating media center goals and objectives were evaluated.

Permission to survey teachers of the Lemmel Middle School was granted by the assistant Superintendent of Planning and Research. The letter of introduction, the questionnaire, directions for completing the questionnaire, and self-addressed, return envelopes were placed in the teachers' mailboxes.

To facilitate in the processing of the questionnaires, the data …

Interactive Simulations For Knowledge Acquisition, Sorel Bosan

Dissertations, Theses, and Masters Projects

No abstract provided.

Safe Computing, Bruce M. Mcmillin, T. L. Casavant

Computer Science Faculty Research & Creative Works

So-called worms, viruses, and Trojan horses that attack computer systems are defined. The vehicle that allows these attacks to occur, namely, the open computer internetwork, is examined. The problem of providing protection against attack in an internetwork environment is discussed. The need for professional responsibility on the part of the scientific and engineering community in enforcing strong ethical practices and neither tolerating nor condoning such practices is stressed.

Small-Kernel Image Restoration, Stephen Edward Reichenbach

Dissertations, Theses, and Masters Projects

The goal of image restoration is to remove degradations that are introduced during image acquisition and display. Although image restoration is a difficult task that requires considerable computation, in many applications the processing must be performed significantly faster than is possible with traditional algorithms implemented on conventional serial architectures. as demonstrated in this dissertation, digital image restoration can be efficiently implemented by convolving an image with a small kernel. Small-kernel convolution is a local operation that requires relatively little processing and can be easily implemented in parallel. A small-kernel technique must compromise effectiveness for efficiency, but if the kernel values …

A New Conjecture About Minimal Imperfect Graphs, H. Meyniel, Stephan Olariu

Computer Science Faculty Publications

H. Meyniel proved that in every minimal imperfect graph, every pair of vertices is joined by a chordless path containing an odd number of edges. We conjectured that in every minimal imperfect graph, every pair of vertices is joined by a path containing an even number of edges. We give an equivalent version of this new conjecture.