Computer Sciences Commons^™

Functional Reasoning And Functional Modelling, J. Sticklen, William E. Bond

Computer Science Faculty Research & Creative Works

A car that will not start on a cold winter day and one that will not start on a hot summer day usually indicate two very different situations. When pressed to explain the difference, we would give a winter account- "Oil is more viscous in cold conditions, and that causes . . .'' -and a summer story- "Vapor lock is a possibility in hot weather and is usually caused by . . .'' How do we build such explanations? One possibility is that understanding how the car works as a device gives us a basis for generating the explanations. But …

Robot Pedagogics: The Adaptation, Analysis, And Computer Control Of A Model Manipulator, Edward T. Hammerand, Chung You Ho

Computer Science Technical Reports

The subject of robotics is addressed by many different fields, among them computer science, electrical engineering, and mechanical engineering. This work is an attempt to bring together all of these aspects from the perspective of a computer science background. Different techniques are considered and reconciled with one another in the analytical area, while detail and explanation are added in all areas that were not previously available. In addition, geometrical interpretations arc presented for concepts that have heretofore been presented only in the form of equations.

Parallel Implementation Of A Recursive Least Squares Neural Network Training Method On The Intel Ipsc/2, James Edward Steck, Bruce M. Mcmillin, K. Krishnamurthy, M. Reza Ashouri, Gary G. Leininger

Computer Science Faculty Research & Creative Works

An algorithm based on the Marquardt-Levenberg least-square optimization method has been shown by S. Kollias and D. Anastassiou (IEEE Trans. on Circuits Syst. vol.36, no.8, p.1092-101, Aug. 1989) to be a much more efficient training method than gradient descent, when applied to some small feedforward neural networks. Yet, for many applications, the increase in computational complexity of the method outweighs any gain in learning rate obtained over current training methods. However, the least-squares method can be more efficiently implemented on parallel architectures than standard methods. This is demonstrated by comparing computation times and learning rates for the least-squares method implemented …

A Direct Access Method Using A Neural Network Model, John William Meyer, George Winston Zobrist

Computer Science Technical Reports

One of the concerns in computer science involves optimizing usage of machines to make them more efficient and cost effective. One item of particular concern is the use of secondary storage devices, devices that store data other than in the main memory of the computer to which it is attached. The times for searching for data on these devices consistently proves to be a contributing factor in inefficient computer usage.

One data access method that avoids searching when possible is the hashing method. A function is defined to return the record number of a record based on its key field. …

Input Data Pattern Encoding For Neural Net Algorithms, Hyeoncheol Kim, George Winston Zobrist

Computer Science Technical Reports

First, a brief overview of neural networks and their applications are described, including the BAM (Bidirectional Associative Memory) model.

A bucket-weight-matrix scheme is proposed, which is a data pattern encoding method that is necessary to transform a set of real-world numbers into neural network state numbers without losing the pattern property the set has. The scheme is designed as a neural net so that it can be combined with other data processing neural nets. The net itself can be used as a bucket-sorting net also. This shows that traditional data structure problems can be an area that neural networks may …

Algorithms And Probabilistic Bounds For The Chromatic Number Of Random Composite Graphs, Jack L. Oakes, Billy E. Gillett

Computer Science Technical Reports

The composite graph coloring problem (CGCP) is a generalization of the standard graph coloring problem (SGCP). Associated with each vertex is a positive integer called its chromaticity. The chromaticity of a vertex specifies the number of consecutive colors which must be assigned to it.

An exact algorithm for solving the CGCP is presented. The algorithm is a generalization of the vertex-sequential with dynamic reordering approach for the SGCP. It is shown that the method is as effective on composite graphs as its counterpart is on standard graphs. Let X̅(CG_np) and X̅(SG_np) denote, respectively, the mean chromatic …

A Fast O(K) Multicast Message Routing Algorithm, Thomas J. Sager, Bruce M. Mcmillin

Computer Science Technical Reports

In many multicomputer applications is it necessary for one node to send an identical message to many nodes. One to many communications are called multicasts. Although broadcasts (one to all) and unicasts (one to one) have been widely implemented, multicasts, in spite of their importance to efficient use of multicomputer systems, have not received much attention.

Minimal traffic multicasting is equivalent to the minimal Steiner tree problem and is known to be NP-complete. Therefore, a heuristic polynomial time approximation must be used; but, to take advantage of advances in second generation multicomputer hardware such as wormhole routing, a distributed multicast …

Computational Complexity Of Geometric Symmetry Detection In Graphs, Joseph Manning

Computer Science Technical Reports

Constructing a visually informative drawing of an abstract graph is a problem of considerable practical importance, and has recently been the focus of much investigation. Displaying symmetry has emerged as one of the foremost criteria for achieving good drawings. Linear-time algorithms are already known for the detection and display of symmetry in trees, outerplanar graphs, and embedded planar graphs. The central results of this paper show that for general graphs, however, detecting the presence of even a single axial or rotational symmetry is NP-complete. A number of related results are also established, including the #P-completeness of counting the axial or …

Highland: A Graph-Based Parallel Processing Environment For Heterogeneous Local Area Networks, Ralph W. Wilkerson, Douglas E. Meyer

Computer Science Faculty Research & Creative Works

No abstract provided.

Computational Intelligence In Cad/Cam Applications, Chaman Sabharwal, Thomas G. Melson, Martin D. Fraser

Computer Science Faculty Research & Creative Works

This paper presents a fundamental, direct, and powerful approach to the surface/surface intersection problem in CAD/CAM applications. The algorithm is designed and implemented in three steps: a) Preprocessing- locate the potentially intersecting sections of the surfaces and decompose the surfaces into surface elements within specified flatness tolerance; b) Intersection- decompose the possibly intersecting pairs of surface elements into continuous surface triangulations to find the approximate intersections between the pairs of surface elements; c) Postprocessing-assemble the intersection primitives into curves of intersection, refine the accuracy of computed intersection points, and compact the intersection curves. This surface/surface intersection algorithm is applicable to …

Role Of Term Symmetry In E-Completion Procedures, Ralph W. Wilkerson, Blayne E. Mayfield

Computer Science Faculty Research & Creative Works

No abstract provided.

Dawgs - A Distributed Compute Server Utilizing Idle Workstations, Henry Clark, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

A collection of powerful workstations interconnected by a local area network can be utilized as compute servers when left idle by their owners. DAWGS allows users to submit jobs for execution on an idle workstation somewhere on a local area network. DAWGS uses a distributed scheduler and a bidding scheme to determine on which machine to run a process. DAWGS can properly redirect all the I/O of a remotely executing process and can checkpoint and then subsequently restart the process, even if the restart is on a different machine than the checkpoint. Our method is different from other work in …

Distributed Evaluation Of An Iterative Function For All Object Pairs On A Simd Hypercube, Fikret Erçal

Computer Science Faculty Research & Creative Works

An efficient distributed algorithm for evaluating an iterative function on all pairwise combinations of C objects on an SIMD hypercube is presented. The algorithm achieves uniform load distribution and minimal, completely local interprocessor communication.

Experimentation With Large-Grained Parallelism Using Local Area Networks, Ralph W. Wilkerson, Douglas E. Meyer

Computer Science Faculty Research & Creative Works

HIGHLAND, a distributed-memory parallel processing environment for heterogeneous local area networks, has been developed. Designed as both a teaching and a research tool, its purpose is to provide an effective mechanism by which a number of networked UNIX workstations, dissimilar in both vendor and performance, can be directly manipulated as a single, unified, multiprocessing system. Utilizing the MIT X-windows environment, HIGHLAND supports a highly interactive graphical interface through which a programmer can create, modify, and control complex systems of communicating processes

Experimental Comparison Of Bidding And Drafting Load Sharing Protocols, Andrew Ross, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

In recent years, a dramatic rise in the number of personal workstations interconnected via local area networks has occurred in the workplace. These can be organized as distributed computing systems. The combined computing power of these systems are often greater than mainframes of a decade ago, and usually less expensive. There is a growing interest in harnessing this often-underutilized power. Researchers are focusing their attention on remote execution of processes as one solution. An additional topic of research is to balance a workload among a series of computers. Remote execution is made possible because the distributed operating system provides migration …

An Expert System To Convert Knowledge-Based Geological Engineering Systems Into Fortran, Ralph W. Wilkerson, Jill J. Cress

Computer Science Faculty Research & Creative Works

A knowledge-based geographic information system (KBGIS) for geological engineering map (GEM) production was developed in GoldWorks, an expert system development shell. Using this shell, the geological engineer is able to develop a rule base for a particular application that results in a valid GEM. However, this implementation failed as a practical production system due to the excessive execution time required to produce a GEM. To solve this problem, a conversion expert system was developed which accepted, as input, a KBGIS and produced, as output, the equivalent Fortran code. Two major objectives are accomplished as a result of this system: GEN …

Development Of An Expert System To Convert Knowledge-Based Geological Engineering Systems Into Fortran, Jill J. Cress, Ralph W. Wilkerson

Computer Science Technical Reports

A knowledge-based geographic information system (KBGIS) for geological engineering map (GEM) production was developed in GoldWorks, an expert system development shell. GoldWorks allows the geological engineer to develop a rule base for a GEM application. Implementation of the resultant rule base produced a valid GEM, but took too much time. This proved that knowledge-based GEM production was possible but in GoldWorks implementation failed as a practical production system. To solve this problem, a Conversion Expert System was developed which accepted, as input, a KBGIS and produced, as output, the equivalent Fortran code. This allowed the engineer to utilize GoldWorks for …

The Directed Steiner Problem On Graphs: A Simulated Annealing Approach, Lawrence Joseph Osborne, Billy E. Gillett

Computer Science Technical Reports

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 …

Automated Translation Of Digital Logic Equations Into Optimized Vhdl Code, John Evan Stark, George Winston Zobrist

Computer Science Technical Reports

It was desired to develop an algorithm for the automated translation of finite slate machines from state table form to optimized VHDL form. To do this, algorithms arc needed for reducing the state machine to simplest form, making state assignments, producing minimal logic equations to represent the state machine, and producing VHDL code which describes the intended circuit. Various such algorithms were examined and a prototype program written to perform this translation.

An Improved Exact Graph Coloring Algorithm, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

We present two algorithms for exact graph coloring of the vertex sequential with dynamic reordering of vertices variety. The first, W-DEG, is a straight-forward improvement on Korman’s original algorithm. The second, SWAP2, is a not so straight forward improvement on Korman’s algorithm and appears to offer the best performance of known exact graph coloring algorithms.

A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

DEXCH, a color-exchange exact graph coloring algorithm is presented. On many classes of graphs, DEXCH can, in the mean, find the chromatic number of a graph considerably faster than the DSATUR algorithm. The improvement over DSATUR stems from the ability to reorganize the subset of colored vertices and to detect in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far. The mean improvement over DSATUR is greatest on high edge-density graphs attaining the value of 42% on random graphs of edge-density 0.7 on 64 vertices.

A Pruning Procedure For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

The graph coloring problem can be stated: “Given an undirected graph, using a minimal number of colors, assign each vertex a color so that if two vertices are connected by an edge then they are not assigned the same color.” Graph coloring can be used to solve scheduling problems with constraints of the form: events e and e' can not be scheduled together. Graph coloring is an NP-Complete problem. Generally large problems are solved heuristically, although some of the better heuristic algorithms use an exact graph coloring algorithm to finish coloring a graph after first reducing it heuristically …

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.

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 …

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.

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 …

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.

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.

Automated Translation Of Digital Logic Equations Into Optimized Vhdl Code, John Evan Stark

Masters Theses

"It was desired to develop an algorithm for the automated translation of' finite slate machines from state table form to optimized VHDL form. To do this, algorithms arc needed for reducing the state machine to simplest form, making state assignments, producing minimal logic equations to represent the state machine, and producing VHDL code which describes the intended circuit. Various such algorithms were examined and a prototype program written to perform this translation"--Abstract, page ii.

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 …