1991 technical reports

CS-91-72
Title	Characteristic Words as Fixed Points of Homomorphisms
Authors	J. O. Shallit
Abstract	Abstract (PDF)
Date	December 1991
Report	Characteristic Words as Fixed Points of Homomorphisms (PDF)			Compressed DVI: Characteristic Words as Fixed Points of Homomorphisms (DVI.Z)

CS-91-67
Title	Comparative Stylistics in an Integrated Machine Translation System
Authors	K. Mah
Abstract	Comparative stylistics is a subfield of stylistics that attempts to account for the differences in style between languages. Rules of comparative stylistics are commonly presented, in textbooks of translation, as "rules-of-thumb", but if we hope to incorporate a knowledge of comparative stylistics into natural language understanding systems, we must take a more formal approach. In particular, we will develop a computational model of comparative stylistics for machine translation that could be used to guide translation and thereby improve the quality of the translated output. An implementation of this model would provide additional information to the machine translation system about the potential modulations to the translated text and their effects, enabling it to make a more informed decision. In this thesis, we develop a set of formal rules of syntactic French-English comparative stylistics to be used as a component of a model of comparative stylistics. As the foundation for the formal rules, we adapt theoretical rules of syntactic French-English comparative stylis- tics compiled by Guillemin-Flescher [1981] and the formal representation of syntactic style developed by DiMarco [1990]. A corpus of French sentences and their English translations is analyzed to convert the theoretical rules to a set of formal rules that builds on DiMarco's grammars of syntactic style. Thus, we present a formal grammar of French-English compara- tive stylistics. We also suggest a method for incorporating these rules into an existing machine translation system.
Date	October 1991
Report	Comparative Stylistics in an Integrated Machine Translation System (PDF)			Compressed DVI: Comparative Stylistics in an Integrated Machine Translation System (DVI.Z)

CS-91-65
Title	Abstraction in Nonlinear Planning
Authors	Qiang Yang, Josh D. Tenenberg, & Steve Woods
Abstract	We extend the hierarchical, precondition-elimination abstraction of Abstrips to nonlinear, least-commitment planners such as Tweak. Specifically, we show that the combined planning system, AbTweak, satisfies the monotonic property, whereby the existence of a lowest level solution the implies the existence of a highest level solution that is structurally similar to II. This property enables one to prune a considerable amount of the search space without loss of completeness. In addition, we develop a criteria for good abstraction hierarchies, and develop a novel, complete search strategy called Left,Wedge that is optimized for good abstraction hierarchies. We demonstrate the utility of both the monotonic property and the Left-Wedge strategy through a series of empirical tests.
Date	December 1991
Report	Abstraction in Nonlinear Planning (PDF)			Compressed PostScript: Abstraction in Nonlinear Planning (PS.Z)

CS-91-62
Title	On Specialization Constraints Over Complex Objects
Authors	M. Ito, G. Weddell and N. Coburn
Abstract	Most semantic data models and object-oriented data models allow entity and object classes to be organized according to a generalization taxonomy. In addition, range restrictions (or property typing) may be specified not only on properties associated with a given class, but also on properties inherited from superclasses. In this paper, we consider a more general form of specialization constraint in which range restrictions are associated with property value paths, instead of with the properties themselves. One consequence is that the constraints enable a form of molecular abstraction, in which the internals of more complicated objects can be defined in terms of a collection of more primitive classes. We consider the problem for two models. The first imposes no constraints on class membership for an object beyond those implied by sub- classing constraints. In this case, we present a sound and complete axiomatization for arbitrary specialization constraints, and e1cient decision procedures for the corresponding membership problems. The second model is more typical and requires that each object is created with respect to a particular class. Membership problems in this case are shown to be NP-hard, and NP-complete if class schema include a "bottom" class. We exhibit polynomial-time decision procedures when a bottom class does exist and antecedent specialization constraints satisfy a bounded path length condition. We also consider a case concerning the second model in which class schema satisfy a lower semi-lattice condition. A sound and complete axiomatization for well-formed specialization constraints is presented, together with e1cient decision procedures for the membership problem for well-formed constraints, and for determining if an arbitrary constraint is well-formed. We prove that the membership problem for arbitrary specialization constraints remains NP-complete, however, even for class schema satisfying the lower semi-lattice condition.
Date	December 1991
Report	On Specialization Constraints Over Complex Objects (PDF)			Compressed DVI: On Specialization Constraints Over Complex Objects (DVI.Z)

CS-91-56
Title	The Maximal Path Length of Binary Trees
Authors	Helen Cameron & Derick Wood
Abstract	We further refine the bounds on the path length of binary trees of a given size by considering not only the size of a binary tree, but also its height and fringe thickness (the difference between the length of a shortest root-to-leaf path and the height). We characterize the maximum path length binary trees of a given height, size, and fringe thickness. Using this characterization, we give an algorithm to find the maximum path length binary trees of a given size and fringe thickness.
Date	October 1991
Report	The Maximal Path Length of Binary Trees (PDF)			Compressed DVI: The Maximal Path Length of Binary Trees (DVI.Z)

CS-91-55
Title	A Constraint-Based Approach to Dynamic Colour Management for Windowing Interfaces
Authors	Blair MacIntyre
Abstract	Selecting harmonious colours for traditional window systems can be a difficult and frustrating endeavor. At the root of this problem is the fact that typical window systems do not allow abstract properties of colours to be specified. Instead, they insist that users specify individual colour values exactly. When many colours are used, the value of each colour must be chosen to satisfy any relationships that exist between it and previously chosen colours. Unfortunately, the difficulty of colour selection often prevents users from taking full advantage of the functional benefits of colour, particularly that of resolving context. A more desirable approach is to allow the aesthetic and functional properties of colours to be specified and to allow users to select values for the colours they wish. The window system can choose the remaining colours using these properties. Another failing of typical window systems is that once a colour value has been determined it will not change without explicit direction from the user. When windows open or close the factors which motivated a choice of colour value may change. Unfortunately, if the user wishes the chosen colour value to change as the environment changes, he or she must typically perform the modifications. A dynamic window system assists the user in making these choices. By specifying colour properties as constraints, a dynamic window system can adjust colour values as the environment changes, to satisfy these constraints. The potential problems with dynamic window systems incorporating colour constraints are investigated in this thesis. An implementation that uses a distributed, jostling, constraint-solver based on a simple dynamical system shows that this approach is possible.
Date	October 1991
Report	A Constraint-Based Approach to Dynamic Colour Management for Windowing Interfaces (PDF)			Compressed PostScript: A Constraint-Based Approach to Dynamic Colour Management for Windowing Interfaces (PS.Z)

CS-91-53
Title	uC++ Annotated Reference Manual (Preliminary Draft)
Authors	P. A. Buhr and R. A. Stroobosscher
Abstract	The goal of this work is to introduce concurrency into the object-oriented language C++ [Str91]. To achieve this goal a set of important programming language abstractions were adapted to C++, producing a new dialect called {mu}C++. These abstractions were derived from a set of design requirements and combinations of elementary execution properties, different combinations of which categorized existing programming language abstractions and suggested new ones. The set of important abstractions contains those needed to express concurrency, as well as some that are not directly related to concurrency. Therefore, while the focus of this work is on concurrency, all the abstractions produced from the elementary properties are discussed. While we are implementing our ideas as an extension to C++, the requirements and elementary properties are generally applicable to other object-oriented languages such as Eiffel [Mey88], Simula [Sta87] and Smalltalk [GR83]. This manual does not discuss how to use the new constructs to build complex concurrent systems. The manual is strictly a reference manual for {mu}C++. A reader should have an intermediate knowledge of control 0ow and concurrency issues to understand the ideas presented in this manual as well as some experience programming in C++.
Date	October 1991
Report	uC++ Annotated Reference Manual (Preliminary Draft) (PDF)			Compressed DVI: uC++ Annotated Reference Manual (Preliminary Draft) (DVI.Z)

CS-91-52
Title	uSystem Annotated Reference Manual Version 4.4
Authors	P. A. Buhr, H. I. Macdonald, & R. A. Stroobosscher
Abstract	The goal of this work was to introduce concurrency into the language C. To achieve this goal a set of library routines and definitions were created in C. The set of routines and definitions contains those needed to express concurrency, as well as some that are not directly related to concurrency. Therefore, while the focus of this work is on concurrency, all the abstractions produced from the routines and definitions are considered important. This manual does not discuss how to use the new constructs to build complex concurrent systems. The manual is strictly a reference manual for the {mu}System definitions. A reader should have an intermediate knowledge of control 0ow and concurrency issues to understand the ideas presented in this manual as well as some experience programming in C. This manual contains annotations set off from the normal discussion in the following way:
Date	October 1991
Report	uSystem Annotated Reference Manual Version 4.4 (PDF)			Compressed PostScript: uSystem Annotated Reference Manual Version 4.4 (DVI.Z)

CS-91-47
Title	Pm Numbers, Ambiguity, and Regularity
Authors	Helen Cameron & Derick Wood
Abstract	Abstract (PDF)
Date	September 1991
Report	Pm Numbers, Ambiguity, and Regularity (PDF)			Compressed DVI: Pm Numbers, Ambiguity, and Regularity (DVI.Z)

CS-91-46
Title	The Technology of Object-Oriented Databases
Authors	G. Weddell
Abstract	There is now a reasonable consensus on what an object-oriented (OODBMS) database system must have in the way of features. Roughly, one obtains an OODBMS by adding a "non-procedural" query language, secondary storage management and support for concurrency and recovery to an object-oriented programming language, such as C++ or Eiffel. Unfortunately, this cannot be accomplished by a straightforward marriage of existing database and compiler technology. From the point of view of relational database technology, new problems are introduced and most existing problems are made more complicated in some way problems on topics relating to query languages, constraint theory, storage management and object indexing, object clustering, query optimization, transaction processing, and so on, are all affected. During the summer of 1991, I had the opportunity of working with thirteen of our graduate students in attempting to gain some appreciation for the present state of OODBMS technology. The students divided into five groups, consisting of two or three people each, for the purpose of surveying five of these topics as they relate to an OODBMS. This document is the result of their efforts. There are five individual reports in the document\|one for each of the groups. The first is a survey of proposals for complex object algebras and for query languages based on extensions to SQL; the second is a survey of typing in an OODBMS. The third report is a survey of recent proposals for concurrency control in cases where transactions are long duration, and where they also access complex object structures. The remaining two reports concern storage management and semantic query optimization respectively. The order of presentation is not accidental; reports on topics relating more to conceptual issues are located prior to those on topics relating to internal issues. However, the reader should have no difficulty in understanding the contents of any of the reports in isolation\|each has been written independently of the others. My thanks to all the students for their interest and enthusiasm for their help in making the course such a success. Particular thanks also to Glenn Paulley for preparing the final draft of this document.
Date	September 1991
Report	DVI Reports: Intro (DVI) Algebra (DVI) Concurrency (DVI) SQO (DVI) Storage (DVI) Types (DVI)		PDF Reports: Intro (PDF) Algebra (PDF) Concurrency (PDF) SQO (PDF) Storage (PDF) Types (PDF)

CS-91-44
Title	Description of Generalized Continued Fractions by Finite Automata
Authors	J. O. Shallit
Abstract	A generalized continued fraction algorithm associates with every real number x a sequence of integers; x is rational iff the sequence is finite. For a fixed algorithm, call a sequence of integers valid if it is the result of that algorithm on some input x0. We show that, if the algorithm is sufficiently well-behaved, then the set of all valid sequences is accepted by a finite automaton.
Date	September 1991
Comments	Use "table.roff" to get the table.
Report	Description of Generalized Continued Fractions by Finite Automata (PDF)			Compressed DVI: Description of Generalized Continued Fractions by Finite Automata (DVI.Z)

CS-91-43
Title	Communication Abstractions for Distributed Systems
Authors	James W. Hong
Abstract	This thesis presents techniques for reducing the complexity of communication in distributed systems. It presents a set of simple standards and tools that provide an eficient and consistent programming interface that can be used to implement a great variety of communication interactions both within and between various types of paradigms, abstractions, and entities. It also provides a framework based on these standards and tools, with which arbitrary communication systems can be constructed. Various communication paradigms and issues are examined in order to identify and categorize the fundamental aspects of communication. These fundamental as- pects are then redefined and organized into a set of communication abstractions which is simple and general, rigorous and flexible, low-level and extensible. The generic communication model based on this set provides a framework for arbitrary communication systems. Further, the model utilizes the eficiencies of a single mem- ory domain while providing a universal interface between various types of paradigms, abstractions, and entities across a wide spectrum of environments. The framework provided in the generic communication model is used to develop a specific model called the Buffer and Queue Model which provides a single eficient and consistent communications programming interface. The Buffer-Queue proto- col extends this consistent programming interface transparently to a distributed environment. Finally, a few examples are presented using Buffers and Queues that illustrate how various complex communication facilities may easily be developed and how the use of a common fundamental base makes intermixing of locally defined user interfaces and conversion between higher-level protocols a relatively straightforward task.
Date	September 1991
Report	Communication Abstractions for Distributed Systems (PDF)			Compressed DVI: Communication Abstractions for Distributed Systems (DVI.Z)

CS-91-39
Title	Drop Tolerance Preconditiong for Incompressible Viscous Flow
Authors	E.F. D'Azevedo, P.A. Forsyth, W.-P. Tang
Date	August 1991
Report	Only available in printed format

CS-91-35
Title	Implication Problems for Functional Constraints on Databases Supporting Complex Objects
Authors	Minoru ITO, Grant E. WEDDELL
Abstract	Virtually all semantic or object-oriented data models assume objects have an identity separate from any of their parts, and allow users to define complex object types in which part values may be any other objects. A more general form of functional dependency is proposed for such models in which component attributes may correspond to descriptions of property paths, called path functional dependencies. The main contribution of the reference is a sound and complete axiomatization for PFDs, when interpretations may be infinite. However, a number of issues were left open which are resolved in this paper. First, we prove that the same axiomatization remains complete if PFDs are permitted empty left-hand sides, and that the implication problem for arbitrary PFDs is decidable. A proof of the latter suggests a means of characterizing an important function closure. Based on this idea, we derive an effective procedure for constructing a deterministic finite state automaton representing the closure. The procedure is further refined to efficient polynomial time algorithms for the implication problem for cases in which antecedent PFDs satisfy a `prefix' condition. This class of PFDs includes as a proper subset the class of key PFDs. Finally, we prove that the axiomatization is not complete if logical consequence is defined with respect to finite interpretations only.
Report	Implication Problems for Functional Constraints on Databases Supporting Complex Objects (PDF)			Compressed DVI: Implication Problems for Functional Constraints on Databases Supporting Complex Objects (DVI.Z)

CS-91-34
Title	A Generic Paradigm for Efficient Distributed Communication
Authors	James W. Hong and James P. Black
Abstract	In our work, we seek to reduce the complexity of communication in distributed systems. We present the Buffer and Queue Model, which consists of a set of simple standards and tools that provide an effcient and consistent programming interface that can be used to implement a great variety of communication interactions both within and among various types of paradigms, abstractions, and entities. The Buffer-Queue protocol extends this consistent programming interface transparently to a distributed environment. We give examples of how various complex communication facilities may be developed using the Buffer and Queue paradigm.
Date	July 1991
Report	A Generic Paradigm for Efficient Distributed Communication (PDF)			Compressed DVI: A Generic Paradigm for Efficient Distributed Communication (PDF) (DVI.Z)

CS-91-33
Title	Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of Odes
Authors	K. R. Jackson and W. L. Seward
Abstract	Iterative linear equation solvers have been shown to be effective in codes for large systems of stiff initial-value problems for ordinary differential equations (ODEs). While preconditioned iterative methods are required in general for effciency and robustness, unpreconditioned methods may be cheaper over some ranges of the interval of integration. In this paper, we develop a strategy for switching between unpreconditioned and preconditioned iterative methods depending on the amount of work being done in the iterative solver and properties of the matrix being solved. This strategy is combined with a "type-insensitive" approach to the choice of formula used in the ODE code to develop a method that makes a smooth transition between nonstiff and stiff regimes in the interval of integration. We find that, as expected, for some large systems of ODEs, there may be a considerable saving in execution time when the type-insensitive approach is used. If there is a region of the integration that is "mildly" stiff, switching between unpreconditioned and preconditioned iterative methods also increases the effciency of the code significantly. Key words:type-insensitive ODE code, iterative linear solver, preconditioning. AMS(MOS) subject classifications:65L05, 65F10.
Date	July 1991
Report	Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of Odes (PDF)			Compressed DVI: Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of Odes (DVI.Z)

CS-91-32
Title	Numeration Systems, Linear Recurrences, and Regular Sets
Authors	J. O. Shallit
Abstract	Abstract (PDF)
Date	July 1991 (Revised November 1991)
Report	Numeration Systems, Linear Recurrences, and Regular Sets (PDF)			Compressed DVI: Numeration Systems, Linear Recurrences, and Regular Sets (DVI.Z)

CS-91-30
Title	Some Facts About Continued Fractions That Should Be Better Known
Authors	J. O. Shallit
Abstract	In this report I will give proofs of some simple theorems concerning continued fractions that are known to the cognoscenti, but for which proofs in the literature seem to be missing, incomplete, or hard to locate. In particular, I will give two proofs of the following "folk theorem": if 5 is an irrational number whose continued fraction has bounded partial quotients, then any non-trivial linear fractional transformation of 5 also has bounded partial quotients. The second proof is of interest because it uses the connection between continued fractions and finite automata first enunciated by G. N. Raney [R]. I will assume that the reader knows basic facts about continued fractions, at the level of [HW, Chapter X]. Note to the reader: It is intended that this report will eventually form a part of a longer article with the same name, written in collaboration with A. J. van der Poorten.
Date	July 1991
Report	Some Facts About Continued Fractions That Should Be Better Known (PDF)			Compressed DVI: Some Facts About Continued Fractions That Should Be Better Known (DVI.Z)

CS-91-27
Title	Numerical Solution of a Turning Point Problem
Authors	W.-P. Tang
Abstract	Abstract (PDF)
Date	July 1991
Report	Numerical Solution of a Turning Point Problem (PDF)			Compressed DVI: Numerical Solution of a Turning Point Problem (DVI.Z)

CS-91-17
Title	An Implementation and Evaluation of a Hierarchical Nonlinear Planner
Authors	Steven G. Woods
Abstract	Planning is the process of generating sequences of actions in order to provide a method for agents to modify the state of the world in which they exist. It is well known that the application of abstraction can greatly reduce the search involved in creating plans. In this talk, an empirical evaluation of several different approaches to reducing search in AbTweak, an abstract nonlinear planning system, are presented. To solve a complex problem using abstraction, one would like to protect parts of the abstract solution that have already been completed during the abstract plan refinement. However, it has not been well understood how this protection can be done profitably; some subgoal protection may indeed result in a decrease in efficiency. The Monotonic Property has been proposed as a form of goal protection in abstract planning. Different versions of this property are investigated with respect to their effect on planning performance in several domains. Furthermore, a series of empirical tests of the utility of the properties are presented, along with an evaluation of different search strategies for abstract planning. In addition, we present a novel abstract planning control strategy known as LeftWedge. This strategy adds a depth-first flavour to a complete search strategy by taking advantage of the fact that less abstract solutions are generally closer to a concrete level solution than more abstract ones. The relative benefit of this approach under various criticality assignments is demonstrated through comparisons with breadth-first strategy. Furthermore, two subgoal selection strategies are presented and compared empirically.
Date	May 1991
Report	An Implementation and Evaluation of a Hierarchical Nonlinear Planner (PDF)			Compressed PostScript: An Implementation and Evaluation of a Hierarchical Nonlinear Planner (PS.Z)

CS-91-14
Title	Introducing a Multi-Dimensional User Model to Tailor Natural Language Generation
Authors	J. Chu
Abstract	Previous work has shown that it is important to include user modelling in question answering systems in order to tailor the output. In this thesis, we develop a natural language response generation model that handles both definitional and procedural questions, and employs a multi-dimensional user model. The various attributes of the user recorded in the user model include the user's role, domain knowledge, preferences, interests, receptivity and memory capability. We also address how to represent the user's view of a knowledge base to then tailor generation to that user's view, and introduce a representation for knowledge bases with property inheritance based on the Telos system. We further specify how this multi-dimensional user model influences different stages of McKeown style generation, on determining question type, deciding relevant knowledge, selecting schema, instantiating predicates, and selecting predicates. An algorithm is proposed to describe how the generation process can be tailored according to these influences, and some examples are presented to show that the output is desirable. We also address the problem of conflicts arising from the variation in response generation suggested by different user model attributes and use various weighting schemes to resolve them. Furthermore, we include a procedure for updating the user model after each interaction which also enables the algorithm to be used over multiple sessions, with up-to-date information about the users.
Date	April 1991
Report	Introducing a Multi-Dimensional User Model to Tailor Natural Language Generation (PDF)			Compressed PostScript: Introducing a Multi-Dimensional User Model to Tailor Natural Language Generation (PS.Z)

CS-91-11
Title	Probabilistic Complexity Classes
Authors	A. Lopez-Ortiz
Abstract	The purpose of this work is to present an overview of the class of problems solvable in probabilistic polynomial time with double sided error (PP). We explore the relationship of PP to other complexity classes, in particular NP and the polynomial hierarchy, and discuss closure under some standard operations such as intersection and complementation. New proofs are given of some results from the literature using techniques developed by the author.
Date	March 1991
Report	Probabilistic Complexity Classes (PDF)			Compressed DVI: Probabilistic Complexity Classes (DVI.Z)

CS-91-09
Title	Reducing Communication to a Buffer and Queue Model
Authors	James W. Hong and James P. Black
Abstract	In our work, we seek to reduce the communication problem to its critical concepts and build a simple, effcient, and general commu- nication paradigm based on these concepts. We present the Buffer and Queue Model, which contains a set of communication abstrac- tions and primitives which is simple and general, rigorous and flexi- ble, low-level and extensible. We show how this model seeks to utilize the effciencies of shared memory communication while providing a universal communications interface between various types of entities across a wide spectrum of environments. We give examples of how various complex communication facilities may be developed from this low-level communication system.
Date	March 1991
Report	Reducing Communication to a Buffer and Queue Model (PDF)			Compressed DVI: Reducing Communication to a Buffer and Queue Model (DVI.Z)

CS-91-04
Title	Preconditioned Conjugate Gradient Methods for Incompressible Navier-Stokes Equations
Authors	P. Chin, E. F. D'Azevedo, P. A. Forsyth, & W.-P. Tang
Abstract	A robust technique for solving primitive-variable formulations of the incompressible Navier-Stokes equations is to use Newton iteration for the fully-implicit nonlinear equations. A direct sparse matrix method can be used to solve the Jacobian but is costly for large problems; an alternative is to use an iterative matrix method. This paper investigates effective ways of using a conjugate gradient type method with an incomplete LU factorization preconditioner for two-dimensional incompressible viscous 0ow problems. Special attention is paid to the ordering of unknowns, with emphasis on a minimum updating matrix (MUM) ordering. Numerical results are given for several test problems.
Date	January 1991
Report	Preconditioned Conjugate Gradient Methods for Incompressible Navier-Stokes Equations (PDF)			Compressed DVI: Preconditioned Conjugate Gradient Methods for Incompressible Navier-Stokes Equations (DVI.Z)