CS Theses & Dissertations 1993

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

A Metric-based Theory of test selection and coverage for Communication Protocols
Alilovic-Curgus, Jadranka
URI : http://hdl.handle.net/2429/1871
Degree : Doctor of Philosophy – PhD
Graduation Date : 1993-11
Supervisor : Dr. Vuong

A metric-based theory is developed that gives a solution to the problem of test selection and coverage evaluation for the control behaviour of network protocol implementations. The key idea is that a fast, completely automated process can uniformly cover the execution subspace of a network protocol control behaviour when characterized by appropriate metric functions, each concerned with some aspect of the protocol behaviour. Efficient systematic approximation of complex systems behaviours is a crucial problem in software testing. This thesis gives a theoretically sound and completely automated solution to the approximation problem for the control behaviour space of network protocols generated by many concurrent and highly recursive network connections. This objective is accomplished in a series of steps. First, a metric-based theory is developed which introduces a rigorous mathematical treatment of the discipline of testing, through the definition of testing distance, test coverage metrics, and metric-based test selection method. It involves a metric characterization of infinite trace sets of protocol behaviour within complete and totally bounded metric spaces, and captures approximations of different patterns of system behaviour due to recursion and parallelism. It is shown that classes of fault coverages of well known protocol test methods form a metric hierarchy within these metric spaces. Next, a general mathematical framework is developed for reasoning about the interoperability of communicating systems. An interoperability relation is obtained which gives a theoretical upper bound for the test selection process. The two threads are drawn together in a specific test selection algorithm, showing that the generation of arbitrarily dense sets of test sequences that approximate some original test suite to some target accuracy within the theoretical upper bound, is a convergent process. Finally, the theory itself is tested on the examples of a multi-media network protocol. It is shown that very high densities of selected sets and coverage calculation can be achieved within reasonable time limits in a completely automated manner. These results indicate that there is no practical impediment to applying rigorous theoretical treatment to the discipline of testing for the case of systems that derive their complexity from highly concurrent and recursive subprocesses.

3D Task Performance Using Head-Coupled Stereo Displays
Arthur, Kevin Wayne
URI : http://hdl.handle.net/2429/2633
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Booth

A Conditional Model of Abduction
Becher, Veronica
URI : http://hdl.handle.net/2429/1281
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Boutilier

A Model Checker for Statecharts (Linking Case Tools with Formal Methods)
Day, Nancy
URI : http://hdl.handle.net/2429/1638
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Joyce

A Hierarchical Software Development for Performance-Oriented Parallel Programming
Feldcamp, David
URI : http://hdl.handle.net/2429/1360
Degree : Master of Science – MSc
Graduation Date : 1993-05

Local Illumination Models from Surface Geometry
Huo, Gang
URI : http://hdl.handle.net/2429/1992
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Fournier

A Real-Time 3D Motion Tracking System
Kam, Johnny W.Y.
URI : http://hdl.handle.net/2429/2545
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Little

A Formal Characterization of a Domain-Independent Abductive Reasoning System
Kean, Alex
URI : http://hdl.handle.net/2429/1751
Degree : Doctor of Philosophy – PhD
Graduation Date : 1993-05
Supervisor : Dr. Mackworth

Abduction is a logical inference technique used in explanation finding and a variety of consequence finding. One application domain that stands out in utilizing abduction is automated diagnostic reasoning. This thesis provides a formal specification and methods of computation for a domain independent propositional abductive reasoning system. On the competence level, specifications are defined for domain independent abductive reasoning in terms of finding assumption-based explanations, direct consequences, extensions and a protocol for revising assumptions. On the performance level, computational strategies for performing abduction according to the defined specifications are studied. The computational framework for a propositional abductive inference engine, the Clause Management System (CMS), is presented. The computational framework of the CMS uses the notion of prime implicates to represent its knowledge base. As a result, the algorithm to update the CMS knowledge base is an incremental algorithm for generating prime implicates - the first reported. Coupled with the notion of reasoning with assumptions, the abduction framework is extended to include inquiry about defeasible assumptions. The notion of assumption-based reasoning presented includes finding assumption-based explanations, direct consequences and extensions. Extending the computational framework of the CMS, an Assumption-based Clause Management System (ACMS) that computes the above functions, is presented. A simple protocol for use by domain specific applications interacting with the ACMS is proposed. Included in the protocol is a method to perform revision of assumptions. The first algorithm to perform incremental deletion of prime implicates is also presented. Additionally, a new notion of approximated abduction together with a set of approximation strategies, namely knowledge-guided and resource-bounded approximation, are proposed. The goal of these studies is to propose a framework for incorporating knowledge-guided and resource-bounded approximation into computational abduction. The potential benefit might be the discovery of a useful and tractable approximation strategy. The specification of a domain independent propositional abductive reasoning system is the main achievement of this thesis. The resulting abductive reasoning system, the ACMS, is adaptable to a wide spectrum of domain specific applications. The ACMS can free designers from repeatedly building specialized abductive inference engines, and instead allow them to concentrate their effort on knowledge engineering and problem solving.

Trace Analysis of Protocols based on Formal Concurrent Specifications
Kim, Myungchul
URI : http://hdl.handle.net/2429/1866
Degree : Doctor of Philosophy – PhD
Graduation Date : 1993-05
Supervisors : Dr. Chanson, Dr. Vuong

To increase the probability of computers communicating reliably with one another, protocol implementations must be tested for conformance to the standards on which they are based. Test case generation and trace analysis are two important topics in protocol testing research. Most of the work so far has focused on test case generation rather than trace analysis. Furthermore, most of the work has dealt only with the sequential aspects of the protocol specifications. In this thesis, a model that combines the two functions of test case generation and trace analysis in a unified framework is presented. The model, which is based on single module extended finite state machines, handles both control and data flows for single module specifications. Symbolic evaluation is used to detect and delete infeasible paths that may be generated. Practical considerations which may occur in a real test environment, such as out of order message sequences, are also addressed. A prototype implementation of the unified model was completed. The application of this method to X.25 LAPB shows that it can manage frame collision and control and data flows of the protocol rigorously. The model is extended to study the trace analysis of concurrent specifications based on multi-module extended finite state machines. This is done by introducing two additional models- concurrency and traceability. The concurrency model deals with concurrent properties such as concurrent events, concurrency blocks, global states, concurrency measures, deadlocks and data races which do not arise in sequential or single module specifications. The concurrency model allows a high-level abstraction to be used for understanding and analyzing concurrent behaviors. We also show how concurrency measures can be computed efficiently based on the concept of concurrency blocks. The traceability concept is needed to obtain the precise order of input/output messages of a module without state space explosion. This model for the trace analysis of concurrent specifications without translating them into their sequential equivalence is formalized and proposed for application to multi-module specification, multi-party testing and interoperability testing. The viability of the proposed methodology which can be applied to any specifications based on extended finite state machines is demonstrated using Estelle specifications in the thesis.

Viewpoint Invariant Surace Reconstruction from Gradient Data
King, Yossarian Yggy
URI : http://hdl.handle.net/2429/2032
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Woodham

Post-Processed Shadow Determination for Composition of Depth Images
Krywolt, Russell W.
URI : http://hdl.handle.net/2429/2054
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Fournier

Orientation-Based Representations of Shape and Attitude Determination
Li, Ying
URI : http://hdl.handle.net/2429/1667
Degree : Doctor of Philosophy – PhD
Graduation Date : 1993-05
Supervisor : Dr. Woodham

The three rotational degrees of freedom between the coordinate system of a sensed object and that of a viewer define the attitude of the object. Orientation-based representations record 3-D surface properties as a function of position on the unit sphere. All orientation-based representations considered share a desirable property: the representation of a rotated object is equal to the rotated representation of the object before rotation. This makes the orientation-based representations well-suited to the task of attitude determination. The mathematical background for orientation-based representations of shape is presented in a consistent framework. Among the orientation-based representations considered, the support function is one-to-one for convex bodies, the curvature functions are one-to-one for convex bodies up to a translation and the radial function is one-to-one for starshaped sets. Using combinations of the support function and the curvature functions for convex bodies, the problem of attitude determination is transformed into an optimization problem. Previous mathematical results on the radial function for convex objects are extended to starshaped objects and the problem of attitude determination by the radial function also is transformed into an optimization problem. Solutions to the optimization problems exist and can be effectively computed using standard numerical methods. A proof-of-concept system has been implemented and experiments conducted both on synthesized data and on real objects using surface data derived from photometric stereo. Experimental results verify the theoretical solutions. Novel contributions of the thesis include: the representation of smooth convex objects by the support function and curvature functions; the definition of a new orientation-based representation for starshaped sets using the 3-D radial function; and solutions to the 3-Dattitude determination problem using the aforementioned representations. In particular, the scope of orientation-based representations has been extended, both in theory and in practice, from convexity to starshapedness.

A Virtual Machine Approach to Parallel Debugging
Lin, Kunhua
URI : http://hdl.handle.net/2429/2169
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Wagner

On the Complexity Theory of Switching Networks
Lin, Geng
URI : http://hdl.handle.net/2429/1662
Degree : Doctor of Philosophy – PhD
Graduation Date : 1993-05
Supervisor : Dr. Pippenger

Fast and efficient communications are essential to the success of large-scale multiprocessor parallel processing systems, distributed processing systems, and telecommunication systems. Switching networks are constructed to support simultaneous communications (of data, voice, image and video) in these systems. This thesis focuses on the complexity theory for the construction of switching networks, with primary emphasis on (a) the complexity of the networks, as measured by the size (number of switches), the depth (largest number of switches on any communication path) and the degree (the largest fan-out of a switch); (b) the complexity of the routing algorithms of the networks, as measured by the time and space; and (c) the fault-tolerance of the networks. We present the first simultaneous "weakly optimal" solutions for the explicit construction of non-blocking networks, and the design of the parallel routing algorithms. "Weakly optimal" here means that all measures of complexity (size and depth of the network, time for the algorithm, and space for the data-structure) are within one or more logarithmic factors of their smallest possible values. We also consider routing algorithms for networks with probabilistic traffic. We present an optimal routing algorithm for series-parallel networks (which includes a broad range of useful connection networks for parallel architectures, e.g., butterflies and Bend networks). The algorithm has an asymptotically minimum expected time among all routing algorithms. We consider fault-tolerant switching networks under a random switch-failure model. We prove lower bounds for the size and depth of fault-tolerant non-blocking networks, rearrangeable networks and superconcentrators. And we explicitly construct such networks with optimal sizes and depths. We also consider fault-tolerant planar switching networks, which become attractive because of the rapid advances in VLSI technology. We prove lower bounds for the degrees of vertices of fault-tolerant planar rearrangeable networks and superconcentrators. We construct such fault-tolerant planar networks with optimal sizes and degrees.

A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane or Simple Paths in a Complex World
McAllister, Michael
URI : http://hdl.handle.net/2429/2000
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Snoeyink

Improving the Portability of Natural Language Interfaces through Learning
McClement, Gregory John
URI : http://hdl.handle.net/2429/1985
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Rosenberg

Microcomputers in Psychological Experimentation Headturn:  A Case Study
Pidcock, Brian
URI : http://hdl.handle.net/2429/1655
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Booth

The Raven Kernel:  A Microkernel for Shared Memory Multiprocessors
Ritchie, Stuart Duncan
URI : http://hdl.handle.net/2429/1945
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Neufeld

Real-Time Intelligent Behaviour in Dynamic Environments:  Soccer-Playing Robots
Sahota, Michael  Kuljit Singh
URI : http://hdl.handle.net/2429/1440
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Mackworth

How Fast can ASN.1 Encoding Rules go?
Sample, Michael
URI : http://hdl.handle.net/2429/2370
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Neufeld

The Implementation of Sequential and Parallel Algorithms for Solving almost Block Bidiagonal Systems
Song, Yan
URI : http://hdl.handle.net/2429/2584
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Varah

Simulating and Visualizing Marine Oil Spills
Van Blankenstein, David
URI : http://hdl.handle.net/2429/2065
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Fournier

Multi-Resolution Surface Approximation for Animation
Wang, Lifeng
URI : http://hdl.handle.net/2429/1877
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Forsey

Object Tracking in Distributed Systems
Xu, Yingchun
URI : http://hdl.handle.net/2429/2342
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Hutchinson

An Object-Oriented Design for Hierarchical B-Spline Surfaces
Yan, Hailin
URI : http://hdl.handle.net/2429/1864
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Forsey

A New Approach to Generating and Selecting Test Sequence for Conformance Testing
Zhou, Limin (Lucy)
URI : http://hdl.handle.net/2429/2709
Degree : Master of Science – MSc
Graduation Date : 1993-05
Supervisor : Dr. Chanson

The Registration of Multimodality Medical Scans
Zuk, Torre Dana
URI : http://hdl.handle.net/2429/1577
Degree : Master of Science – MSc
Graduation Date : 1993-11
Supervisor : Dr. Booth, Dr. Atkins (SFU)