CS Theses & Dissertations 1989

For 1989 graduation dates (in alphabetical order by last name):

Resource Management in Application Level Message Transfer Systems
Brachman, Barry Jeffrey
URI : http://hdl.handle.net/2429/29060
Degree : Doctor of Philosophy – PhD
Graduation Date : 1989-11
Supervisor : Dr. Chanson

This thesis is concerned with the design of the resource management components of application level, store-and-forward message transfer systems. Although these systems have for some time been used to transport electronic mail, there has been little investigation into designs that emphasize performance and correctness aspects. Current message transfer systems are loosely structured in that there is little, if any, end-to-end resource management. The thesis begins by characterizing the message handling environment and comparing the message transfer approach to that of connection-based file transfer. Current message transfer systems have a fundamental limitation in that the largest message that can be transferred is determined by the amount of storage available at any of the intermediate hosts along the message's route. Major components of a message transfer system and design alternatives are discussed. Existing schemes that deal with solutions designed for lower networking levels are reviewed and shown to be inadequate in addressing the problems in the message handling environment. A framework for designing message transfer systems is presented. Systems adhering to the design methodology address performance issues in a structured way. Two new techniques are central to this framework: message fragmentation and the message stream. Message fragmentation is introduced as a means of delivering arbitrary size messages. The message stream abstraction is the basis of flow control and congestion control. A hierarchical technique for deadlock prevention in the message handling environment is introduced. In this method, the structured buffer pool approach is used as a top level and is integrated with a second method at the bottom level to produce a practical, deadlock-free message transfer system. Methods for providing transit buffer management and recipient buffer space allocation are discussed. A simulation study of some of the performance aspects of message streams and recipient buffer space allocation is presented.

An Algorithm for solving Index 1 Differential Algebraic Equations in Boundary Value Problems
Chan, Sek Yuen Pat
URI : http://hdl.handle.net/2429/27404
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Ascher

A Qualitative Representation for Manipulator Kinematics and Other Vector and Scalar Fields
Dangelmaier, Heidi Therese
URI : http://hdl.handle.net/2429/28970
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Little

A Request/Response Protocol to Support ISO Remote Operations
Goldberg, Murray Warren
URI : http://hdl.handle.net/2429/27456
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Neufeld

A Data Management Strategy for Transportable Natural Language Interfaces
Johnson, Julia Ann
URI : http://hdl.handle.net/2429/29119
Degree : Doctor of Philosophy – PhD
Graduation Date : 1989-11
Supervisor : Dr. Rosenberg

This thesis focuses on the problem of designing a highly portable domain independent natural language interface for standard relational database systems. It is argued that a careful strategy for providing the natural language interface (NLI) with morphological, syntactic, and semantic knowledge about the subject of discourse and the database is needed to make the NLI portable from one subject area and database to another. There has been a great deal of interest recently in utilizing the database system to provide that knowledge. Previous approaches attempted to solve this challenging problem by capturing knowledge from the relational database (RDB) schema, but were unsatisfactory for the following reasons: 1.) RDB schemas contain referential ambiguities which seriously limit their usefulness as a knowledge representation strategy for NL understanding. 2.) Knowledge captured from the RDB schema is sensitive to arbitrary decisions made by the designer of the schema. In our work we provide a new solution by applying a conceptual model for database schema design to the design of a portable natural language interface. It has been our observation that the process used for adapting the natural language interface to a new subject area and database overlaps considerably with the process of designing the database schema. Based on this important observation, we design an enhanced natural language interface with the following significant features: complete independence of the linguistic component from the database component, economies in attaching the natural language and DB components, and sharing of knowledge about the relationships in the subject of discourse for database schema design and NL understanding.

Issues on Design and Implementation of Protocol Test Systems
Lee, Bernard P.
URI : http://hdl.handle.net/2429/27580
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Chanson

Design and Implementation of Ferry Clip Test System
Parakh, Neville Jehangir
URI : http://hdl.handle.net/2429/27613
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Chanson

Algorithms for Embeddik Binary Trees into Hypercubes
Smedley, Garth
URI : http://hdl.handle.net/2429/27635
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Wagner

Distributed Object Management in Raven
Sutanto, Marcel
URI : http://hdl.handle.net/2429/27674
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Neufeld

Bar-Representable Visibility Graphs and a Related Network Flow Problem
Wismath, Stephen Kenneth
URI : http://hdl.handle.net/2429/29320
Degree : Doctor of Philosophy – PhD
Graduation Date : 1989-11
Supervisor : Dr. Kirkpatrick

A bar layout is a set of vertically oriented non-intersecting line segments in the plane called bars. The visibility graph associated with a layout is defined as the graph whose vertices correspond to the bars and whose edges represent the horizontal visibilities between pairs of bars. This dissertation is concerned with the characterization of bar-representable graphs: those graphs which are the visibility graphs of some bar layout. A polynomial time algorithm for determining if a given graph is bar-representable, and the subsequent construction of an associated layout are provided. Weighted and directed versions of the problem are also formulated and solved; in particular, polynomial time algorithms for the layout of such graphs are developed. The Planar Full Flow problem is to determine a plane embedding and an (acyclic) orientation of an undirected planar network that admits a feasible flow, that uses all arcs (except those incident upon the source or sink) to full capacity and maintains planarity. The connection of this flow problem to bar-representable graphs is exploited to solve the weighted case of the latter. As evidence that both the acyclicity and planarity constraints are necessary to obtain a polynomial algorithm for this problem, two natural variants of the Full Flow problem are shown to be strongly NP-Complete.

A Behavioral Approach to Open Robot Systems:  Design and Programming
Zhang, Ying
URI : http://hdl.handle.net/2429/27754
Degree : Master of Science – MSc
Graduation Date : 1989-11
Supervisor : Dr. Mackworth