leff@smu.UUCP (Laurence Leff) (04/22/88)
TECHNICAL REPORTS FOR 1987 Computer and Information Science Department University of Oregon Eugene, OR 97403 CIS-TR-87-01 A Virtual Processor for Parallel Logic Programs by John S. Conery and David M. Meyer. Abstract: The Warren Abstract Machine is the state of the art in implementation technology for Prolog. Its success is based on an instruction set that supports unification, clause selection, and the management of variable binding environments. Prolog is a sequential programming language, and many of the operations of the WAM rely on the standard, depth-first execution order of Prolog programs. This paper introduces OM, a virtual processor for parallel logic programs. The processor is being designed so that a collection of OM processors will be suitable for a large scale, non-shared memory multiprocessor. Some of the features of the WAM, such as instructions for unification, are present in OM, but other aspects, such as control instructions and the management of binding environments, have been redesigned to support programs of an abstract parallel execution model. CIS-TR-87-02 Permutation groups in NC by Laszlo Babai, Eugene M. Luks, and Akos Seress. Abstract: We show that the basic problems of permutation group manipulation admit efficient parallel solutions. Given a permutation group G by a list of generators, we find a set of NC-efficient strong generators in NC. Using this, we show that the following problems are in NC: membership in G; determining the order of G; finding the center of F; finding a composition series of G along with permutation representations of each composition factor. Moreover, given G, we are able to find the pointwise stabilizer of a set in NC. One consequence is that isomorphism of graphs with bounded multiplicity of eigenvalues is in NC. The analysis of the algorithms depends, in several ways, on consequences of the classification of finite simple groups. CIS-TR-87-03 Design and Implementation of a Qualitative Constraint Satisfaction System by P. Thyagarajan and Arthur M. Farley. Abstract: This report describes the design and implementation of a constraint-based environment for modeling the structural description of physical systems in qualitative space. The variables and constraints define the structural description and the constraint propagation derives the behavioral descriptions. The constraint propagation finds an interval value for each variable by shrinking the initial interval values of the variables, such that all the solutions are captured by the final values of the variables. During the propagation of constraints, justifications are built for each variable so to give an explanation for a behavior of the system. The constraint system is incorporated with an Assumption-based Truth Maintenance System (ATMS) to avoid recomputation. CIS-TR-87-04 Problem Acquisition in Software Analysis: A preliminary Study by Stephen Fickas, Sharon Collins, and Susan Olivier. Abstract: We are interested in how a problem description can be acquired from a client, subsequently debugged, and finally turned into a formal software specification. In this paper we discuss a) the components of a proposed system for handling these processes, b) the results of preliminary protocol studies in support of the acquisition component of our system, and c) our prescription for further work in the area. We include an Appendix that contains pieces of our protocols that illustrate two important acquisition techniques that emerged from our studies, example generation and summarization. CIS-TR-87-05 Automating the Specification Process by Stephen Fickas. Abstract: Recent results in formalizing and automating software specification move us closer to a computer-based specification assistant. In this paper, we review three projects that we believe are particularly relevant to this goal. For each project we describe first the underlying model, and second our efforts to study it by construction of a prototype tool based on the model. Finally, we discuss incorporating the results of our study into a knowledge-based system that assists in the construction of a formal specification. CIS-TR-87-06 Reliable Minimum-Time Broadcast Networks by Arthur M. Farley. Abstract: The specification of a communication network requires both a topological and an operational aspect. The topological aspect consists of a graph with vertices representing sites and edges their interconnection by lines. The operational aspect consists of calling procedures sufficient to complete various communication tasks. In earlier research, we specified several classes of minimum-time broadcast networks; such networks allow completion of one-to-all broadcast task from any site as originator in the minimum possible time (i.e., $\lceil log_2~n \rceil$ time units for n sites). Here we present extensions to the operational specifications of one of these classes to realize broadcast networks that are also immune to single site failures and to isolated site failures. In these networks, broadcast incurs the minimum possible delay of at mos ofteual tunit for eaa compoially unreliable data in system load tables. CIS-TR-86-16 Finding a Minimum Base for Permutation Groups is NP-hard by Kenneth D. Blaha. Abstract: The notions of a base and strong generating set were defined by Sims in 1970, and used as an efficient method to store and analyze large permutation groups. Since then the base and strong generating set have played a key role in the development of numerous group theoretic algorithms. The base and strong generating set also have applications to graph isomorphism testing, network theory, and backtrack search algorithms. A number of authors have noted that the size of the base has a direct effect on the space and time complexity of algorithms that use a base as a key ingredient. Given generators for a permutation group G on n letters, the question was posed as to whether or not a polynomial time greedy algorithm could be used to find a minimum base for G. We show that the greedy algorithm does not always find a minimum base for G. In fact, the minimum base problem is NP-hard, even if G is restricted to be a cyclic group or an abelian p-group. The corresponding decision problem, does there exist a base for G of size no more than K, is NP-complete. Let G be a permutation group of degree n, and suppose that G has a minimum base of size k. The maximum size of a nonredundant base for G is bounded above by O(k ~log~ n). Moreover, there exists an infinite family of permutation groups with: minimum base size k, degree n, and nonredundant base of size W (k ~log~ n). We have also obtained bounds for the size of a base produced by the greedy algorithm when G is restricted to be an abelian p-group. If G is an abelian p-group, then the size of a base produced by the greedy algorithm is bounded above by O(k ~log~ ~log~ n). Further, there exists an infinite family of abelian p-groups with: minimum base size k, degree n, and base produced by the greedy algorithm of size W (k ~log~ ~log~ n). h: minimum base size k, degree n, and nonredundant base of size W (k ~log~ n). We have also obtained bounds for the size of a base produced by the greedy algorithm when G is restricted to be an abelian p-group. If G is an abelian p-group, then the size of a base produced by the greedy algorithm is bounded above by O(k b90/comp/doc/techreports/42 664 5 angeMetalogical operations, such as assert and retract, or extensions to logical operations, such as unification with read-onlyn abeliables, are not required. The effects of oby the greiented programming are obtained through a control strategy that interprets some negative literals as procedure calls and others as instances of objects. A new type of logical formula, the object clause, is introduced to describe procedures that modify instances of objects. The paper concludes with a discussion of aspects of object oriented programming, such as class hierarchies, and how they can be realized in the new NP-co. \medskip \noindent CIS-TR-87-11 Cluster-based Representation of Hydraulic Systems by Arthur M. Farleian p-stract: Traditional qualitative mse of s techniques have focused on means for abstracting the W (k paces of variables that are used to represent system states and for simplifying the constraints that hold among those variable values. In this paper we present a technique for structural abstraction applicable to the domain of pressurized hydraulic systems. Valves, when closed, functionally i minite clusters of components. A cluster can only be in one of two qualitative states -- static, where pressures are equal throughout and no flow occurs, or dynamic, where flow from a high pressure source to a low pressure sink occurs. Ro mor in terms of clusters is shown to facilitate planning for and explaining about the operation and repair of hydraulic systems. CIS-TR-87-12 Automatic Derivation of Systolic Arrays for LU Decomposition by Sanjay V. Rajopadhye. Abstract: We present a number of systolic arrays for decomposing a matrix into its lower and upper triangular factors (LU-decomposition). These architectures have been formally derived using techniques for synthesizing systolic arrays from affine recurrence equations, and the entire design process can be automated. The derivation highlights two important aspects of our synthesis methodology. Firstly, the initial specification is a high level one similar to a nested loop program. We illustrate the use of a technique called explicit pipelining to automatically localize the data dependencies. Secondly, the architectures that we present have interesting features such as control signals, and specialized behavior of certain processors (such as boundary processors). We describe how these characteristics (and also processor initialization signals) can be derived automatically. CIS- In f14 Wavelength Selection for Synthetic Image Generation by Gary W. Meyer. Abstract: The efficient synthesis of color in computer graphics is dependent on modelling the correct number and spacing of wavelengths across the visible spectrum. It has recently been shown that the opponent representation of the fundamental spectral sensitivity functins is optimal from the point of view of statistical communication theory. This result is used in this paper to guide the selection of wavelengths for synthetic image generation. Gaussian quadrature with the oppoiablefundamentals as weighting functions is used to choose the wavelengths. This approach is shown to be superior to using Gaussian quadrature with the fundamental spectral sensitivity functions or the CIE XYZ matching functions. The technique is evaluated by using color difference calculations and by comparisons between a real scene and a computer generated picture of that scene. CIS- R-87-15 Color Defective Vision and Commputer Graphic Displays by Gary W. Meyer and Donald P. Greenburg. Abstract: The fundamental spectral sensitivity functions of the human visual system define a color space which can be employed to design better color user interfaces. In particular, this color space makes it possible to accommodate individuals with color deficient vision. In order to screen potential users of computer graphics systems, traditional color vision tests, such as the Farnsworth-Munsell 100 hues test, can be implemented using a digitally controlled color television monitor, and these tests can be extended in ways that improve the specificity of their diagnoses. To assist in the design of computer graphic displays, a picture of the world as seen by the color deficient o ~log~vers can be synthesized and guidelines can be given for the selection of colors to be presented to color deficient observers. CIS-TR-87-16 I/O Behavior of Systolic Arrays by Sanjay Rajopadhye. Abstract: We study the problem of systematically deriving how data should be loaded and unloaded from systolic arrays. While a number of researchers have studied the problem of deriving systolic arrays (usually by transformations of algorithmiccorrespondations), the question of how the processors are to be loaded, and how the results should be extracted from the derived arrays has not received much attention. We show how this problem can be tackled in the same context as the synthesis problem. Thus, the derived arrays are guaranteed to have appropriate m NP-nisms for data loading/unloading, and