leff@smu.UUCP (Laurence Leff) (04/22/88)
TECHNICAL REPORTS FOR 1985 Computer and Information Science Department University of Oregon Eugene, OR 97403 CIS-TR-85-01 Automating the Transformational Development of Software by Stephen Fickas. Abstract: This paper reports on efforts to extend the Transformational Implementation (TI) model of Software Development [1]. In particular, we describe a system that used AI techniques to automate major portions of a transformational implementation. The work has focused on the formalization of the goals, strategies, selection rationale, and finally the transformations used by expert human developers. A system has been constructed that includes representations for each of these problem solving components, as well as machinery for handling human/system interaction and problem solving control. We will present the system and illustrate automation issues through two annotated examples. This report will appear in IEEE Trans. Soft. Eng. 1985. CIS-TR-85-02 AND Parallelism and Nondeterminism in Logic Programs by John S. Conery and Dennis F. Kibler. Abstract: This paper defines an abstract interpreter for logic programs based on a system of asynchronous, independent processors which communicate only by passing messages. Each logic program is automatically partitioned and its pieces distributed to available processors. This approach permits two distinct forms of parallelism. OR parallelism arises from evaluating non-deterministic choices simultaneously. AND parallelism arises when a computation involves independent, but necessary, subcomputations. Algorithms like quicksort, which follow a divide and conquer approach, usually exhibit this form of parallelism. These two forms of parallelism are conjoinly achieved by the parallel interpreter. CIS-TR-85-03 Polynomial time solutions of some problems in computational algebra by Katalin Friedl and Lajos Ronyai. Abstract: The first structure theory in abstract algebra was that of finite dimensional Lie algebras (Cartan-Killing), followed by the structure theory of associative algebras (Wedderburn-Artin). These theories determine, in a non-constructive way, the basic building blocks of the respective algebras (the radical and the simple components of the factor by the radical). In view of the extensive computations done in such algebras, it seems important to design efficient algorithms to find these building blocks. We find polynomial time solutions to a substantial part of these problems. We restrict our attention to algebras over finite fields and over algebraic number fields. We succeed in determining the radical (the ``bad part'' of the algebra) in polynomial time, using (in the case of prime characteristic) some new algebraic results developed in this paper. For associative algebras we are able to determine the simple components as well. This latter result generalizes factorization of polynomials over the given field. Correspondingly, our algorithm over finite fields is Las Vegas. Some of the results generalize to fields given by oracles. Some fundamental problems remain open. An example: decide whether or not a given rational algebra is a noncommutative field. CIS-TR-85-04 Building Control Strategies in a Rule-Based System by Stephen Fickas, David Novick, and Rob Reesor. Abstract: Rule-based systems in which conflict resolution occurs require a control strategy. This paper shows that effective conflict resolution often requires domain-specific knowledge. Moreover, defining control knowledge may be as difficult as defining domain knowledge. We present the ORBS model and implementation of a rule-based systems environment which supports complex and dynamic control strategies, and the interactive development of these strategies. ORBS and earlier systems are compared with respect to language, control, and environmental support for development of control. Four examples of control using ORBS are discussed: emulating a conventional system, separating domain knowledge from scheduling knowledge, using an agenda-based strategy, and dynamically changing a strategy during execution. The ORBS environment provides machine-aided construction of scheduling strategies through a catalog of scheduling functions from which strategies can be constructed, a skeleton scheduler, a scheduling editor, a scheduling tracer, and a break package. Finally, the paper discusses a model for system implementation of control from user-provided examples. CIS-TR-85-05 Control Knowledge in Expert Systems: Relaxing Restrictive Assumptions by Stephen Fickas and David Novick. Abstract: Many expert systems use fixed, domain-independent control strategies. These systems often embody assumptions about control and control knowledge which limit the utility of application programs. We present the ORBS model and implementation of a rule-based systems environment which attempts to expose, and give users access to, hidden control points. ORBS provides a language for defining control strategies, and supports the interactive development of these strategies. We discuss the process of explicating control knowledge through a process of refining an application rule. CIS-TR-85-06 Design Issues in a Rule-Based System by Stephen Fickas. Abstract: This paper discusses the interaction between language, environment and development model in the realm of rule-based systems. In particular, we discuss our efforts in building a rule-based language and development tools that support incremental development, interactive debugging, and reuse of components. CIS-TR-85-07 Computing the Composition Factors of a Permutation Group in Polynomial Time by Eugene M. Luks. Abstract: Given generators for a group of permutations, it is shown that generators for the subgroups in a composition series can be found in polynomial time. The procedure also yields permutation representions of the composition factors. CIS-TR-85-08 The Concave Cusp as a Determiner of Figure-Ground by Kent A. Stevens and Allen Brookes. Abstract: One method by which figure is distinguished from ground is on the basis of information provided by concave cusps in contours. Concave cusps are prevalent in natural textures, occurring in images wherever the silhouettes of convex, opaque objects about or partially occlude one another. The points of contact between silhouettes present concave cusps, each indicating the local assignment of figure versus ground across the contour. There are known tendancies to interpret as figure those regions that are lighter, or smaller or more convex. We show that the concave cusp is another, distinct, determiner of apparent figure-ground that provides a stronger influence on figure-ground than lightness or size. While concave cusps are associated with overlapping convex figures, the salience of the cusp appears to derive from the local geometry and not from the adjacent contour convexity. CIS-TR-85-09 Fast Parallel Computation with Permutation Groups by Eugene M. Luks and Pierre McKenzie. Abstract: We develop fast parallel solutions to a number of basic problems involving solvable and nilpotent permutation groups. Testing solvability is in NC, and RNC includes, for solvable groups, finding order, testing membership, finding the derived series and finding a composition series. Additionally, for nilpotent groups, one can, in RNC, find the center, a central composition series, and point-wise stabilizers of sets. There are applications to graph isomorphism. In fact, we exhibit a class of vertex-colored graphs for which determining isomorphism is NC-equivalent to computing ranks of matrices over small fields. A useful tool is the observation that the problem of finding the smallest subspace containing a given set of vectors and closed under a given set of linear transformations (all over a small field) belongs to RNC. CIS-TR-85-10 An Environment for Building Rule-Based Systems: An Overview by Stephen Fickas, David Novick, and Rob Reesor. Abstract: This paper presents an overview of the Oregon Rule-Based System (ORBS), an environment which supports the construction and development of domain knowledge and control knowledge for rule-based expert systems. We describe the operation of the system, with particular attention to issues of control knowledge. The paper then presents an interactive model for development of application systems. Finally, the paper discusses KATE, a knowledge-based, problem-solving specification language and its use in constructing expert systems. CIS-TR-85-11 Orthogonality in the Design of Command Languages by Cathryn A. Stanford, Edward M. Bowden, David Locke, and Sarah Douglas. Abstract: Research has shown that organization plays an important role in memory. The present study applies these findings to the design of a command language. The concept of orthogonality is used to maximize the internal organization of a text editing command language. This orthogonal language is compared to an organized, but non-orthogonal, and an anti-organized language on measures of predictability, recall, and performance. Subjects in the orthogonal language condition performed better than subjects in the other conditions on all measures. General steps necessary to design an orthogonal language are discussed. CIS-TR-85-12 Zero divisors and invariant subspaces by Lajos Ronyai. Abstract: In this paper we continue the study of algorithmic problems related to associative algebras we initiated in recent work by Friedl-Ronyai. The main result of this paper is an algorithm to find zero divisors in associative algebras over finite fields. The idea of this algorithm comes from an almost constructive proof of Weddernburn's theorem on finite fields given in Herstein's algebra text. The above result is applied to the problem of finding common invariant subspaces for a set of matrices over a finite field. Using this method one can give a polynomial time algorithm to find certain minimal normal subgroups in permutation groups. The corresponding questions over fields of characteristic zero remain open. CIS-TR-85-13 A Knowledge-Based Approach to Specification Acquisition and Construction by Stephen Fickas. This work is concerned with the automation of the software specification process. Specification automation research to date has concentrated on non-interactive translation of complete, correct but informal problem descriptions into formal specifications. The work proposed here is unique in that it addresses the construction of complete, correct informal problem descriptions from incomplete, often incorrect user descriptions. The proposed system will rely on interactive problem solving and large amounts of domain specific knowledge to carry out this process. The final output of the system will be a formal specification; our current target is the Gist specification language, although other languages are under consideration.