A general model of interactive problem solving is described. The model views interactive problem solving to be the product of cooperating subsystems. The operative subsystem selectively attends to and manipulates problem relevant information in search of a solution. The descriptive subsystem is capable of interpreting this behavior and of discussing...
A tour of a graph (digraph, or sequential machine) is a sequence of nodes from the graph such that each node appears at least once and two nodes are adjacent in the sequence only if they are adjacent in the graph. Finding the shortest tour. of a graph is known...
G. Spencer Brown's book Laws of Form has been enjoying a vogue among social and biological scientists. Proponents claim that the book introduces a new logic ideally suited to their fields of study, and that the new logic solves the problems of self-reference. These claims are false. We show that...
An operator calculus for transforming assignment statements, loops, and choice constructs into equation-of-state expressions is shown to be powerful enough to synthetically execute a given computer program and its test data. A demonstration of the program is equivalent to applying an operator formalism to the equation-of-state in order to reduce...
Microprogramming has evolved since its introduction in 1951 by Maurice Wilkes. The most significant change that has taken place is the recent growth of interest in user microprogramming. However, user microprogramming is a difficult task because of various complex and intricate features of the host processors. A microprogrammer must be...
Context-free grammars with graph control provide a general framework for the various types of context-free grammars with regulated rewriting. The vertices or edges of the directed graph are labeled with the productions of the grammar. The only strings in the language generated by the grammar are those whose derivations correspond...
Recently several simply computed graph theoretic measures of computer program complexity, testing and unstructuredness have been proposed. Most of them are based on a static analysis of the program graph. One of the best known and most widely accepted is the cyclomatic number. Another is the number of knots, or...
A graph fold is the special case of a graph homomorphism where the two identified vertices are both adjacent to a common vertex. Like homomorphisms, folds are related to the chromatic number and we obtain an Interpolation Theorem for folds. If X(G) = n, then G is absolutely n-chromatic if...
Local stability seems to imply global stability for population models. To investigate this claim, we formally define a population model. This definition seems to include the one-dimensional discrete models now in use. We derive a necessary and sufficient condition for the global stability of our defined class of models. We...
This monograph presents a proof grammar for a formal language containing property symbols of every finite type. The proof grammar is thus applicable to any finite level higher-order logic.
The unique features of this system are: first, its mode of presentation as a recursive discourse grammar rigorously constructed from the...
Production Systems are languages widely used for the implementation of Artificial Intelligence projects. They support programs in which the sequence of instructions is not fully determined at the beginning of their execution, as well as 'event driven' programs (i.e. the occurrence of a particular element in the data set determines...
System architectures for interconnecting large numbers of processors are being widely studied [AG82,TH75,TR82]. Of particular interest in such architectures is the exploitation of concurrency among processors. This concurrency can be parallelism, in which different parts of a single data case are processed at the same time, or pipelining, in which...
Program understanding is an integral part of the testing and maintenance phases of the software life cycle. There have been numerous investigations of the influence of various aspects of a program and the program- ming process on program comprehension. However, the many different measures of understanding used in these studies...
Cichelli has presented a simple method for constructing minimal perfect hash tables of identifiers for small static word 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....
A computer program complexity measure is a measure of how easy the program is to understand, test, modify, maintain, etc. Many of these measures are derived from the control or flow graph of the program. We describe these measures graph theoretically, indicate what aspect or aspects of the program they...
A software system to study network algorithms was implemented on UNIX. Each part of a network algorithm can be 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/44. Inter-node communication...
A concurrency and resiliency control scheme for a distributed database system with replicated data is discussed. The scheme, true-copy token scheme, uses true-copy tokens in order to designate the physical data copies (true copies) that can be identified with the current logical data that are globally unique, and then it...
A theory for resiliency control of distributed database systems is developed, and schemes that preserve the consistent global database state in the presence of site crashes and message link failures are discussed. The schemes can at least theoretically be paired with any concurrency control scheme that produces y-serializable executions. Further,...
This grant supported acquisition of a minicomputer system for departmental research. The equipment selected is a DEC VAX-11/750 system, installed in remodeled space in the Computer Science (formerly Farm Crops) Building. Grant funds for equipment acquisition were supplemented by support from the Tektronix Foundation.
After completion of the physical facilities...
A typical database system maintains target data, which contain information useful for users, and access path data, which facilitate faster accesses to target data. Further, most large database systems support concurrent processing of multiple transactions. For a static database system model, where units of concurrency control are not dynamically created...
This paper presents a model for deterministic parsing which was designed to simplify the task or writing and understanding a deterministic grammar. While retaining structures and operations similar to those or Marcus's PARSIFAL parser [Marcus 80] the grammar language incorporates the following changes. (1) The use or productions operating in...
Caesar is an interactive graphic editor that is used to generate layouts for VLSI circuits . It runs on a VAX-11/780 under the UNIX operating system with Berkeley extensions. Caesar has a unique and simple user interface. Phled is an enhanced version of Caesar
that runs on a M68000-based engineering...
A denotational semantics is presented for a language that includes multiple-valued functions (essentially Lisp S-expressions), which map from ground values into the power domain of ground values. The domain equations are reflexive. and fixed points of all functions are defined. Thus, it is possible to specify an operating system as...
It is highly desirable for a distributed database system to achieve logically continuous operation even if some sites or message links fail. In this paper, we describe a scheme that can automatically reconfigure a fully-replicated distributed database system upon subsystem failures. The scheme can tolerate total failures of some sites....
Tbc expanding complexity of database application worlds, and the accelerating pace of change of these worlds mandate data models which support some of the tasks of data interpretation which formerly were borne by the applications programs. Chief among these are the support for virtual data, definition of transactions, and enforcement...
A database to be used by electrical circuit design, test, and repair expert systems must support both structural data and inferential data about the circuit. It is well known that engineering databases must support dynamic schema (re)definition of the structural data and entity-based access to it. We analyze this requirement...
This paper presents a Hypothetical Storage Server for an experimental design database system. The storage server provides unified management of historical versions and hypothetical versions of objects in a design database. The extension of each database object is man.aged as a tree of multiple distinct representatives. One branch of the...
Performance of a reliable storage subsystem for a centralized database system was studied by simulation. The reliable storage subsystem studied consists of three redundant disk units that are updated one at a time from a consistent database state to another consistent database state, Thus, even if a central processor and/or...
The "style metric" of Berry and Meekings is purported to quantify the lucidity of software written in the C programming language. We used a modification of this metric to try and identify error-prone software. Our results indicate that this metric seems to bear little relationship to the density of errors...
Information is often incomplete in databases, and nulls are required to represent missing or unknown data; however, many difficulties occur with nulls. In his 1983 text, C. J . Date rejected outer join of relations with nulls mainly due to a perceived problem with functional dependencies (FDs): when nulls are...
There is some debate over the effect of using deeply nested control structures upon programmer comprehension. In order to test the effect of deeply nested IF-THEN-ELSE statements, we split 148 computer science students of varing backgrounds into two groups. One group received a listing of a program that made excessive...
A method for implementing parameterized types is given. Two simplifying restrictions are assumed: types are only parameterized with other types, and assignment is like that of SNOBOL, CLU, and Smalltalk. An algorithm for type checking that handles parameterized types and overloading is presented .
The design of an experimental object-based programming language is discussed. The language is intended for investigating techniques for organization of programs.
This study examined the UNIX command abbreviation schemes preferred by expert and novice UNIX programmers. The two parts of the conducted experiment were: subjective rating of UNIX command abbreviations for each of the six abbreviation categories (acronym, combination, contraction, identity, synonym, and truncation); subjects suggested descriptive command names for UNDC...
Exploratory Data Analysis (EDA) is a lesser known field which has outgrown the bounds of statistics. It differs from ordinary, or “confirmatory”, data analysis. Originated by John Tukey, EDA aspires toward an open-ended meta-goal: to discover “all interesting” [nontrivial, normal form, valid] hypotheses about a domain that is represented by...
This technical report reprints two articles that appeared in Proceedings of the Third International Machine Learning Workshop at Skytop, Pennsylvania, June 24-26, 1985. The first paper, The EG Project: Recent Progress, summarizes work on the EG project, which is investigating the role of active experimentation in aiding machine learning programs....
Test incorporations are program transformations that improve the performance of generate-and-test procedures by moving information out of the "test" and into the "generator." The test information is said to be "incorporated" into the generator so that items produced by the generator are guaranteed to satisfy the incorporated test. This article...
When Newell introduced the concept of the knowledge level as a useful level of description for computer systems, he focused on the representation of knowledge. This paper applies the knowledge level notion to the problem of knowledge acquisition. Two interesting issues arise. First, some existing machine learning programs appear to...
This report reviews the 31 papers on machine learning that were presented at the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85) held in Los Angeles during August, 1985. The papers are grouped according to a taxonomy of the various subareas of machine learning research. The areas receiving the most...
It is difficult to build intelligent computer-aided design (ICAD) programs using available expert system shells and AI programming languages. To build ICAD programs, tools are needed that support (a) generative search of design spaces, (b) deep search of design spaces to evaluate alternative designs, (c) simultaneous exploration of alternative designs...
In this short paper, we present an implementation method for a distributed commit/ termination protocol for a distributed database system. The protocol, which handles both commit and termination processing of distributed transactions, is represented by communicating Moore machines. Several advantages of our approach are discussed.
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 explains why previous researchers have found it so difficult to construct good...
The ALGEBRA READER models how an expert might read an algebra word problem. When experts read such problems they are believed to use pattern-indexed schemata and heuristics for known problem categories. These schemata are represented by pattern-action pairs that interact concurrently with the augmented transition network used to parse the...
We investigate the use of automata theory to model strategies for nonzero-sum two-person games such as the Prisoner's Dilemma. We are particularly interested in infinite tournaments of such games. In the case of finite-state strategies (such as ALL D or TIT FOR TAT) we use graph traversal techniques to show...
Smalltalk-80 obtains some of its expressive power from arranging classes in a hierarchy. Inheritance is an important aspect of this hierarchy. An alternative organization of classes is proposed that emphasizes description instead of inheritance. This alternative can be used with compile-time type checking and retains the important characteristics of Smalltalk's...
This paper presents the results of a controlled experiment comparing debugging abilities of novice, intermediate and skilled student programmers. Debugging performance differences were studied using two single-page Pascal programs: a binary search program and a median calculation program. Two types of semantic errors, array bounds and undefined variable, and two...
FORTRAN permits both explicit and implicit options for both data declaration and type conversion features. This study investigated the effects of explicit and implicit data declaration and type conversion features on a program comprehension task performed by FORTRAN programmers in an introductory programming course. The results indicated that both factors...
Recent advances in diagnostic expert systems have been limited by the crucial Knowledge Acquisition Problem: to bring expert heuristics into logical, conditional rule forms useful for computer aided diagnosis. Some automatic systems with potential biomedical relevance that do acquire knowledge are reviewed here, and analyzed from the standpoint of possible...
This paper presents the initial results from an empirical study of mechanical design engineers. In this study, six engineers were video-taped solving real mechanical design problems. Preliminary analysis of this protocol data has yielded several important findings, including (a) mechanical designers progress from systematic to opportunistic behavior as the design...
X2 is an object-oriented programming language. Object-oriented programming models everything in the world as objects that have some local state that may vary with time. If the state of an object varies with time the object is mutable. If the state is time independent the object is immutable. Each object's...
Yashar is a rule based meta-tool for rapidly producing tools to increase programming speed through automating restructuring of existing source code modules so they can be reused, generating of syntax-directed tools, language-to-language translation, automated document generation , and various debugging tools. The main significance of Yashar is that it can...
The focus of this paper is on the underlying knowledge base for an intelligent tutorial system for high school algebra problems. We present a model of problem solving flexible enough to account for a variety of problem solving behaviors and general enough to allow new problem domains to be defined...
Arash is a rule-based tool for re-structuring source programs in order to build software systems from reusable components. Arash incorporates a collection of Generalizers which transform source code modules into abstracted modules. Conversely, a collection of Refiners produce a concrete instance from an abstracted source module . Both Generalizers and...
Artimis is part of an environment for software reuse consisting of two logically independent portions, 1) the indexing and retrieval facility called, GrabBag, for storage and subsequent retrieval of reusable modules, and 2) a set of tools called Browsers, which aid reading and understanding of source programs. GrabBag creates a...
Expert advisory systems for agricultural pest management control offer the means to capitalize on the wealth of information that is currently tied up in research laboratories and human experts' minds. The ideal system would blend knowledge from three sources - human experts, dynamic simulation models, and historical databases - to...
This tutorial discusses one of the oldest problems in computing: how to search and retrieve keyed information from a list in the least amount of time. Hashing -- a technique that mathematically converts a key into a storage address -- is one of the best methods of finding and retrieving...
Detecting instances of software theft and plagiarism is a difficult problem. The statistical analysis of peculiar words or phrases known to be used by an author is a common method of settling authorship disputes in English literature. This paper presents a similar method for identifying authorship of programs. The method...
Programming style guidelines and automated coding style analyzers have been developed without a solid experimental or theoretical basis. In this paper we make a distinction between typographic (layout) style characteristics and the underlying structural style content and then show through controlled studies that this distinction aids in assessing the influence...
This chapter develops a taxonomy of learning methods using techniques based on Newell’s knowledge level. Two properties of each system are defined: knowledge level predictability and knowledge level learning. A system is predictable at the knowledge level if the principle of rationality can be applied to predict its behavior. A...
Two powerful reasoning tools have recently appeared, logic programming and assumption based truth maintenance systems (ATMS). An ATMS offers significant advantages to a problem solver: assumptions are easily managed and the search for solutions can be carried out in the most general context first and in any order. Logic programming...
Several years ago we began development of an object-based programming language and environment which we call X2. We implemented X2 using a virtual machine similar to Smalltalk-80 implementations, but X2 does no message look-up. The implementation differs from most Smalltalk-80 systems in that objects are paged and in the ability...
This report describes of current research in Artificial Intelligence at Oregon State University. The five areas of active research are ( a) intelligent aids for mechanical engineering design, (b) active experimentation as a method in machine learning, ( c) techniques for combining logic programming and assumption-based truth maintenance, ( d)...
Three different approaches to type checking have been taken in object-oriented programming languages. Smalltalk-80 uses run-time type checking. C++ uses subtypes. A third alternative is to use parameterized types. We examine the difficulties of programming in an object-oriented fashion with compile-time type checking and argue that parameterized types are better...
We extend previous results for optimally scheduling concurrent program modules, called tasks, on a fixed, finite number of parallel processors in two fundamental ways: (1) we introduce a new heuristic which considers the time delay imposed by message transmission among concurrently running tasks; and (2) we introduce a second heuristic...
Two methods for parallelizing WHILE loops are presented. The first method converts a WHILE loop into a FORALL construct, and the second method pipelines a WHILE loop. Each of the methods is based on a transformation that makes explicit the loop counting. Also, we propose two parallel WHILE constructs.
The term object-oriented is defined. This definition is then related to message-passing, inheritance, polymorphism, data abstraction, generics, and overloading.
A complete approach to reasoning under uncertainty requires support for both identification of the appropriate hypothesis space and ranking hypotheses based on available evidence. We present a hybrid reasoning scheme which combines symbolic and numeric methods for uncertainty management to provide efficient and effective support for both of these tasks....
In this paper we will describe two known strategies for static processors allocation in an n-cube multiprocessor, namely the buddy system strategy and the gray code strategy and then propose a new strategy that outperforms the first by (n-k+1) and the second by (n-k+1)/2 in cube recognition. Furthermore, our strategy...
We survey the use of genetic algorithms in function optimization. We find that there are two distinct camps. Holland's camp seems to be interested in artificial intelligence uses of genetic algorithms and seems to have made only a few attempts at function optimization. Rechenberg's camp has concentrated on the optimization...
Reasoning about physical systems requites the integration of a range of knowledge and reasoning techniques. P. Hayes has named the enterprise of identifying and formalizing the common-sense knowledge people use for th.is task "naive physics." Qualitative Process theory by K. Forbus proposes a structure and some of the content of...
Using Smalltalk-80, programmers can produce prototypes much faster than with C or Pascal. What techniques do Smalltalk-80 programmers use to produce these prototypes? What is special about Smalltalk-80 that enables them to uses these techniques? Can these techniques be used with conventional languages such as C? In an attempt to...
Many studies have shown that expert programmers are more effective at debugging programs than novice programmers. These studies have suggested that the major reason for this difference is due to the experts' superior comprehension of the program. This paper reports two experiments which investigated expert and novice student programmers program...
We investigate several methods of computing Fibonacci numbers quickly and generalize some properties of the Fibonacci numbers to degree r Fibonacci (R-nacci) numbers. Sections 2 and 3 present several algorithms for computing the traditional, degree two, Fibonacci numbers quickly. Sections 4 and 5 investigate the structure of the binary representation...
Oregon Speedcode Universe (OSU) is a software development system employing on-screen editing of standard graphical user interface objects, prototyping, program generation, and automatic analysis tools which are typically used to accelerate the production of running applications. A programmer uses OSU to design and implement all user interface objects such as...
This paper introduces a method that improves the performance of a problem solver by reformulating its domain theory into one in which functionally relevant features are explicit in the syntax. This method, in contrast to previous reformulation methods, employs sets of training examples to constrain and direct the reformulation process....
This tutorial discusses one of the oldest problems in computing: how to search and retrieve keyed information from a list in the least amount of time. Hashing - a technique that mathematically converts a key into a storage address - is one of the best methods of finding and retrieving...
Asmodeus is a distributed database system which simplifies the tasks of the Unix systems administrator. Using simple commands to the Asmodeus command interface, the systems administrator can perform many tedious operations over a large network of machines. The system uses a reliable datagram socket connection for all of its communication....
ELGDF (Extended Large Grain Data Flow) is a design language that allows representation of a wide variety of parallel programs. The syntax is graphical and hierarchical to allow construction and viewing of realistically sized programs. ELGDF language facilitates describing parallel programs in a natural way for both shared memory model...
Oregon Speedcode Universe (OSU) is a software development environment for design, implementation, and maintenance of large soft.ware systems. Designed to be highly visual, OSU combines traditional structured analysis techniques found in most CASE tools with advanced graphical user interface management systems (UIMS) found on most contemporary workstations. This paper describes...
Recently generalized Fibonacci numbers have received increasing attention. Some properties that are well known for traditional Fibonacci numbers do not generalize easily, some others do not generalize at all. In this paper we report some properties that we have generalized. Section 1 introduces the notation and a theorem due to...
We introduce five criteria by which to judge the suitability of a method for solving the problem of learning concepts from examples: correctness (the correct concept should be identified), performance efficiency (the learned definition should be efficient to apply to the performance task), flexibility (the method should be able to...
Acoustic position estimation is used where high accuracy navigation is required over a small area, such as for searching or for collecting gravitational or geomagnetic data. In this position estimation method, a surface ship or submersible periodically sends out a high-frequency acoustic 'ping' at a prearranged frequency. This ping is...
In recent papers on machine learning, the term 'operationalization' has been used to describe the purpose of the learning process. In particular, explanation-based learning systems are said to 'operationalize' the given target concept. Unfortunately, the exact meaning of this term has varied from one paper to another, and frequently the...
A complete approach to uncertainty management requires support for interactive and incremental problem formulation, inference, hypothesis ranking, and decision making. In addition, computational models must allow for time and resource bounds. Current approaches to uncertainty management concentrate primarily on inference, provide little or no support for the larger issues in...
New parallel algorithms for solving the decomposed linear programs are developed. Direct parallelization of the sequential algorithm results in very limited performance improvement using multiple processors. By redesigning the algorithm, we achieved more than 2*P times performance improvement over the sequential algorithm, where P is the number of processors used...