The material in this paper is divided into the following four chapters for convenience. Chapter 1 explains, how the idea of fault testing changed from testing the machine instructions to testing the hardware in logic circuits. Chapters 2, 3 and 4 present the different approaches considered, namely:
1. Path sensitizing...
The purpose of this paper is to discuss some of the theory of Boolean matrices and apply this theory to construct contact networks by using algebraic methods.
The first section of this paper (Chapter I to III) describes Boolean algebra and its properties, the theory of Boolean matrices, and the...
COMPLOT is a versatile set of plot drivers designed to be used
on a Tekterminal, Calcomp, or Hewlett Packard plotter in a time-sharing
environment. Although the hardware aspects of each plotting
device are quite different, COMPLOT allows the plotting devices to
be treated as if they were the same.
The project herein described, presents the results of an investigation
in the relatively new and expanding field of computer stimulated
learning machines for use in pattern recognition.
A learning machine, one that benefits from its past experience
was devised in computer program form. It may be described as a
Piecewise-Linear,...
This paper continues exploration in the area of
programming for parallel computers. The appendix to the
paper contains an extensive survey of the literature related
to parallel computers and parallel programming techniques.
The paper itself presents a new approach to solving
the Laplace equation on a. parallel computer. A new...
This thesis describes a syntax-directed compiler-compiler
called COMCOM which has been implemented by the author on the CDC
3300 under the OS-3 operating system. The theory and terminology
of the parsing method and compiler-compilers in general are briefly
discussed. COMCOM uses Floyd's operator precedence bottom-up
parsing technique which avoids backup...
Specifications for a simulation language capable of modeling
fuzzy systems are presented. Actions occurring in the running
model are to be displayed on a graphics terminal in the .form of
modified E-nets. The concept of partial execution of predicates
is introduced in connection with the underlying continuously valued
logic. Fuzzy...
The well-known local adjustment algorithm for training a
threshold logic unit, TLU, is extended to a local adjustment
algorithm for training a network of TLUs Computer simulations
show that the extension is unsatisfactory.
A new logic for a committee of TLUs, called modified veto logic,
and a local adjustment algorithm...
The design of checking experiments for sequential machines
which do not initially have a distinguishing sequence is investigated.
Improvem,Jnts are suggested to an existing method for
augmenting the output logic so that the machine acquires homogeneous
distinguishing sequences. To indicate how the procedure
may be implemented on a computer, elements...
A radix 2n non-restoring division algorithm is described. The
algorithm is designed to be compatible with hardware multiprecision
multiplication methods currectly used in high speed digital computers.
This enables the use of the same hardware, with only changes in
control logic, to be used to implement both multiplication and
division....
In this thesis we introduce alpha and beta tree acceptors,
generalizations of tree automata. The alpha tree acceptors recognize
a tree by final symbol and the beta tree acceptors by final state. We
show that alpha and beta tree acceptors recognize the same sets of
Gorn trees and demonstrate that...
A review of current computer performance and evaluation techniques reveals a lack of an acceptable analytic tool for optimal computer system performance and evaluation. A generalized approach to the formulation of a third generation computer system model is proposed. The approach is used to optimize computer resource utilization and to...
A cost reduction analysis is performed by coordinating
the exchange of LANDSAT (formerly ERTS) data between a CDC
3300 and a PDP8/L minicomputer. The LANDSAT data is displayed
on a 4002 Tektronix terminal by means of a grayscale output.
Large amounts of data and number manipulation are processed
in the...
The FLEX/REFLEX paradigm is applied to the description of a computer program system. The paradigm is shown to be relevant and appropriate to computer program systems and to advantageously display and structure the general hierarchical characteristics of computer program systems. Program systems characterized in the paradigm are described both holistically...
The concept of a process is often used in connection with operations
of parts of a computer system. This thesis discusses processes
in terms of their use as representations of a physical object or system.
Five primitives are introduced as operators for allowing processes
to be run in a piecemeal...
Interval arithmetic is applied to the problem of obtaining
rigorous solutions to integral equations on a computer. The
integral equations considered are the linear Fredholm equation of
the second kind and the nonlinear Urysohn equation. Techniques are
presented which enable the computer to find an approximate
solution, prove the existence...
MARLA is a collection of FORTRAN routines which
implements the Shannon-type-chess program with alphabeta
cutoffs occurring dynamically. Board positions
are updated incrementally. Also involved in position
analysis is a production system which models the human
chess player's advice-taking, theme, and chess learning
in a general sense. Interfacing these two sections,...
The paper describes research on the representation of knowledge. The goal is to develop a formalism which can be used for the testing of hypotheses on the nature of human understanding and as a foundation or artificial intelligence programs. The ideas expressed herein are implemented in a program which converses...
This paper describes a Lesson Generating System for CAI, which, by relieving the course author from the burden of programming, provides an efficient means for developing courseware to augment classroom instruction.
This paper compares three classes of algorithms for finding
Hamiltonian circuits in graphs. Two of the classes are exhaustive
search procedures and this study finds them to have an exponential
dependence on the size of the graph. The third class of algorithms,
based on Warnsdorff's rule, is found to be...
Contemporary database systems are used in a variety of business applications requiring rapid retrieval of online data. When records contain unique information indexed by a single key, the retrieval operation can be simplified. However, when added generality and flexibility is needed, inverted files and sophisticated data models result in a...
In analyses of multivariate data, a classification of the data into related groups is frequently desired. This is generally referred to as the clustering problem. It has been studied in detail and many clustering algorithms exist. Most of these algorithms, however, require experimenting with the actual data before satisfactory results...
A new system called sequential/parallel matrix grammars
for two-dimensional pattern processing is introduced and studied.
Miscellaneous language operations such as union, catenation (row
and column), Kleene's closure (row and column) and substitutions
are investigated. The equivalence of sequential/parallel matrix
languages and finite-turn repetitive checking automata is established.
Hierarchies for both...
The information processing industry is one of the fastest growing, and most dynamic industries on the scientific as well as business scene, today. Progress in designing and applying computing systems has out raced progress in evaluating their performance. In order to circumvent this trend, there should be a simultaneous development...
This paper describes an investigation of a matrix algebraic method to determine isomorphism in pairs of undirected graphs. The method is described in some detail. The theoretical as well as the practical difficulties are given. It is shown that the method works for some cases. When the adjacency matrix of...
In this work we propose a computer based approach by means of
which the decision maker in Bendel State, Nigeria, can best be assisted
in the formulation of policies related to land use.
In Chapter I we briefly discuss the role of the computer in
planning and state the problem....
Tree systems are used in syntactic pattern recognition for
describing two-dimensional patterns. We extend results on tree
automata with the introduction of the subtree-invariant equivalence
relation R. R relates two trees when the appearance of one implies the
appearance of the other in similar trees. A new state minimizing
algorithm...
Technological advances of the last three decades have caused an enormous increase in the amount of published and unpublished information generated by our society. This inflation has created the need for improved information management systems. Existing systems are inadequate primarily because they are discipline-oriented and lack the flexibility that is...
The need for and problems related to string processing are
discussed and a definition of the term "string" is derived. A
brief review of some existing string processing systems leads
to the presentation of a design for a string processing extension
to the programming language Pascal. A rationale for the...
A digital computer is characterized by the instruction set it executes. Each machine instruction is a bit pattern which is to be interpreted by the central processing unit CPU. The traditional way to interpret a machine instruction is to use random hardware. A contemporary approach is to install a program...
Most measures of program complexity gauge either textual or
control flow attributes of a program. A recent addition to the field
of complexity measures, the knot metric, is a function of both these
attributes. A knot measurement reflects the degree of control-flow
tangle in a program's listing. This thesis discusses...
The general problem of classroom scheduling is well known to be NP-complete. A typical classroom scheduling problem is that of assigning students to a limited number of pieces of laboratory equipment. Frequently several identical pieces of equipment are available only at fixed hours and have limited access due to physical...
This paper demonstrates the effectiveness of a heuristic for
the Traveling Salesman Problem based purely on the efficient
storage of multiple partial sub-tours. The heuristic is among the
best available for the solution of large scale geometric Traveling
Salesman Problems. Additionally, a version of the heuristic can be
used to...
Quickersort, Straight Insertion Sort, Mehlhorn's AVL-tree Sorting Algorithm and Cook's new sorting algorithm are compared on nearly and nedium sorted lists. The ratio of the minimum number of list elements that must be removed so that the remaining portion of the list is in order to the size of the...
This research work investigates the use of production
systems as a model of parallel processing. The purpose of
the model is to provide a suitable medium within which parallel
processing systems can be systematically specified,
analyzed, and designed. Furthermore, the model provides a
suitable means for deriving implementations of synchronization...
An experiment was conducted at Oregon State University to evaluate the effectiveness of Computer Aided Instruction based lessons in a self study environment. The 47 student subjects were assigned to one of three groups: a CAI-EXP group which used a CAI lesson for teaching introductory FORTRAN formatted input and output;...
The methodology of structured programming has
enabled rapid progress in many areas of theoretical
computer science. Structured programs are generally
easier to debug, test, prove and analyse. The development
of these achievements into commercially viable applications
and products has been slower than expected.
The primary reason is that most of...
Historically, coding theory has dealt with binary
codes correcting symmetric errors, in which errors are
made in both 0 and 1 bits with equal likelihood.
Within the past ten years, some study has been made of
asymmetric codes, under the assumption that the only
errors which occur are errors in...
In process control systems where an entire process
is being controlled by a computer, the component tasks of
the system have to be monitored. An efficient message
oriented environment could be an important factor in the
optimization of such systems. In this paper we discuss
the design of a real...
A software system to study network algorithms was implemented on UNIX. Each part of a network algorithm is written as a single C program which becomes a virtual node in the network. During a simulation, all virtualized nodes run as separate processes on a single PDP 11/40. Inter-node communication is...
Why are the fast Fourier transform and the fast
Hadamard transform fast? A transform can be computed by
multiplying a matrix times a vector, which normally requires 0(n²) operations. The matrices corresponding to
these transforms can be rearranged to eliminate redundant
computations resulting in O(nlogn) operations.
We investigate algebraic reasons...
The system described is an interface between a student and a problem-solving production system that solves some class of problems. Its purpose is to help a student learn some part of the realm of problem solving. As a student attempts to solve a problem the system controls the firing of...
A process-resource graph is a directed graph with m
resource nodes and n process nodes. A request edge is
directed from a process to a resource. An assignment edge
is directed from a resource to a process. A cycle in the
process-resource graph is a necessary and sufficient condition for...
A new algorithm, the Horizontal and Vertical Algorithm, for
on-line detection of deadlocks in distributed computer systems, is
presented. Two protocols for implementing the algorithm are given.
The first protocol, the centralized protocol, is based on the
assumption that one site in the network acts as the controller for
global...
Cichelli gave a simple machine independent minimal perfect hashing function for small static sets. The hash function value for a word is computed as the sum of the length of the word and the values associated with the first and last letters of the word. Cichelli's algorithm (word-oriented) to find...
Very High Level Languages (VHLL) provide higher level abstractions and more powerful primitives than high level languages (HLL). A programmer uses these abstractions to solve a problem by specifying "what" is to be done rather than "how" it is to be done. This research work reports the design and development...
An interactive computer graphics package was developed for the
purpose of solving certain geometric problems in the Euclidean plane.
The Geometric Graphics Package provides basic application-independent
functions for creating arbitrary views of two-dimensional objects and
for supporting interaction between the application program and its
user. The application program contains a...
The paper, "On the Duality of Operating System
Structures," by Lauer and Needham [21], claims that
operating systems can be modeled as procedure-oriented or
message-oriented, and that the two models are duals of each
other. Duality, in this case, means that the models are
logically and functionally equivalent, and have...
The minimal kernel for a network data base management
system is developed. It includes format specification for
the object schema and the data base file, and routines for
performing the basic network functions.
The object schema defines the relationship between the
schema, records, sets, and fields. It informs the system...
The objective of this thesis is to develop a tool
which can be used to implement query processing algorithms
produced by a query optimizer. The tool should have the
following properties:
(1) it should support a description of the query solution in a dataflow-like language,
(2) it should support data...
The SEAS Directory and File Manager is a multiple window interactive tool to assist users in modifying and maintaining UNIX files and directories. This tool includes a show directory utility, a show file utility, a type file utility and provides access to the UNIX shell.
The purpose of this project is to design and implement an intermediate language interpreter for a very high level language called Bagit. The Bagit compiler produces Bcode, and this in turn is interpreted by the program described in this report.
A new class of information intensive applications is emerging [Fuch82;
Ohsu82] for which neither Artificial Intelligence (AI) nor Database technologies
alone are well suited. Database systems do not provide the general inferential
capabilities required for problem solving, while AI techniques have not been
adapted to handle massive amounts of structured...
Rapid Prototyping is a technique that has been created to alleviate some of the problems inherent in the traditional approach to software development. Various prototyping techniques currently employed are presented. The user interface aspect of system design is studied and where the benefit of prototyping user interfaces lies is shown....
The need for graphical presentation arises in many disciplines. This thesis describes a prototype software system, the graph creation system, which gives unspecialized users the ability to create and display a variety of graphical figures. Templates for types of graphical figures, and the user interactions for creating instances of a...
Display, which is the function for displaying the
schema of the network at the conceptual level, is implemented
to enhance the network database system ALLEGRO.
To display the schema is one step towards modifiable
schemas in the network model. The problem of updating a
schema is examined at all three...
Allegro is a database management system being built at Oregon State University to provide a vehicle for ongoing research in information systems architecture. The initial Allegro system is a single user environment incorporating a limited network model database management system based on the proposals made by various CODASYL committees. This...
This document describes the design and implementation of a pair of language interfaces to a network database management system. CSDDL provides the DBMS with a data description language facility, and CSDSDL functions as a data storage description language interface of the DBMS. Source languages of CSDDL and CSDSDL are approximately...
Recently several minimal perfect hashing functions far small static word sets have been developed. However, they are limited to sets of 50 words or less. In this paper, a Two Level Minimal Perfect Hash Function for large data sets is given. It partitions a large static set into small sets...
Program understanding is a very important part of the testing and maintenance phases of the programming projects. The overall program knowledge, understanding the various parts of the program, and how they communicate are key steps in understanding the program. Hence data communication among modules contributes much to program complexity and...
This survey looks at five different polygon breaking algorithms and compares them. The criteria for comparison are:
1. Complexity of the algorithm.
2. The number and type of subpolygons produced.
3. The classes of input polygons that can be broken.
The best algorithm is then coded and a comparison is...
University Honors Program Senior Project.
Many times the study of the behavior of an algorithm can be inhibited by the inability to actually see exactly what the algorithm does. Static diagrams and verbal descriptions are often not enough to provide real insight into the behavior of an algorithm. It would...
Conversion of software written for one machine or
operating system to equivalent software for another machine
or operating system is shown to be economically attractive
using source-to-source translation. The features of an
automatic converter are described using a Pascal-to-C
translater as an example. Solutions to the problems of
denesting procedures,...
In von Neumann Languages, side effects occur if one or more non local variables change value(s) during the execution of a procedure or a function. Side effects can occur only if the programming language provides a notion of memory (or state) where the effect will be stored. Side effects complicate...
This paper discusses a new approach to the design of operating systems. We view the jobs or tasks in this system as a number of small independent steps or functions which are sequenced together to produce a desired result. The concepts upon which this operating system is based are drawn...
A decision support system (DSS) incorporating domain
expertise guides, tutors, and consults a decision maker in
opportunity, problem, and crisis identification activities. The
objective for the system is to promote improved decision making.
Using an "Independent Groups" design, an experimental study was
conducted to investigate the effects of DSS use...
In this dissertation we consider the problem of
automating the design of access structures for relational
database systems. The main considerations are effective
and rigorous utilization of the users' usage patterns,
global treatment of the whole design and utilizing most of
the commonly known access structures.
We represent the usage...
Controlling the "complexity" or "understandability"
of computer software is important because of its impact on
program testing and maintenance. Of the large number of
complexity metrics that have been developed to measure the
complexity of a computer program, most assess the
"micro-complexity" of each subprogram and few assess the
"macro-complexity"...
An interactive Computational geometry package was developed
for the purpose of experimenting with geometry problems in
the Euclidean plane. The package also contains computer graphics
functions to display the result. Application independent functions
were developed that are both flexible and general enough for
creating new geometry experiments as well as...
This paper reviews McCabe's cyclomatic complexity and Halstead's laws; it discusses studies in current literature relating the metrics to software. The studies are reproduced using data obtained from a large software project developed in a major electronics firm. Problems that occur when deriving the metrics are discussed; the result of...
Various problems related to systematic error-detecting
and error-correcting unidirectional codes are discussed.
Systematic codes with r check bits are the main topic of
the thesis. Classes of codes are presented which work for
specific numbers of information bits and then a class of
codes is given which detects the same...
QCritic is a rule-based critic for analog bipolar circuits. It functions as a post-processor for the SPICE simulator, making use of netlist, current, and voltage data. The program was written in OPS83, and demonstrates good run-time performance on a VAX 11/780. At present, the system contains rules for analyzing circuits...
Previous research in program understanding has been hampered by the
lack of an easy tool to measure the degree of that understanding. The cloze
procedure, suggested by Cook, Bregar, and Foote (1984) was an attempt to find
a simple, reliable, and valid measure of program understanding. In this
procedure, tokens...
Object files are named active entities (processes) in the UNIX file system graph which provide services. Services are solicited by using the object file's pathname in any system call. Other continuing services can be obtained by opening an object file (which creates an communication path to the object) or by...
Seed-Lab, is a software system for managing seed laboratory information. It was developed at the Oregon State University Seed Testing Laboratory. Seed-Lab was built around a database development package Revelation, which provides its own programming language.
Seed-Lab shields the user from the complexities of database management by supporting menu driven...
The task of inductive learning from examples places constraints on the representation of training instances and concepts. These constraints are different from, and often incompatible with, the constraints placed on the representation by the performance task. This incompatibility is severe when learning functional concepts and explains why previous researchers have...
A rule based transformational model for program development and a metatool based on the above model is presented. The meta-tool can be instantiated to create various program development tools such as tools for building reusable software components, language directed editors, language to language translators, program instrumentation, structured document generator, and...
Allegro is a network database management system being developed at Oregon State University. This project adds a user friendly query facility to the system. The user is presented with pictorial display of the network records and a query interface modeled on the Query-By-Example system. By request the user may be...
An abstract document processing system has been designed, based on the object model of document formatting, which allows users to specify abstract operations directly on the concrete form of objects which compose a document. The result is to restrict the number of operations necessary in document preparation and to minimize...
The Macintosh revolutionary interface sets it apart from all other personal computers. The Macintosh designers made the Macintosh easy to learn, understand, and use.
To ensure correct implementation of their User interface, Apple provided Macintosh programmers with "Inside Macintosh". Inside Macintosh is a complete detailed manual which contains recommendations and...
OSIRIS is an integrated information architecture which was developed at Oregon State University. SIDUR is the data model upon which the semantic level is based. The semantic level is the mediating level between user's information needs and the stored data. The advantages of providing a semantic database environment include flexibility...
A forward-chaining logic programming system (FORLOG) has been developed at Oregon State University. This system coupled with an assumption-based truth maintenance system (ATMS), provides an alternative to the logic programming paradigm of backward-chaining with Horn clauses. To compare FORLOG to this paradigm, we define a subset of FORLOG, called mini-FORLOG,...
Traditional database management systems have been deemed unsuitable for use in the Computer Aided Engineering environment Object-oriented data models with project management features have been proposed as an alternative. The Distributed Hypothetical Storage System is intended to serve as the underlying storage mechanism for an object-oriented data model. The storage...
A translator has been designed and implemented which generates parallel code for a long instruction word parallel computer with local memories. Its main methods are to translate the sequential source code into single assignment, two-operand form, and to then assign the operations to processors so as to minimize the number...
An extensive theory of symmetric error control coding has been developed in the last few decades. The recently developed VLSI circuits, ROM, and RAM memories have given an impetus to the extension of error control coding to include asymmetric and unidirectional types of error control. The maximal numbers of unidirectional...
X2 [4] is a Smalltalk-like programming environment [1]. As it has grown in size and complexity the existing organizational tools have become inadequate for user and system needs. This project addresses this deficiency and some of its important consequences.
The entities to be organized are those that are a fixed...