Computer Sciences Commons^™

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 …

Symbolic Automation And Numerical Synthesis For Robot Kinematics, Jen Sriwattanathamma, Chung You Ho

Computer Science Technical Reports

This research analyzes three topics in robot arm kinematics. First, the direct kinematics which determines the Cartesian position and orientation of the end effector for the specified values of joint parameters is analyzed. Second, the differential motions concerning the differential relationships between the command variables in position and orientation of the end effector and the joint-controlled variables are studied. Finally, the inverse kinematics which determines the joint variables for a specified Cartesian position and orientation of the end effector is considered.

This dissertation presents a methodology for incorporating the artificial intelligence types of knowledge into automating solutions for the direct …

A Parallel Implementation Of Stickel's Ac Unification Algorithm In A Message-Passing Environment, David John Kleikamp, Ralph W. Wilkerson

Computer Science Technical Reports

Unification algorithms are an essential component of automated reasoning and term rewriting systems. Unification finds a set of substitutions or unifiers that, when applied to variables in two or more terms, make those terms identical or equivalent. Most systems use Robinson's unification algorithm or some variant of it. However, terms containing functions exhibiting properties such as associativity and commutativity may be made equivalent without appearing identical. Systems employing Robinson's unification algorithm must use some mechanism separate from the unification algorithm to reason with such functions. Often this is done by incorporating the properties into a rule base and generating equivalent …

A System For The Diagnosis Of Faults Using A First Principles Approach, Barbara A. Smith, Ralph W. Wilkerson

Computer Science Technical Reports

One of the primary areas of application of Artificial Intelligence is diagnosis. Diagnosis from first principles is a diagnostic technique which uses knowledge of the designed structure and function of a device to determine the possible causes of the malfunction.

This work builds on the foundation of a theory of diagnosis by implementing and extending the theory. A correction to the algorithm which defines the theory is presented. The theory is extended for multiple sets of observations of the system and measurement data.

A fundamental problem in diagnosis is selecting the measurement which will be of the most benefit in …

The Ipe-Pc Integrated Programming Environment, Nurcan Coskun, Thomas J. Sager

Computer Science Technical Reports

An Integrated Programming Environment, IPE-PC, that supports pseudo-code development has been designed and implemented. This environment is based on a Pascal-like language which is designed according to the requirements of a language-based environment. The nucleus of IPE-PC is a language-based editor which represents programs as graphs internally. The same representation is used in every mode of the environment (i.e., editing, compilation, execution, debugging and translation). The system provides facilities to take advantage of both top-down and bottom-up programming. Stepwise refinement has been supported by providing comment structures that can be transformed into procedures. Bottom-up programming is supported because it is …

Composite Graph Coloring Algorithms And Applications, Stephen Hong Seng Yek, Billy E. Gillett

Computer Science Technical Reports

A vertex-composite graph is a graph that can have unequal chromaticities on its vertices. Vertex-composite graph coloring or composite graph coloring involves coloring each vertex of a composite graph with consecutive colors according to the vertex's chromaticity with no two vertices adjacent to one another having the same color(s).

New heuristic algorithms including the use of the saturation degree method have been developed in this research. All eleven heuristic algorithms including Clementson and Elphick algorithms were then tested using random composite graphs with five different chromaticity distributions. The best algorithm which uses the least average colors from the experiment is …

Complete Sets Of Reductions Modulo A Class Of Equational Theories Which Generate Infinite Congruence Classes, Timothy B. Baird, Ralph W. Wilkerson

Computer Science Technical Reports

In this paper we present a generalization of the Knuth-Bendix procedure for generating a complete set of reductions modulo an equational theory. Previous such completion procedures have been restricted to equational theories which generate finite congruence classes. The distinguishing feature of this work is that we are able to generate complete sets of reductions for some equational theories which generate infinite congruence classes. In particular, we are able to handle the class of equational theories which contain the associative, commutative, and identity laws for one or more operators.

We first generalize the notion of rewriting modulo an equational theory to …

The Role Of Term Symmetry In E-Unification And E-Completion, Blayne E. Mayfield, Ralph W. Wilkerson

Computer Science Technical Reports

A major portion of the work and time involved in completing an incomplete set of reductions using an E-completion procedure such as the one described by Knuth and Bendix [070] or its extension to associative-commutative equational theories as described by Peterson and Stickel [PS81] is spent calculating critical pairs and subsequently testing them for coherence. A pruning technique which removes from consideration those critical pairs that represent redundant or superfluous information, either before, during, or after their calculation, can therefore make a marked difference in the run time and efficiency of an E-completion procedure to which it is applied.

The …

Automated Circuit Diagnosis Using First Order Logic Tools, Barbara Smith, Ralph W. Wilkerson, Gerald E. Peterson, Mcdonnell Douglas

Computer Science Faculty Research & Creative Works

While Numerous Diagnostic Expert Systems Have Been Successfully Developed in Recent Years, They Are Almost Uniformly based on Heuristic Reasoning Techniques (I.e., Shallow Knowledge) in the Form of Rules. This Paper Reports on an Automated Circuit Diagnostic Tool based on Reiter's Theory of Diagnosis. in Particular, this is a Theory of Diagnosis based on Deep Knowledge (I.e., Knowledge based on Certain Design Information) and using First Order Logic as the Representation Language. the Inference Mechanism Which is Incorporated as Part of the Diagnostic Tool is a Refutation based Theorem Prover using Rewriting Systems for Boolean Algebra Developed by Hsiang. Consequently, …

Computer Control Of A Pbx Washout Plant, Scott Cameron Sharp, Chung You Ho

Computer Science Technical Reports

A fully automated, computer controlled plant has been designed specifically for safe removal of plastic bonded explosives (PBX) from obsolete military munitions. This PBX washout plant consists of a two stage delivery system and robotically operated high pressure waterjet lance. The assigned task was to develop control packages for each component.

The first stage of the delivery system is a battery operated overhead trolley. Its control package consist of a dedicated computer, DC motor and custom positioning subprograms. The dedicated computer communicates through an infrared link to the operator's computer. This link was developed due to requirements of a hazardous …

Micro Database Management System Language, Karen Yingling Tam, George Winston Zobrist

Computer Science Technical Reports

There are two approaches to solve computational problems in a microcomputer environment:

1. Non-database approach: uses a high level programming language with non-database files as input and/or output files.
2. Database approach: uses the programming language embedded in the micro Data Base Management System(DBMS), with the database defined by the integrated database definition language as input and/or output files.

Adopting the appropriate approach in any single application may save cost and time. This paper compares the two different approaches while solving the same Control Section (CSECT) Interaction Hierarchy problem and suggests which to use when.

Deduction Of A Functional Dependency From A Set Of Functional Dependencies, James M. Richardson, Daniel C. St. Clair

Computer Science Technical Reports

This paper describes an algorithm called the Deduction Tracing Algorithm (DTA) which utilizes basic properties of functional dependencies from database systems and a modification of a tree search algorithm from artificial intelligence. The algorithm takes a set of functional dependencies, F, along with a specific functional dependency L → R as input and produces a list of functional dependencies from F that can be used to deduce L → R. The resulting algorithm is easily automated to provide relational database users with a tool for organizing their queries.

Intensity Blending Of Computer Image Generation-Based Displays, Elizabeth Scheppler Reidelberger, Daniel C. St. Clair

Computer Science Technical Reports

State-of-the-art combat simulators require a 360 degree field of view, allowing the pilot and radar intercept officer to have the same visibility in the simulator that they would experience in the aircraft. The sky/earth display must be computer - generated and displayed with a minimum of two channels to provide the most realistic display possible. The two channels of display come together in the dome, forming an equator, that must be as indiscernible to the aircrew as possible. To accomplish this, an algorithm has been developed for controlling the video output which makes the two separate channel displays appear as …

Implementation Of Cross Intersection Between Triangular Surfaces, Chaman Sabharwal, Thomas G. Melson

Computer Science Faculty Research & Creative Works

No abstract provided.

An Inherently Parallel Large Grained Data Flow Environment, Roger E. Eggen, John R. Metzner

Computer Science Faculty Research & Creative Works

A parallel programming environment based on data flow is described. Programming in the environment involves use with an interactive graphic editor which facilitates the construction of a program graph consisting of modules, ports, paths and triggers. Parallelism is inherent since data presence allows many modules to execute concurrently. The graph is executed directly without transformation to traditional representations. The environment supports programming at a very high level as opposed to parallelism at the individual instruction level.

Executable Assertion Development For The Distributed Parallel Environment, Bruce M. Mcmillin, L. M. Ni

Computer Science Faculty Research & Creative Works

The use of executable assertions is a powerful tool with which to perform program verification, provide software fault-tolerance, and provide hardware fault-tolerance via the application-oriented paradigm. The authors show that assertions commonly used in the sequential programming environment are inadequate for the distributed parallel environment. In particular, it is shown that even design-based assertions are myopic and provide inadequate error coverage. In their place, a triad of basic metrics is proposed for certain classes of problems that, when applied beginning with the specification phase of the life cycle, produce assertions that are better suited to the parallel environment. This method …

Composite Graph Coloring Algorithms And Applications, Stephen Hong Seng Yek

Masters Theses

"A vertex-composite graph is a graph that can have unequal chromaticities on its vertices. Vertex-composite graph coloring or composite graph coloring involves coloring each vertex of a composite graph with consecutive colors according to the vertex's chromaticity with no two vertices adjacent to one another having the same color(s).

New heuristic algorithms including the use of the saturation degree method have been developed in this research. All eleven heuristic algorithms including Clementson and Elphick algorithms were then tested using random composite graphs with five different chromaticity distributions. The best algorithm which uses the least average colors from the experiment is …

Knowledge Organization And Inference Engine For The Wvu Face Decision Support System, S. Carrow, R. S. Nutter Jr., R. S. Raman, N. A. Reddy, Y. V. Reddy, R. Larry Grayson

Mining Engineering Faculty Research & Creative Works

The knowledge-based organization for the West Virginia University Face Decision Support System is given, along with the initial development of the associated inference engine. The knowledge base contains generic knowledge about underground coal mines that utilize continuous miners. A typical knowledge entry is given, and the inference engine methodology is explained. The engine utilizes this knowledge with data from monitoring systems and from interaction with the section foreman, to assist in making section management decisions and plans.

Fractals With Arbitrary Segment Lengths, Daniel Michael Doerer

Masters Theses

"Work in the area of fractal geometry has generally focused on a specific facet of the discipline at the expense of other interesting features. This approach often generates more questions than answers for the general audience due to the lack of unification across all views. It appears that a common thread to relate all aspects of fractal characteristics is missing. This paper addresses this question and presents some new and fascinating results. For example, in-depth mathematical analysis often defers to the intriguing and attractive graphical displays produced by mapping the complex plane to the pixel field on a CRT. Both …

Intensity Blending Of Computer Image Generation-Based Displays, Elizabeth Scheppler Reidelberger

Masters Theses

"State-of-the-art combat simulators require a 360 degree field of view, allowing the pilot and radar intercept officer to have the same visibility in the simulator that they would experience in the aircraft. The sky/earth display must be computer - generated and displayed with a minimum of two channels to provide the most realistic display possible. The two channels of display come together in the dome, forming an equator, that must be as indiscernible to the aircrew as possible. To accomplish this, an algorithm has been developed for controlling the video output which makes the two separate channel displays appear as …

Deduction Of A Functional Dependency From A Set Of Functional Dependencies, James M. Richardson

Masters Theses

"This paper describes an algorithm called the Deduction Tracing Algorithm (DTA) which utilizes basic properties of functional dependencies from database systems and a modification of a tree search algorithm from artificial intelligence. The algorithm takes a set of functional dependencies, F, along with a specific functional dependency L→R as input and produces a list of functional dependencies from F that can be used to deduce L→R. The resulting algorithm is easily automated to provide relational database users with a tool for organizing their queries"--Abstract, page iii.

Micro Database Management System Language, Karen Yingling Tam

Masters Theses

"There are two approaches to solve computational problems in a microcomputer environment:

1. Non-database approach: uses a high level programming language with non-database files as input and/or output files.
2. Database approach: uses the programming language embedded in the micro Data Base Management System(DBMS), with the database defined by the integrated database definition language as input and/or output files.

Adopting the appropriate approach in any single application may save cost and time. This paper compares the two different approaches while solving the same Control Section (CSECT) Interaction Hierarchy problem and suggests which to use when"--Abstract, page ii.

Computer Control Of A Pbx Washout Plant, Scott Cameron Sharp

Masters Theses

"A fully automated, computer controlled plant has been designed specifically for safe removal of plastic bonded explosives (PBX) from obsolete military munitions. This PBX washout plant consists of a two stage delivery system and robotically operated high pressure waterjet lance. The assigned task was to develop control packages for each component.

The first stage of the delivery system is a battery operated overhead trolley. Its control package consist of a dedicated computer, DC motor and custom positioning subprograms. The dedicated computer communicates through an infrared link to the operator's computer. This link was developed due to requirements of a hazardous …

A Parallel Implementation Of Stickel's Ac Unification Algorithm In A Message-Passing Environment, David John Kleikamp

Masters Theses

"Unification algorithms are an essential component of automated reasoning and term rewriting systems. Unification finds a set of substitutions or unifiers that, when applied to variables in two or more terms, make those terms identical or equivalent. Most systems use Robinson's unification algorithm or some variant of it. However, terms containing functions exhibiting properties such as associativity and commutativity may be made equivalent without appearing identical. Systems employing Robinson's unification algorithm must use some mechanism separate from the unification algorithm to reason with such functions. Often this is done by incorporating the properties into a rule base and generating equivalent …

An Integrated Programming Environment For Pseudo-Code Development, Ipe-Pc, Nurcan Coskun

Doctoral Dissertations

"An Integrated Programming Environment, IPE-PC, that supports pseudo-code development has been designed and implemented. This environment is based on a Pascal-like language which is designed according to the requirements of a language-based environment. The nucleus of IPE-PC is a language-based editor which represents programs as graphs internally. The same representation is used in every mode of the environment (i.e., editing, compilation, execution, debugging and translation). The system provides facilities to take advantage of both top-down and bottom-up programming. Stepwise refinement has been supported by providing comment structures that can be transformed into procedures. Bottom-up programming is supported because it is …

Symbolic Automation And Numerical Synthesis For Robot Kinematics, Jen Sriwattanathamma

Doctoral Dissertations

"This research analyzes three topics in robot arm kinematics. First, the direct kinematics which determines the Cartesian position and orientation of the end effector for the specified values of joint parameters is analyzed. Second, the differential motions concerning the differential relationships between the command variables in position and orientation of the end effector and the joint-controlled variables are studied. Finally, the inverse kinematics which determines the joint variables for a specified Cartesian position and orientation of the end effector is considered.

This dissertation presents a methodology for incorporating the artificial intelligence types of knowledge into automating solutions for the direct …

The Role Of Term Symmetry In E-Unification And E-Completion, Blayne E. Mayfield

Doctoral Dissertations

“A major portion of the work and time involved in completing an incomplete set of reductions using an E-completion procedure such as the one described by Knuth and Bendix [KB70] or its extension to associative-commutative equational theories as described by Peterson and Stickel [PS81] is spent calculating critical pairs and subsequently testing them for coherence. A pruning technique which removes from consideration those critical pairs that represent redundant or superfluous information, either before, during, or after their calculation, can therefore make a marked difference in the run time and efficiency of an E-completion procedure to which it is applied.

The …

Multilist And Inverted File System Performance Measurements, Ashok Chandramouli, George Winston Zobrist

Computer Science Technical Reports

This study evaluates the multilist and inverted file systems. It describes the structure of the two file system and then proceeds to investigate the performance. The performance is based on quantitative estimates of space requirements for file system, time to retrieve records, time to insert a record, time to delete a record, time to update a record and time to exhaustively read and reorganize the file system. The study then investigates specific situations in which one file system seems to perform better than the other.

Performance Parameter Measurements Of Generic Files, Sankarraman Subramanian, George Winston Zobrist

Computer Science Technical Reports

This study discusses the performance parameter measurements of generic files, the pile file, the sequential file, the indexed-sequential file, the indexed file and the direct file. The file performance measurements are compiled in a software package. The study then describes the use of such software package as a simulation tool in a file design environment.

Heuristic Coloring Algorithm For The Composite Graph Coloring Problem, Johnnie C. Roberts, Billy E. Gillett

Computer Science Technical Reports

A composite graph is a finite undirected graph in which a positive integer known as a chromaticity is associated with each vertex of the graph. The composite graph coloring problem (CGCP) is the problem of finding the chromatic number of a composite graph, i.e., the minimum number of colors (positive integers) required to assign a sequence of consecutive colors to each vertex of the graph in a manner such that adjacent vertices are not assigned sequences with colors in common and the sequence assigned to a vertex has the number of colors indicated by the chromaticity of the vertex. The …