Digital Commons Network^™

A Query-Processing Optimization Strategy For Generalized File Structures, Donna Marie Kaminski

Masters Theses

In processing a Boolean query against a non-inverted file, a subset of the query's keys must be selected. Only the records satisfying these keys need to be retrieved from the file. A dynamic programming algorithm, the Dual-to-minDF, is developed here for arriving at the optimum set of keys, i.e., the minimum number of external record retrievals. Previously suggested greedy methods yield feasible solutions which may or may not be optimal. This algorithm has exponential time complexity. However, it is useful for applications involving relatively short queries with duplication of keys within different conjuncts, and in cases where the files have …

An Improvement In The Performance Of A Learning System For Finite State Machines, Lea F. Fuller

Masters Theses

A learning system is examined which is capable of learning a finite state machine from a class of finite state machines based on the observed behavior of the machine. The size of the search space becomes very large as the number of states in the machine increases. The size of the search space quickly becomes the limiting factor in the size of the class of machines which may be learned. An investigation is made of methods to improve the performance of the learning system. The application of a depth first approach to the development of the search space is shown …

On Symmetry Detection, Mikhail J. Atallah

Department of Computer Science Technical Reports

No abstract provided.

The Importance Of Scaling For The Hermite Bicubic Collocation Equations, Wayne R. Dyksen, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Rcs: A System For Version Control, Walter F. Tichy

Department of Computer Science Technical Reports

No abstract provided.

The Composite Bound Method (Cbm) For Computing Throughput Bounds In Multiple Class Environments, Teemu Kerola

Department of Computer Science Technical Reports

No abstract provided.

Computer Revolution: Another Human Extension, Russell W. Maatman

Pro Rege

No abstract provided.

View-3 And Ada: Tools For Building Systems With Many Tasks, Ann Kratzer, Mark Sherman

Dartmouth Scholarship

This paper discusses some useful features for tools that are intended to be used for developing systems with multiple tasks. We include a description of one tool that has been built, View-3. We also describe some problems that might be encountered when trying to fit this kind of tool into an APSE system.

Rediflow Multiprocessing, Robert M. Keller, Frank C. H. Lin, Jiro Tanaka

All HMC Faculty Publications and Research

We discuss the concepts underlying Rediflow, a multiprocessing system being designed to support concurrent programming through a hybrid model of reduction, dataflow, and von Neumann processes. The techniques of automatic load-balancing in Rediflow are described in some detail.

On Terminal Assignments That Minimize The Density, Mikhail J. Atallah, Susanne E. Hambrusch

Department of Computer Science Technical Reports

No abstract provided.

Simple On The Chip, D. Gannon, J. Panetta

Department of Computer Science Technical Reports

No abstract provided.

Fortran Extensions For Parallel And Vector Computation, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Optimal Rotation Problems In Channel Routing, Mikhail J. Atallah, Susanne E. Hambrusch

Department of Computer Science Technical Reports

No abstract provided.

An Improved Algorithm For Generating Minimal Perfect Hash Functions, Thomas J. Sager

Computer Science Technical Reports

A minimal perfect hash function (MPHF) is a function from a set of M objects to the first M non-negative integers. MPHF's are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language. In this paper we improve on an earlier result and present an algorithm for generating MPHF's with an expected time complexity proportional to M⁴. We also give a MPHF for the 256 most frequently used words in the English language.

Parallelism In The Language, Natural, Thomas J. Sager

Computer Science Technical Reports

Natural is a language designed to provide a vehicle for the expression of abstract programming concepts clearly and precisely in a natural and mathematical form. The concept of parallelism can be expressed both explicitly and implicitly in the language, Natural. Due to relative freedom from side-effects and the use of a special value, undef, subexpressions can often be evaluated in parallel. The for and do statements both allow for a parallel mode of execution. A builtin functional, prlleval, creates functions which can evaluate their arguements in a parallel mode. In addition, the concept of module allows for the definition of …

A New Method For Generating Minimal Perfect Hash Functions, Thomas J. Sager

Computer Science Technical Reports

A perfect hash function, PHF, is an injection, F, from a set, W, of M objects into the set consisting of the first N non-negative integers where N>=M. If N=M then F is a minimal perfect hash function, MPHF. PHFs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language.

The mincycle algorithm for finding PHFs executes with an expected time complexity proportional to M⁴ and has been used successfully on sets of cardinality up to 256. The mincycle …

An Analysis Of The Use Of Rademacher-Walsh Spectrum In Compact Testing, Ten-Chuan Hsiao, Sharad C. Seth

School of Computing: Faculty Publications

Earlier approaches to random compact testing use a random pattern generator which depends on the combinational function under test and a circuit signature which remains the same independent of the circuit. In this correspondence we analyze the performance of a new scheme in which the pattern generator is simple and independent of the function being tested but the circuit signature is chosen to be a coefficient from the Rademacher-Walsh (RW) spectrum of the function under test. The analysis provides guidelines for choosing an RW coefficient, a test length, and an error tolerance so as to minimize the probabilities of rejecting …

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Π_k-formulae of size n for which every Σ_k-formula has size exp Ω(n^1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σ_k-formula of size exp O(n^1/(k-1)). Thus our hierarchy theorem is the best possible.

Consistency Testing For Data-Flow Circuits, Chu S. Jhon, Robert M. Keller

All HMC Faculty Publications and Research

One means of making VLSI design tractable is to proceed from a high-level specification of a circuit in terms of functionality, to the circuit level. A notable error which may occur in a topdown design starting with a data-flow graph representation of a circuit is a design inconsistency due to deadlock. This paper attempts to further develop the theoretical basis for algorithms which analyze the deadlock property of circuits on the basis of their data-flow graph representations. A systematic scheme to verify the absence of deadlock in data-flow graphs is also presented.

A Graphical Representation Of An Executing Program, Sherry A. Lile

Masters Theses

"This thesis describes the rationale for a computer program used as a teaching aid, as well as, the design, development, and implementation of that computer program. The program is a prototype that displays, line by line, a graphical depiction of a BASIC program being executed. Icons are used to represent FOR-NEXT loops, the contents of variables, I/O, and other programming elements. The internal logic associated with the Arithmetic-Logic Unit is also represented. The purpose is to produce an environment where the student may visualize the processes occurring in memory by viewing a symbolic portrayal of an executing program. The example …

Incompleteness, Negation, Hazard: On The Precariousness Of Systems, Martin Zwick

Complex Systems Faculty Publications and Presentations

An account is offered of the dialectical tensions which afflict systems of widely differing type, "contradictions" which cannot be fully or permanently resolved, and from which follow the lawfulness of both hazard and opportunity.

An Experimental Study Of The Effects Of Modularity On Resource Consumption In Software Development, Alan D. Christiansen

Masters Theses

"Many authors have encouraged the use of modular programming techniques in software development. In fact, there is almost total agreement within industrial and academic circles that modularity is a desirable feature of any software package. Unfortunately, the desirability of modular design is almost always voiced without support from experimental evidence.

This thesis consists of an experiment comparing the resource consumption of programmers based on the modularity practices employed during the design and programming phases of software development. The experiment tests the effectiveness of modularity in reducing psychological complexity of software.

The results of the research show that in some cases …

The Optimal Trajectory Modelling Of Robot Manipulators, Mary Claire Miller

Masters Theses

"Greater robot capability can be achieved through the use of robot manipulator control systems. Crucial to the success of these control systems is the optimal trajectory modelling of the path traced by the end- effector. To create this optimal path the utilization of B-Spline curve functions will be investigated, and compared to Cubic Spline curve functions"--Abstract, page ii.

The Design And Implementation Of The Programming Language Natural, Alan L. Sparks

Masters Theses

"This paper reports progress on the development of the programming language Natural, currently under design by Dr. Thomas J. Sager at the University of Missouri--Rolla. Natural is a very high-level language with a mathematical flavor, and includes several concepts relatively uncommon in programming language design.

The text also discusses an implementation on the IBM Personal Computer of Mini-Natural, a subset of Natural, and presents examples of programs written in Mini-Natural"--Abstract, page ii.

A Simple Method For Organizing Nearly Optimal Binary Search Trees, Joy L. Henderson

Masters Theses

"Improving the efficiency of retrieving information concerns users of computer systems involved in many applications- One way of addressing this concern is to organize a sorted sequence into a binary search tree. Knuth's Algorithm K is a bottom-up organization algorithm that always constructs a binary tree which minimizes average search time. However, the cost of executing Algorithm K is prohibitive for a large tree. The aim of this work is to find a less costly method of organizing sorted sequences into nearly-optimal binary search trees.

We present a top-down organization method which yields better average search times than top-down methods …

Survey Of Routing Algorithms For Computer Networks, Lu Yu

Masters Theses

"This thesis gives a general discussion of routing for computer networks, followed by an overview of a number of typical routing algorithms used or reported in the past few years. Attention is mainly focused on distributed adaptive routing algorithms for packet switching (or message switching) networks. Algorithms for major commercial networks (or network architectures) are reviewed as well, for the convenience of comparison"--Abstract, page ii.

Program Modeling And Control Synthesis For Robotic Manipulators, Ramiz Najib Ballou

Masters Theses

"The control and programming methodology of industrial robots is becoming increasingly important. The speed and accuracy of data generation, and the performance of the robot are considered the most important factors in robotics control.

This paper presents and discusses algorithms that solve for the inverse solution for a given point in space at a very high speed based on the top down abstract method. The algorithms are independent of any specific type of manipulator configuration or programming language. The algorithms were implemented or the IBM-PC using the FORTRAN language to control the Armdroid robot. The program generates 500 sets of …

Ciegen: A System For Testing Knowledge Base Compilation Heuristics On A Microcomputer, Jayne D. Ward

Masters Theses

"The expert system has proven itself to be a valuable aid in diagnosing and treating problems in domains requiring expertise. The commercial world has been alerted to this fact and the thrust is to make the expert system portable and available on small computers.

The goal of this research has been to lay the groundwork for a domain independent expert system builder on a microcomputer. The result of this effort was CIEGEN, a system consisting of a rule compiler, inference engine, and rule generator developed on the IBM PC. It is domain independent, responsible for transforming a knowledge base of …

A Focus Of Attention Algorithm For Expert Systems, Kevin W. Whiting

Masters Theses

"This research is primarily concerned with increasing the performance of expert systems. A refined focus of attention strategy and its affect on performance are discussed. Early expert systems used a brute force approach to process the knowledge base. Each production rule in the knowledge base was evaluated each cycle. More recently, processing efficiency has been increased by focusing the attention of the inference engine on a subset of the rules by "filtering" for further testing, only rules that could possibly fire given the current content of the context base. Focus of attention as developed in this research increases performance over …

Toward A Normative Computer-Aided Contingency Planning Protocol, Peter H. Aiken

Theses and Dissertations

This thesis effort is an investigation into the subject of contingency planning.

Increases in the number of organizations operating in "turbulent environments" have highlighted deficiencies in planning methodologies which attempt to base continued organizational survival upon a single course of action. In these instances, organizations experience an increase in the number of variables and possible events for which they must be prepared. Traditional contingency planning efforts attempt to prepare the organization for the occurrence of events that are foreseen deviations from "the master plan". When operating in turbulent environments, organizations must plan to move quickly through a series of differing …