CS Theses & Dissertations 1988

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

Tiebreaking the minimum degree algorithm for ordering sparse symmetric positive definite matrices
Cavers, Ian Alfred
URI : http://hdl.handle.net/2429/27855
Degree : Master of Science – MSc
Graduation Date : 1988-05
Supervisor : Dr. Varah

Issues in Designing a Distributed, Object-Based Programming System
Chin, Roger Steven
URI : http://hdl.handle.net/2429/27858
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisor : Dr. Chanson

A Principal-Based System for Natural language Analysis and Translation
Crocker, Matthew Walter
URI : http://hdl.handle.net/2429/27863
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisors : Dr. Rochemont, Dr. Abramson

Teaching Prolog using Intelligent Computer-Assisted Instruction and a graphical trace
Fogel, Earl
URI : http://hdl.handle.net/2429/27923
Degree : Master of Science – MSc
Graduation Date : 1988-05
Supervisor : Dr. Mackworth

Design and Implementation of a token bus protocol for a power line local
Gu, Hua
URI : http://hdl.handle.net/2429/27930
Degree : Master of Science – MSc
Graduation Date : 1988-05
Supervisor : Dr. Vuong

Randomized Distributed Computing on Rings
Higham, Lisa
URI : http://hdl.handle.net/2429/28839
Degree : Doctor of Philosophy – PhD
Graduation Date : 1988-11
Supervisor : Dr. Kirkpatrick

The communication complexity of fundamental problems in distributed computing on an asynchronous ring are examined from both the algorithmic and lower bound perspective. A detailed study is made of the effect on complexity of a number of assumptions about the algorithms. Randomization is shown to influence both the computability and complexity of several problems. Communication complexity is also shown to exhibit varying degrees of sensitivity to additional parameters including admissibility of error, kind of error, knowledge of ring size, termination requirements, and the existence of identifiers. A unified collection of formal models of distributed computation on asynchronous rings is developed which captures the essential characteristics of a spectrum of distributed algorithms those that are error free (deterministic, Las Vegas, and nondeterministic), and those that err with small probability (Monte Carlo and nondeterministic/probabilistic). The nondeterministic and nondeterministic/probabilistic models are introduced as natural generalizations of the Las Vegas and Monte Carlo models respectively, and prove useful in deriving lower bounds. The unification helps to clarify the essential differences between the progressively more general notions of a distributed algorithm. In addition, the models reveal the sensitivity of various problems to the parameters listed above. Complexity bounds derived using these models typically vary depending on the type of algorithm being investigated. The lower bounds are complemented by algorithms with matching complexity while frequently the lower bounds hold on even more powerful models than those required by the algorithms. Among the algorithms and lower bounds presented are two specific results which stand out because of their relative significance. 1. If g is any nonconstant cyclic function of n variables, then any nondeterministic algorithm for computing g on an anonymous ring of size n has complexity [Formula Omitted] bits of communication; and, there is a is nonconstant cyclic boolean function [Formula Omitted], such that [Formula Omitted] can be computed by a Las Vegas algorithm in [Formula Omitted] expected bits of communication on a ring of size n. 2. The expected complexity of computing AND (and a number of other natural functions) on a ring of fixed size n in the Monte Carlo model is [Formula Omitted] messages and bits where [Formula Omitted] is the allowable probability of error.

Replication Patterns for Polygon Fill Algorithms
Kreykenbohm, Michael Walter
URI : http://hdl.handle.net/2429/27974
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisor : Dr. McLean

Logic Programming as a Formalism for Specification and Implementation of Computer Systems
Kusalik, Anthony Joseph
URI : http://hdl.handle.net/2429/28848
Degree : Doctor of Philosophy – PhD
Graduation Date : 1988-11

The expressive power of logic-programming languages allows utilization of conventional constructs in development of computer systems based on logic programming. However, logic-programming languages have many novel features and capabilities. This thesis investigates how advantage can be taken of these features in the development of a logic-based computer system. It demonstrates that innovative approaches to software, hardware, and computer system design and implementation are feasible in a logic-programming context and often preferable to adaptation of conventional ones. The investigation centers on three main ideas: executable specification, declarative I/O, and implementation through transformation and meta-interpretation. A particular class of languages supporting parallel computation, committed-choice logic-programming languages, are emphasized. One member of this class, Concurrent Prolog, serves as the machine, specification, and implementation language. The investigation has several facets. Hardware, software, and overall system models for a logic-based computer are determined and examined. The models are described by logic programs. The computer system is represented as a goal for resolution. The clauses involved in the subsequent reduction steps constitute its specification. The same clauses also describe the manner in which the computer system is initiated. Frameworks are given for developing models of peripheral devices whose actions and interactions can be declaratively expressed. Interactions do not rely on side-effects or destructive assignment, and are term-based. A methodology is presented for realizing (prototypic) implementations from device specifications. The methodology is based on source-to-source transformation and meta-interpretation. A magnetic disk memory is used as a representative example, resulting in an innovative approach to secondary storage in a logic-programming environment. Building on these accomplishments, a file system for a logic-based computer system is developed. The file system follows a simple model and supports term-based, declarative I/O. Throughout the thesis, features of the logic-programming paradigm are demonstrated and exploited. Interesting and innovative concepts established include: device processes and device processors; restartable and perpetual devices and systems; peripheral devices modelled as function computations or independent logical (inference) systems; unique, compact representations of terms; lazy term expansion; files systems as perpetual processes maintaining local states; and term- and unification-based file abstractions. Logic programs are the sole formalism for specifications and implementations.

xpProlog:  High Performance extended pure Prolog
Lüdemann, Peter Gerald
URI : http://hdl.handle.net/2429/27982
Degree : Master of Science – MSc
Graduation Date : 1988-05

Solving for Relative Orientation and Depth
McReynolds, Daniel Peter
URI : http://hdl.handle.net/2429/28023
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisor : Dr. Lowe

A Computation Vision System for Joint Angle Sensing
Mulligan, I. Jane
URI : http://hdl.handle.net/2429/28029
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisors : Dr. Mackworth, Dr. Lawrence

On Implementing the ISO Virtual Terminal Protocol for a UNIX 4.2 BSD Environment
Ng, Chi Ho Steve
URI : http://hdl.handle.net/2429/28292
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisor : Dr. Neufeld

The Semantics and Transformation of Imperative Programs Using Horn Clauses
Ross, Brian James
URI : http://hdl.handle.net/2429/28326
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisor : Dr. Abramson

Group Communication in Distributed Operating System T-Shoshin
See, Helen Lim
URI : http://hdl.handle.net/2429/28395
Degree : Master of Science – MSc
Graduation Date : 1988-05
Supervisor : Dr. Vuong

A Graphical Extension for Pascal based on the Graphical Kernel System
Starr, Cynthia Louise
URI : http://hdl.handle.net/2429/28402
Degree : Master of Science – MSc
Graduation Date : 1988-05
Supervisor : Dr. Schrack

A Methodology for Database Management of time-variant encodings and/or missing information
Threlfall, William John
URI : http://hdl.handle.net/2429/28349
Degree : Master of Science – MSc
Graduation Date : 1988-05
Supervisor : Dr. Gilmore

On an Implementation of Abstract Interpretation
Westcott, Doug
URI : http://hdl.handle.net/2429/28354
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisor : Dr. Abramson

ASN.1-C Compiler for Automatic Protocol Implementation
Yang, Yueli
URI : http://hdl.handle.net/2429/28359
Degree : Master of Science – MSc
Graduation Date : 1988-11
Supervisor : Dr. Neufeld