CS Theses & Dissertations 1985

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

Remote Interprocess Communication and its performance in team shoshin
Acton, Donald
URI : http://hdl.handle.net/2429/24449
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Neufeld

The role of exception mechanisms in software systems design
Atkins, Margaret Stella
URI : http://hdl.handle.net/2429/25555
Degree : Doctor of Philosophy – PhD
Graduation Date : 1985-11
Supervisor : Dr. Vuong

Exception handling is a crucial aspect of practical programming, particularly in systems allowing logical concurrency such as multi-process distributed systems. First, a survey of existing exception handling mechanisms in operating systems is performed, which shows a diversity of implementations, depending on the process model and the method of inter-process communication. The thesis then develops a model for designing software which exploits the different mechanisms for handling normal and exceptional events. The model is applicable in many multi-process programming environments, and not only preserves modularity, but also enhances efficiency and reliability, while often increasing concurrency. To derive such a model, exceptions in multi-process software are classified primarily according to the program level at which they are detected and handled. Server-to-client exceptions are of particular interest because of their ubiquity; these are exceptions detected by a server and handled by a client. The model treats systems programs as event driven, and proposes dividing the events into normal or exceptional, according to the cost and mechanisms for handling them. Techniques are described for designing software according to three criteria: minimising the average run-time, minimising the exception processing time, and incrementally increasing the program's functionality. Many examples are given which illustrate the use of the general model. Program paradigms in several languages and in several systems are introduced to model features which are system dependent, through illustrative examples for asynchronous i/o multiplexing, and for exception notification from a server to its client or clients. Finally, some programs which have been implemented according to the rules of the model are described and compared with their more conventional counterparts. These programs illustrate the practicality and usefulness of the model for diverse systems and concurrent environments.

Implementation of the Cambridge ring protocols on the sun workstation
Chan, Linda
URI : http://hdl.handle.net/2429/24591
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Chanson

On the Implementation of Multigrid Methods for the Numeration Solution of Partial Differential Equations
Delaney, Allen Daniel
URI : http://hdl.handle.net/2429/24628
Degree : Master of Science – MSc
Graduation Date : 1985-05
Supervisor : Dr. Ascher

Semi-Automatic Implementation of Network Protocols
Ford, Daniel Alexander
URI : http://hdl.handle.net/2429/24665
Degree : Master of Science – MSc
Graduation Date : 1985-05
Supervisor : Dr. Vuong

A Logic Data model for the machine representation of knowledge
Goebel, Randolph G.
URI : http://hdl.handle.net/2429/25799
Degree : Doctor of Philosophy – PhD
Graduation Date : 1985-11
Supervisor : Dr. Reiter

DLOG is a logic-based data model developed to show how logic-programming can combine contributions of Data Base Management (DBM) and Artificial Intelligence (AI). The DLOG specification includes a language syntax, a proof (or query evaluation) procedure, a description of the language's semantics, and a specification of the relationships between assertions, queries, and application databases. DLOG's data description language is the Horn clause subset of first order logic [Kowalski79, Kowalski81], augmented with descriptive terms and non-Horn integrity constraints. The descriptive terms are motivated by AI representation language ideas, specifically, the descriptive terms of the KRL language [Bobrow77]. A similar facility based on logical descriptions is provided in DLOG. DLOG permits the use of definite and indefinite descriptions of individuals and sets in queries and assertions. The meaning of DLOG's extended language is specified as Horn clauses that describe the relation between the basic language and the extensions. The experimental implementation is a Prolog program derived from that specification. The DLOG implementation relies on an extension to the standard Prolog proof procedure. This includes a "unification" procedure that matches embedded terms by recursively invoking the DLOG proof procedure (cf. LOGLISP [Robinson82]). The experimental system includes Prolog implementations of traditional database facilities (e.g., transactions, integrity constraints, data dictionaries, data manipulation language facilities), and an idea for using logic as the basis for heuristic interpretation of queries. This heuristic uses a notion of partial, match or sub-proof to produce assumptions under which plausible query answers can be derived. The experimental DLOG knowledge base management system is exercised by describing an undergraduate degree program. The example application is a description of the Bachelor of Computer Science degree requirements at The University of British Columbia. This application demonstrates how DLOG's descriptive terms provide a concise description of degree program knowledge, and how that knowledge is used to specify student programs and select program options.

Calibrating the Photographic Reproduction of Colour Digital Images
Heiss, Detlef Guntram
URI : http://hdl.handle.net/2429/24680
Degree : Master of Science – MSc
Graduation Date : 1985-05
Supervisor : Dr. Woodham

Solid Modelling using Linear Octree Representation
Ho, Sunny Sheung-Lai
URI : http://hdl.handle.net/2429/24684
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Schrack

Protocol Validation via Reachability Analysis:  An Implementation
Hui, Daniel
URI : http://hdl.handle.net/2429/24689
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Vuong

Coaxial Stereo and Scale-Based Matching
Katz, Itzhak
URI : http://hdl.handle.net/2429/24693
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Mackworth

A Message-based Remote Database Access Facility
Koorland, Neil Karl
URI : http://hdl.handle.net/2429/24831
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Gilmore

Recovering Shape and Determining Attitude from Extended Gaussian Images
Little, James
URI : http://hdl.handle.net/2429/25816
Degree : Doctor of Philosophy – PhD
Graduation Date : 1985-05
Supervisor : Dr. Woodham

This dissertation is concerned with surface representations which record surface properties as a function of surface orientation. The Extended Gaussian Image (EGI) of an object records the variation of surface area with surface orientation. When the object is polyhedral, the EGI takes the form of a set of vectors, one for each face, parallel to the outer surface normal of the face. The length of a vector is the area of the corresponding face. The EGI uniquely represents convex objects and is easily derived from conventional models of an object. An iterative algorithm is described which converts an EGI into an object model in terms of coordinates of vertices, edges, and faces. The algorithm converges to a solution by constrained optimization. There are two aspects to describing shape for polyhedral objects: first, the way in which faces intersect each other, termed the adjacency structure, and, second, the location of the faces in space. The latter may change without altering the former, but not vice versa. The algorithm for shape recovery determines both elements of shape. The continuous support function is described in terms of the area function for curves, permitting a qualitative comparison of the smoothness of the two functions. The next Section describes a method of curve segmentation based on extrema of the support function. Because the support function varies with translation, its behaviour under translation is studied, leading to proposals for several candidate centres of support. The study of these ideas suggests some interesting problems in computational geometry. The EGI has been applied to determine object attitude, the rotation in 3-space bringing a sample object into correspondence with a prototype. The methods developed for the inversion problem can be applied to attitude determination. Experiments show attitude determination using the new method to be more robust than area matching methods. The method given here can be applied at lower resolution of orientation, so that it is possible to sample the space of attitudes more densely, leading to increased accuracy in attitude determination. The discussion finally is broadened to include non-convex objects, where surface orientation is not unique. The generalizations of the EGI do not support shape reconstruction for arbitrary non-convex objects. However, surfaces of revolution do allow a natural generalization of the EGI. The topological structure of regions of constant sign of curvature is invariant under Euclidean motion, and may be useful for recognition tasks.

Using Discrimination Graphs to Represent Visual Knowledge
Mulder, Jan A.
URI : http://hdl.handle.net/2429/25943
Degree : Doctor of Philosophy – PhD
Graduation Date : 1985-11
Supervisor : Dr. Mackworth

This dissertation is concerned with the representation of visual knowledge. Image features often have many different local interpretations. As a result, visual interpretations are often ambiguous and hypothetical. In many model-based vision systems the problem of representing ambiguous and hypothetical interpretations is not very specifically addressed. Generally, specialization hierarchies are used to suppress a potential explosion in local interpretations. Such a solution has problems, as many local interpretations cannot be represented by a single hierarchy. As well, ambiguous and hypothetical interpretations tend to be represented along more than one knowledge representation dimension limiting modularity in representation and control. In this dissertation a better solution is proposed. Classes of objects which have local features with similar appearance in the image are represented by discrimination graphs. Such graphs are directed and acyclic. Their leaves represent classes of elementary objects. All other nodes represent abstract (and sometimes unnatural) classes of objects, which intensionally represent the set of elementary object classes that descend from them. Rather than interpreting each image feature as an elementary object, we use the abstract class that represents the complete set of possible (elementary) objects. Following the principle of least commitment, the interpretation of each image feature is repeatedly forced into more restrictive classes as the context for the image feature is expanded, until the image no longer provides subclassification information. This approach is called discrimination vision, and it has several attractive features. First, hypothetical and ambiguous interpretations can be represented along one knowledge representation dimension. Second, the number of hypotheses represented for a single image feature can be kept small. Third, in an interpretation graph competing hypotheses can be represented in the domain of a single variable. This often eliminates the need for restructuring the graph when a hypothesis is invalidated. Fourth, the problem of resolving ambiguity can be treated as a constraint satisfaction problem which is a well researched problem in Computational Vision. Our system has been implemented as Mapsee-3, a program for interpreting sketch maps. A hierarchical arc consistency algorithm has been used to deal with the inherently hierarchical discrimination graphs. Experimental data show that, for the domain implemented, this algorithm is more efficient than standard arc consistency algorithms.

A Numerical Investigation of Two boundary Element Methods
Quek, Vivian Mui Hoon
URI : http://hdl.handle.net/2429/24900
Degree : Master of Science – MSc
Graduation Date : 1985-05
Supervisor : Dr. Ascher

An Expert System Shell for Processing Logic Grammars
Salim, Juliani Susanti
URI : http://hdl.handle.net/2429/24912
Degree : Master of Science – MSc
Graduation Date : 1985-05
Supervisor : Dr. Ascher

A Model of Grammar Based on Principles of Government and Binding
Sharp, Randall
URI : http://hdl.handle.net/2429/24917
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Rochemont

Implementation of a Protocol Validation and Synthesis System
Tong, Darren Pong Choi
URI : http://hdl.handle.net/2429/25061
Degree : Master of Science – MSc
Graduation Date : 1985-05
Supervisor : Dr. Vuong

Specification- Verification of Protocols - The Significant Event Temporal Logic Technique
Tsiknis, George Konstantinos
URI : http://hdl.handle.net/2429/25047
Degree : Master of Science – MSc
Graduation Date : 1985-05
Supervisor : Dr. Gilmore

A Portable Natural Language Database Query System
White, Steven John
URI : http://hdl.handle.net/2429/25066
Degree : Master of Science – MSc
Graduation Date : 1985-11
Supervisor : Dr. Rosenberg