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...