CS9556  

Title  Numerical Control Tool Path Generation using SpaceFilling Curves and Pixel Models  
Authors  D.P. Dragomatz  
Abstract  Two methods for generating numerical control tool paths have ap peared recently, one using pixel models, the other using Hilbert curves. The pixel model approach is able to represent many as pects of path generation, but requires large amounts of storage for physically large objects represented at high accuracy. The Hilbert curve approach uses the local refinement property of Hil bert spacefilling curves to create an adaptive sampling approach that increases the density of path points only where necessary. In this thesis, I propose and implement a hybrid technique that uses elements of each method, retaining the major benefits of both without incurring the storage costs of the pixel model. The scheme supports the creation of both roughing paths and surface machining paths, but is nonoptimal for the later. The addition of containment and exclusion zones to the method leads to a promising paradigm for partitioning object geometry into machin able regions.  
Date  December 1995  
Comments  Chapter 2 is a 35page discussion on issues in tool path generation mostly from a computational point of view. Chapter 3 is background material on spacefilling curves and pixel models. Chapter 4 describes the approach and shows some sample paths, including photographs of machined parts. Appendix A is a 36page classified bibliography of papers on various topics related to NC tool path generation. 

Report  Numerical Control Tool Path Generation using SpaceFilling Curves and Pixel Models (PS)  Compressed PostScript: Numerical Control Tool Path Generation using SpaceFilling Curves and Pixel Models (PS.Z) 
CS9554  

Title  Spline Extensions for the MAPLE Plot System  
Authors  Wolfgang Heidrich  
Abstract  Traditionally computer algebra systems use lines and polygons to represent mathematical functions graphically. While these geometric primitives can easily be rendered on conventional raster graphics hardware, a smooth representation using splines would provide a wider range of tradeoffs between image quality and rendering performance. Since modern computer graphics hardware directly supports rendering of spline objects, their use becomes more and more interesting. In this thesis we examine the possibilities for replacing traditional representations of functions and graphs by spline representations. We describe the use of \BSplines\ for interpolation and approximation, and discuss several approaches for generating parameterizations for these tasks. Finally we present some novel results regarding the use of rational splines for curve and surface fitting. 

Report  Spline Extensions for the MAPLE Plot System (PDF)  Compressed PostScript: Spline Extensions for the MAPLE Plot System (PS.Z) 
CS9553  

Title  A topological data structure for hierarchical planar subdivisions  
Authors  W. Celes F., L.H. de Figuiredo, M. Gattass, P.C. Carvalho  
Abstract  We introduce HPS, a new topological data structure that efficiently represents hierarchies of planar subdivisions, thus providing direct and efficient support for GIS concepts such as abstract generalizations and multiscale partitions. Unlike previous ad hoc solutions, HPS provides efficient access to adjacency information for each level and across levels, while storing the complete hierarchy in a single data structure, without duplications. HPS also provides topological operators that ensure global consistency. Like all topological data structures, HPS can be used as a framework onto which geometric and attribute information is placed: HPS explicitly handles attributes consistently with modeling, and naturally supports both topological and geometrical multiresolution representations. We also discuss how some typical applications in GIS, Digital Cartography, and Finite Element mesh generation can be improved with HPS. Keywords:topological data structures, hierarchical modeling, multiresolution, multiscale partitions, Geographic Information Systems 

Date  December 1995  
Comments  This paper has been submitted to Algorithmica (special issue on GIS)  
Report  A topological data structure for hierarchical planar subdivisions (PDF)  Compressed PostScript: A topological data structure for hierarchical planar subdivisions (GZIP) 
CS9552  

Title  Program Understanding: A Constraint Satisfaction Modeling Framework; Understanding as Plan Recognition  
Authors  S. Woods, A. Quilici and Qiang Yang  
Abstract  Different program understanding algorithms often use different representational frameworks and take advantage of numerous heuristic tricks. This situation makes it is difficult to compare these approaches and their performance. This paper addresses this problem by proposing constraint satisfaction as a general framework for describing program understanding algorithms, demonstrating how to tranform a relatively complex existing program understanding algorithm into an instance of a constraint satisfaction problem, and showing how this facilitates better understanding of its performance. Plan recognition is the task of interpreting the actions of agents in the environment, in the context of the knowledge we possess about how action occurs in the world, and why. The recognition task involves constructing a mapping, possibly partial, between an existing repository of plan and domain knowledge and a set of dynamic observations of a subset of the actions taken toward a goal. Program understanding can be viewed as a special case of plan recognition, where the task is to recognize the plans programmers have used in constructing a particular piece of legacy source code. However, program understanding differs from generalized plan recognition in that a complete set of action observations is the basis of goal determination. This paper discusses, in detail, how this difference leads to inadequacies in applying typical plan recognition algorithms to program understanding. Program understanding can instead be viewed as a special case of plan recognition which is particularly amenable to constraint satisfaction techniques. 

Date  November 1995  
Report  Program Understanding: A Constraint Satisfaction Modeling Framework; Understanding as Plan Recognition (PDF)  Compressed PostScript: Program Understanding: A Constraint Satisfaction Modeling Framework; Understanding as Plan Recognition (PS.Z) 
CS9551  

Title  Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques  
Authors  S. Woods and Q. Yang  
Abstract  The process of understanding a source code in a highlevel programming language involves complex computation. Given a piece of legacy code and a library of program plan templates, understanding the code corresponds to building mappings from parts of the source code to particular program plans. These mappings could be used to assist an expert in reverse engineering legacy code, to facilitate software reuse, or to assist in the translation of the source into another programming language. In this paper we present a model of program understanding using constraint satisfaction. Within this model we intelligently compose a partial global picture of the source program code by transforming knowledge about the problem domain and the program itself into sets of constraints. We then systematically study different search algorithms and empirically evaluate their performance. One advantage of the constraint satisfaction model is its generality; many previous attempts in program understanding could now be cast under the same spectrum of heuristics, and thus be readily compared. Another advantage is the improvement in search efficiency using various heuristic techniques in constraint satisfaction.  
Date  November 1995  
Report  Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques (PDF)  Compressed PostScript: Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques (PS.Z) 
CS9550  

Title  Analysis of Hashing Algorithms and a New Mathematical Transform  
Authors  A. Viola  
Abstract  The main contribution of this report is the introduction of a new mathematical tool that we call the Diagonal Poisson Transform, and its application to the analysis of some linear probing hashing schemes. We also present what appears to be the first exact analysis of a linear probing hashing scheme with buckets of size b. First, we present the Diagonal Poisson Transform. We show its main properties and apply it to solve recurrences, find inversse relations and obtain several generalizations of Abel's summation formula. We follow with the analysis of LCFS hashing with linear probing. It is known that the Robin Hood linear probing algorith minimizes the variance of the cost of successful searches for all linear probing algorithms. We prove that the variance of the LCFS scheme is within lower order terms of this optimum. Finally, we present the first exact analysis of linear probing hashing with buckets of size b. From the generating function for the Robin Hood heuristic, we obtain exact expressions for the cost of successful searches when the table is full. Then, with the help of Singularity Analysis, we find the asymptotic expansion of this cost up to O((bm)1), where m is the number of buckets. We also give upper and lower bound when the table is not full. We conclude with a new approach to study certain recurrences that involves truncated exponentials. A new family of numbers that satisfies a recurrence resembling that of the Bernoulli numbers is introduced. These numbers may prove helpful in studying recurrences involving truncated generating functions. 

Date  December 1995  
Report  Analysis of Hashing Algorithms and a New Mathematical Transform (PDF)  Compressed PostScript: Analysis of Hashing Algorithms and a New Mathematical Transform (PS.Z) 
CS9548  

Title  Process Spaces  
Authors  R. Negulescu  
Abstract  This paper introduces process spaces, a unified theory of interacting systems. The main new trait, abstract executions, leads to a simple and general set formalism. For concurrent systems (including digital circuits), process spaces apply to diverse correctness concerns and yield a new classification of liveness and progress faults. The resulting studies of different correctness concerns are decoupled and homogeneous (i.e., they do not interfere with each other and they have the same algebraic structure). Applications to other interacting systems, such as electrical networks and dynamical systems, are also possible. Process spaces have many meaningful properties; here, some results from concurrency theory are generalized and simplified, and some new results are found.  
Date  December 1995  
Report  Process Spaces (PDF)  Compressed PostScript: Process Spaces (PS.Z) 
CS9547  

Title  Surface intersection using affine arithmetic  
Authors  L.H. de Figueiredo  
Abstract  We describe a variant of a domain decomposition method proposed by Gleicher and Kass for intersecting and trimming parametric surfaces. Instead of using interval arithmetic to guide the decomposition, the variant described here uses affine arithmetic, a tool recently proposed for range analysis. Affine arithmetic is similar to standard interval arithmetic, but takes into account correlations between operands and subformulas, generally providing much tighter bounds for the computed quantities. As a consequence, the quadtree domain decompositions are much smaller and the intersection algorithm runs faster. Keywords: surface intersection, trimming surfaces, range analysis, interval analysis, CAGD 

Date  October 1995  
Comments  This paper has been submitted to Graphics Interface `96  
Report  Surface intersection using affine arithmetic (PDF)  Compressed PostScript: Surface intersection using affine arithmetic (GZIP) 
CS9546  

Title  Transformation of Structured Documents  
Authors  E. Kuikka and M. Penttonen  
Abstract  Structure definitions of documents have been used successfully for inputting and formatting in text processing systems. This report considers transformations between different representations of structured documents and studies possiblities to extend the use of structure definitions to document transformations and to discover algorithmic methods for carrying out transformations. Documents are presented as parse trees for contextfree grammars and transformations are made from parse tree to parse tree. First, the report describes differences of manuscript styles demanded by various scientific journals and presents a declarative classification for structure differences between two parse trees. Second, a set of tree transformation methods are described and their suitability for transformations between documents having a structure difference in each defined class is analyzed. For each class several methods may or must be used and only certain kinds of differences can be managed automatically. Finally, instead of designing a system where a method accommodates for all kinds of differences or where different methods are used in various transformations, the report presents a model for a document transformation system that presents a possibility of using various methods according to differences in document representations. The system is divided two modules. In the first one transformations are made automatically and they do not change the hierarchical structure of a document. In the second one transformations are made semiautomatically or nonautomatically and the hierarchical structure changes. Differences between the existing and the required representation of a document are analyzed and methods selected according to the classified differences.  
Date  October 1995  
Comments  The later version of this report has been submitted to Eletronic Publishing journal.  
Report  Transformation of Structured Documents (PDF)  Compressed PostScript: Transformation of Structured Documents (GZIP) 
CS9545  

Title  ScenarioBased Analysis of Software Architecture  
Authors  R.N. Kazman, Gregory Abowd, Len Bass and Paul Clements  
Abstract  Software architecture is one of the most important tools for designing and understanding a system, whether that system is in preliminary design, active deployment, or maintenance. Scenarios are important tools for exercising an architecture in order to gain information about a system's fitness with respect to a set of desired quality attributes. This paper presents a set of experiential case studies illustrating the methodological use of scenarios to gain architecturelevel understanding and predictive insight into large, realworld systems in various domains. A structured method for scenariobased architectural analysis is presented, using scenarios to analyze architectures with respect to achieving quality attributes. Finally, lessons and morals are presented, drawn from the growing body of experience in applying scenariobased architectural analysis techniques.  
Date  October 1995  
Report  ScenarioBased Analysis of Software Architecture (PDF)  Compressed PostScript: ScenarioBased Analysis of Software Architecture (GZIP) 
CS9544  

Title  Depth from Shading as an Attentional Cue in User Surfaces  
Authors  S.L. Loop  
Abstract  When using a computer, we are engaging in a dialogue with the computer. In order to communicate effectively with the computer, we must be aware of the state of the computer. Therefore, we need our attention drawn to particular areas that may indicate the state. When these areas are not found easily, that is these areas are not conspicuous, then we may sacrifice speed and accuracy resulting in potentially disastrous consequences. It has been known for years that colour is very conspicuous: it is easily noticed and attracts attention. For this reason, colour has been used in the interface to group, discriminate and draw attention. Visual texture, normally studied for its segregating and discriminating properties, is also very conspicuous. Another visual attribute that research has shown to be conspicuous is depth conveyed through shape from shading perception: convex and concave objects are easily discriminated. The theedimensional look that shape from shading imparts is becoming more popular in interface design due to its concrete, realistic appeal. However, designers are not making use of the functional benefits, that is the conspicuousness, of depth from shading in the design of the interface. A windowing system is a good example of an interface that needs to present conspicuous information to the user so that the user knows the state of the computer. In this case, so it is known which window is active and can receive input. This thesis empirically supports the idea that depth from shading can be used as a conspicuous attribute in a windowing system to indicate the active window. However, as the depth from shading cue is obscured by othe overlapping windows, the conspicuousness of the cue decreases. Some guidelines for maintaining conspicuity of the depth from shading cue are provided. 

Date  October 1995  
Comments  The experimental results files before processing are in the 'results.*' files. 'results.E1.*' = experiment 1 'results.E2.*' = experiment 2 'results.E3.*' = experiment 3 

Report  E1 (SL), E2 (ED), E2 (FG), E2 (GV), E2 (JB), E2 (JW)  E2 (SL), E2 (SM), E2 (WC), E3 (SL), E3 (WC)  Depth from Shading as an Attentional Cue in User Surfaces (PDF)  Compressed PostScript: Depth from Shading as an Attentional Cue in User Surfaces (PS.Z) 
CS9541  

Title  Searching in Constant Time and Minimum Space  
Authors  A. Brodnik  
Abstract 
This report deals with techniques for minimal space representation of a subset of elements from a bounded universe so that various types of searches can be performed in constant time. In particular, we introduce a data structure to represent a subset of N elements of [0, ..., M1]$ in a number of bits close to the information theoretic minimum and use the structure to answer membership queries in constant time. Next, we describe a representation of an arbitrary subset of points on an M x M grid such that closest neighbour queries (under L_1 and L_oo) can be performed in constant time. This structure requires M^2 + o(M^2) bits. Finally, under a byte overlap model of memory we present an M+o(M) bit, constant time solution to the dynamic onedimensional closest neighbour problem (hence, also unionsplitfind and priority queue problems) on [0, ..., M1]. 

Date  September 1995  
Comments 


Report  Searching in Constant Time and Minimum Space (PDF)  Compressed PostScript: Searching in Constant Time and Minimum Space (PS.Z) 
CS9540  

Title  Programming Support for Blossoming: The Blossom Classes  
Authors  Wayne Liu  
Abstract  A C++ library has been created to facilitate prototyping of curve and surface modeling techniques. The library provides generalpurpose blossoming datatypes to support creation of modeling techniques based on blossoming analysis. The datatypes have efficient operations which are generalizations of important CAGD algorithms, and can be used to implement many algorithms. Most importantly, the library is able to interoperate with usersupplied datatypes or routines to create complex modeling techniques.  
Comments   This technical report is based on author's master's thesis.  The code for the library described in this thesis is available by contacting the author. 

Report  Programming Support for Blossoming: The Blossom Classes (PDF)  Compressed PostScript: Programming Support for Blossoming: The Blossom Classes (PS.Z) 
CS9539  

Title  A Study of Delays and DeSynchronisation in a MultipleView Direct Manipulation Task  
Authors  F. Jaubert  
Abstract  Computer graphics are used in increasingly complex situations, often involving multiple dynamic views. This poses the problem of maintaining proper synchronisation among the various views. The effect of desynchronisation and delays in commandline and singleview graphical environments has been well studied; this thesis aims to do the same with multiple view environments. To that end, an experimental platform is developed, which requires subjects to complete a placement task in a multipleview representation of a threedimensional world. Delays are imposed on the different views, and the effect on the subject's performance (in terms of completion time and number of manipulation operations required) is noted. The results show that delays on the view under manipulation have a definite detrimental effect on all subjects; furthermore, certain subjects are affected by delays on other views as well. To conclude, the experiment reveals that the problem of desynchronisation in a multipleview environment is a complex one, requiring further research; several new experiments are suggested to help answer the questions posed in this study.  
Date  September 1995  
Comments  A Master of Mathematics Thesis  
Report  A Study of Delays and DeSynchronisation in a MultipleView Direct Manipulation Task (PDF)  Compressed PostScript: A Study of Delays and DeSynchronisation in a MultipleView Direct Manipulation Task (PS.Z) 
CS9537  

Title  Editable Software Views  
Authors  Michael Hardy  
Abstract  Understanding software is a very expensive component of software development and maintenance. As a result, tools that assist in the process of software understanding play an important part in reducing software development and maintenance costs. As part of this research, the current literature was examined and it was determined, surprisingly, that very little work had been done in developing tools to assist programmers in understanding source code. Many of the tools presented in the literature suffer from one or more drawbacks that limit their usefulness for a software developer or maintainer. To address some of these limitations, an extensible prototype system that presents extrinsic information about a program in editable source code views was designed and developed. The views are created by embellishing the source code using changes in font family, size, and style, text colour, and text elision. This thesis presents the design and implementation of this system. This research represents a step in the development of tools to assist in software understanding, but it is clear that more effort must be directed towards this area of research.  
Report  Editable Software Views (PDF)  Compressed PostScript: Editable Software Views (PS.Z) 
CS9535  

Title  Improving Depth Perception in 3D Interfaces with Sound  
Authors  S. Mereu  
Abstract  The ability for users to perceive depth in 3D computer interfaces is essential for these applications to be useful. Due to the 2D nature of the display screen, perceiving three dimensions is not always as easy as it is in the real world. Solutions to the lack of depth cues presented are numerous including stereo glasses and head tracking. These solutions, however, are often too expensive for the general user. Sound on the other hand is relatively inexpensive. Experiments have recently been completed in this area and have shown that sound is an effective depth cue. This report discusses the results and makes suggestions on implementing a sound based application.  
Date  August 1995  
Report  Improving Depth Perception in 3D Interfaces with Sound (PDF)  Compressed PostScript: Improving Depth Perception in 3D Interfaces with Sound (PS.Z) 
CS9532  

Title  Relative Liveness: From Intuition to Automated Verification  
Authors  R. Negulescu and J.A. Brzozowski  
Abstract  We point out deficiencies of previous treatments of liveness. We define a new liveness condition in two forms: one based on finite trace theory, and the other on automata. We prove the equivalence of these two definitions. We also introduce a safety condition and provide modular and hierarchical verification theorems for both safety and liveness. Finally, we present a verification algorithm for liveness.  
Date  July 1995  
Comments  An extended summary of this report was presented at the Second Working Conference on Asynchronous Design Methodologies, South Bank University, London, UK, May 1995.  
Report  Relative Liveness: From Intuition to Automated Verification (PDF)  Compressed PostScript: Relative Liveness: From Intuition to Automated Verification (PS.Z) 
CS9531  

Title  Nonlinear Iteration Methods for High Speed Laminar Compressible NavierStokes Equations  
Authors  P.A. Forsyth and H. Jiang  
Abstract  Full Newton nonlinear iteration is compared to use of a defect correction approach (first order Jacobian, second order residual) for solving the steady state compressible flow equations. The Jacobian is constructed numerically, and solved using a PCG type method with block $ILU(k)$ preconditioning. Numerical tests are carried out using the NACA 0012 airfoil, at various free stream Mach numbers and Reynolds numbers. The full Newton approximation is generally more robust and takes less CPU time than the defect correction approach. No particular difficulty was observed in solving the full Newton Jacobian using an $ILU(2)$ ($\simeq 100,000$ unknowns) with CGSTAB acceleration.  
Date  July 1995  
Report  Nonlinear Iteration Methods for High Speed Laminar Compressible NavierStokes Equations (PDF)  Compressed PostScript: Nonlinear Iteration Methods for High Speed Laminar Compressible NavierStokes Equations (GZIP) 
CS9530  

Title  Finding Largest Subtrees and Smallest Supertrees  
Authors  A. Gupta and N. Nishimura  
Abstract  As trees are used in a wide variety of application areas, the comparison of trees arises in many guises. Here we consider two generalizations of classical tree pattern matching, which consists of determining if one tree is isomorphic to a subgraph of another. For the embedding problems of subgraph isomorphism and topological embedding, we present algorithms for determining the largest tree embeddable in two trees T and T' (or a largest subtree) and for constructing the smallest tree in which each of T and T' can be embedded (or a smallest supertree). Both subtrees and supertrees can be used in a variety of different applications. For example, when each of the two trees contains partial information about a data set, such as the evolution of a set of species, the subtree or supertree corresponds to a structuring of the data in a manner consistent with both original trees. The size of a subtree or supertree of two trees can also be used to measure the similarity between two arrangements of data, whether images, documents, or RNA secondary structures. In this paper, we present a general paradigm for sequential and parallel subtree and supertree algorithms for subgraph isomorphism and topological embedding. Our sequential algorithms run in time O(n^{2.5} log n) and our parallel algorithms in time O(log^3 n) on a randomized CREW PRAM using a polynomial number of processors. In addition, we produce better algorithms for these problems when the underlying trees are ordered, that is, when the children of each node have a lefttoright ordering associated with them. In particular, we obtain O(n^2) time sequential algorithms and O(log^3 n) time deterministic parallel algorithms on CREW PRAMs for both embeddings. 

Date  July 1995  
Report  Finding Largest Subtrees and Smallest Supertrees (PDF)  Compressed PostScript: Finding Largest Subtrees and Smallest Supertrees (PS.Z) 
CS9525  

Title  Text/Relational Database Management Systems: Overview and Proposed SQL Extensions  
Authors  G.E. Blake,M.P. Consens, I.J. Davis, P. Kilpelainen, E. Kuikka, P.A. Larson, T. Snider and F.W. Tompa  
Abstract  Combined text and relational database support is increasingly recognized as an emerging need of industry, spanning applications requiring text fields as parts of their data (e.g., for customer sup port) to those augmenting primary text resources by conventional rela tional data (e.g., for publication control). In this paper, we propose extensions to SQL2 that provide flexible and efficient access to struc tured text described by SGML or other encodings. We also propose an architecture to support a text/relational database management system as a federated database environment, where component databases are accessed via ``agents'': SQL agents that translate standard or extended SQL2 queries into vendorspecific dialects, and text agents that pro cess text subqueries on fulltext search engines.  
Date  June 1995  
Comments  Supercedes earlier version published in Proceedings of the ADB'94 Conference.  
Report  Text/Relational Database Management Systems: Overview and Proposed SQL Extensions (PDF)  Compressed PostScript: Text/Relational Database Management Systems: Overview and Proposed SQL Extensions (PS.Z) 
CS9524  

Title  An Analysis of Polynomial Composition Algorithms  
Authors  S. Mann and W. Liu  
Abstract  An analysis is made of the runtime of a previously published algorithm for polynomial composition. Two new, more efficient algorithms are presented. One of these algorithms is optimal, while the other algorithm is numerically more stable than the optimal one. Additionally, as a generalization of polynomial composition, we show how to compose a multiaffine function with a set of polynomials as an extension to an earlier algorithm for composing two polynomial functions. With this extension, we are able to perform degree raising with composition. 

Date  June 1995  
Report  An Analysis of Polynomial Composition Algorithms (PDF)  Compressed PostScript: An Analysis of Polynomial Composition Algorithms (PS.Z) 
CS9522  

Title  Evaluating Tensor Product and Triangular Bezier Surfaces  
Authors  J. Carriere  
Abstract  Many papers describe techniques for evaluating spline curves and surfaces. While each paper provides some theoretical or empirical evidence with which to compare techniques, there exist few global comparisons. Also, papers describing particular algorithms often provide few details, making implementation of the technique presented difficult or impossible. This report attempts to illuminate the performance relationships between, and implementations of, various methods for rendering spline surfaces. Empirical results are given for bicubic tensor product Bezier surfaces, and for cubic and quartic triangular Bezier surfaces.  
Date  May 1995  
Report  Evaluating Tensor Product and Triangular Bezier Surfaces (PDF)  Compressed PostScript: Evaluating Tensor Product and Triangular Bezier Surfaces (PS.Z) 
CS9520  

Title  Walking Streets Faster  
Authors  A. LopezOrtiz and S. Schuierer  
Abstract  A fundamental problem in robotics is to compute a path for a robot from its current location to a given goal. In this paper we consider the problem of a robot equipped with an onboard vision system searching for a goal g in an unknown environment. We assume that the robot is originally located at a point $s$ on the boundary of a street polygon. A street is a simple polygon with two distinguished points s and g, which are located on the polygon boundary and the part of the polygon boundary from s to g is weakly visible to the part from g to s and vice versa. Our aim is to minimise the ratio of the length of the path traveled by the robot to the length of the shortest path from s to g. In analogy to online algorithms this value is called the competitive ratio. We present a series of strategies all of which follow the same general high level strategy. In the first part we present a class of strategies any of which can be shown to have a competitive ratio of Pi + 1. These strategies are robust under small navigational errors and their analysis is very simple. In the second part we present the strategy Continuous Lad which is based on the heuristic optimality criterion of minimising the Local Absolute Detour. We show an upper bound on the competitive ratio of Continuous Lad of ~2.03. Finally, we also present a hybrid strategy consisting of Continuous Lad and the strategy MoveinQuadrant. We show that this combination of strategies achieves a competitive ratio of 1.73. This about halves the gap between the known sqrt(2) lower bound for this problem and the previously best known competitive ratio of ~2.05. 

Date  October 1995  
Report  Walking Streets Faster (PDF)  Compressed PostScript: Walking Streets Faster (PS.Z) 
CS9517  

Title  From Data Representation to Data Model: MetaSemantic Issues in the Evolution of SGML  
Authors  D. Raymond, F.W. Tompa and D. Wood  
Abstract  SGML provides standard representations for documents, but as documents become more fluid, we will need standard semantics for them as well. The ability to manage change is a fundamental capability of any system that supports document semantics. We look at three areas important in change management: equivalence, redundancy, and operators. We show how these areas are implicitly addressed in SGML and SGMLbased standards, and argue that more explicit consideration would be useful both for evaluating current standards, and for developing new systems for document semantics. Keywords:document semantics, document update, document data modelling 

Date  April 1995  
Report  From Data Representation to Data Model: MetaSemantic Issues in the Evolution of SGML (PDF)  Compressed PostScript: From Data Representation to Data Model: MetaSemantic Issues in the Evolution of SGML (PS.Z) 
CS9514  

Title  The Complexity of Subgraph Isomorphism: Duality Results for Graphs of Bounded Pathand TreeWidth  
Authors  A. Gupta and N. Nishimura  
Abstract  We present a clear demarcation between classes of bounded treewidth graphs for which the subgraph isomorphism problem is NPcomplete and those for which it can be solved in polynomial time. In previous work, it has been shown that this problem is solvable in polynomial time if the source graph has either bounded degree or is kconnected, for k the treewidth of the two graphs. As well, it has also been shown that for certain specific connectivity or degree conditions, the problem becomes NPcomplete. Here we give a complete characterization of the complexity of this problem on bounded treewidth graphs for all possible connectivity conditions of the two input graphs. Specifically, we show that when the source graph is not kconnected or has more than k vertices of unbounded degree the problem is NPcomplete, thus answering an open question of Matousek and Thomas. Many of our reductions are restricted to using a subset of graphs of bounded treewidth, namely graphs of bounded pathwidth. As a direct result of our constructions, we also show that when the source and target graphs have connectivity less than k or at least one has k vertices of unbounded degree, the subgraph isomorphism problem for bounded pathwidth graphs is NPcomplete. 

Date  February 1995  
Report  The Complexity of Subgraph Isomorphism: Duality Results for Graphs of Bounded Pathand TreeWidth (PDF)  Compressed PostScript: The Complexity of Subgraph Isomorphism: Duality Results for Graphs of Bounded Pathand TreeWidth (PS.Z) 
CS9512  

Title  A Global Search Architecture  
Authors  F.J. Burkowski, G.V. Cormack, C.L.A. Clarke and R.C. Good  
Abstract  Recent advances in communication and storage technology make available vast quantities of online information. But this information is of limited use unless it can be searched effectively. Huge scale and heterogeneity of data raise a unique combination of architectural issues that must be addressed to support effective search. These issues occasion the use of multiuser distributed search databases with the following capabilities: efficient structured searching of the contents of files having various schema; continuous availability in spite of failures and maintenance; highthroughput incorporation of a continuous stream of updates, especially the arrival new data and removal of obsolete data. We present an architecture that embodies solutions to specific technical problems that arise in the provision of these capabilities.  
Date  March 1995  
Report  A Global Search Architecture (PDF)  Compressed PostScript: A Global Search Architecture (PS.Z) 
CS9510  

Title  A Robust Storage System Architecture  
Authors  R.C. Good, G.V. Cormack, D. Taylor and C.L.A. Clarke  
Abstract  Errorcorrecting codes allow either incorrect data to be corrected or missing data to be rebuilt. They are frequently used with communications channels to recover data lost through line noise and thus provide a `noise free' bit pipe. Data can also be lost through hardware failure; for instance a disk crash. In case of hardware failure, we want a storage system that has the robustness and tunability of errorcorrecting codes in order to provide recovery of the lost data. This is especially so when dealing with systems involving a large number of disks as, when taken as a group, they are more error prone than single disks but are a vary practical way of building large data stores. At present, the most common way to provide data recovery is straight duplication (mirroring) or a code able to detect single failures within a tightly coupled array of disks. A new prototype system has been designed and implemented which uses linear errorcorrecting codes to provide data storage over a loosely coupled distributed storage system. The faulttolerance of this system can be varied by choosing the amount of redundant information stored. 

Date  February 1995  
Report  A Robust Storage System Architecture (PDF)  Compressed PostScript: A Robust Storage System Architecture (PS.Z) 
CS9509  

Title  Interchanging the Order of Grouping and Join  
Authors  W.P. Yan and P.A. Larson  
Abstract  Assume that we have an SQL query containing joins, a GROUPBY and possibly a HAVING predicate. The standard way of evaluating this type of query is to first perform the groupby early, that is to push the groupby operation past one or more joins. This may reduce the query processing cost by reducing the amount of data partocipating in joins. The reverse transformation, ie.e, performing joing before groupby, can also be beneficial because the join may greatly reduce the input to the groupby. We formally define the problem, adhering strictly to the semantics of SQL2, and prove necessary and sufficient conditions for deciding when the transformation is valid. In practice, it may be expensive or even impossible to test whether the conditions are satisfied. Therfore, we also present a more practical algorith that tests a simpler, sufficient condition. This algorithm is fast and detects a large subclass of transformable queries.  
Date  February 1995  
Report  Interchanging the Order of Grouping and Join (PDF)  Compressed PostScript: Interchanging the Order of Grouping and Join (PS.Z) 
CS9508  

Title  A Calculus for Concurrent Update  
Authors  G.V. Cormack  
Abstract  The distributed operation transform (dOPT) is proposed by Ellis and Gibbs (SIGMOD Record 18:2, 1989) as a lockfree algorithm to ensure the consistency of concurrently updatable distributed objects. dOPT is shown by counterexample to be incorrect. A corrected algorithm is given for a restricted environment based on pointtopoint communication. There appears to be no simple correction to dOPT for a general environment based on broadcast communication.  
Date  January 1995  
Report  A Calculus for Concurrent Update (PDF)  Compressed PostScript: A Calculus for Concurrent Update (PS.Z) 
CS9507  

Title  On the use of Regular Expressions for Searching Text  
Authors  C.L.A. Clarke and G.V. Cormack  
Abstract  The use of regular expressions to search text is well known and understood as a useful technique. It is then surprising that the standard techniques and tools prove to be of limited use for searching text formatted with SGML or other similar markup languages. Experience with structured text search has caused us to carefully reexamine the current practice. The generally accepted rule of "leftmost longest match" is an unfortunate choice and is at the root of the difficulties. We instead propose a rule which is semantically cleaner and is incidentally more simple and efficient to implement. This rule is generally applicable to any text search application.  
Date  February 1995  
Report  On the use of Regular Expressions for Searching Text (PDF)  Compressed PostScript: On the use of Regular Expressions for Searching Text (PS.Z) 
CS9506  

Title  A Calculus for Concurrent Update  
Authors  G.V. Cormack  
Abstract  This paper introduces a calculus for concurrent update (CCU) that is used to specify distributed objects. The calculus permits updates to be effected immediately at each site  no central server, locking, token passing, rollback, or other form of serialization is enforced. Notice of each update at each site is transmitted to every other site, where a corresponding update is effected. Unless special provisions are taken, network transmission delay may cause corresponding updates to be effected at different sites in different orders, potentially rendering them meaningless or inconsistent. CCU avoids this eventuality: transformations are applied to corresponding updates as necessary to preserve overall meaning and consistency. CCU derives from the Distributed Operational Transform (dOPT) algorithm proposed by Ellis and Gibbs (ACM SIGMOD Record 18:2, 1989) as a concurrency control mechanism for groupware systems. dOPT introduces the notion of consistencypreserving transformations, and embeds exactly the lightweight CBCAST algorithm published later by Birman, Schiper and Stephenson (ACM TOCS 9:3, 1991). However, Ellis and Gibbs present no method for reasoning about either the overall consistency or meaningfulness of the transforms as applied by dOPT. Indeed, dOPT is incorrect, as demonstrated by a counterexample in which it fails to maintain consistency. 

Date  January 1995  
Report  A Calculus for Concurrent Update (PDF)  Compressed PostScript: A Calculus for Concurrent Update (PS.Z) 
CS9501  

Title  The Grail Papers: Version 2.3  
Authors  D. Raymond and D. Wood  
Abstract  Grail is a package for computing with finitestate machines and regular expressions, written in C++. Grail supports input and output of textual descriptions of automata and regular expres sions, conversions between machines and regular expressions, and other operations. Grail can be used as a set of shellcallable processes, a library of functions, or as individual C++ classes. Version 2.3 of Grail supports parameterizable machines and expressions. This collection of papers includes a description of the the his tory and design of Grail, a user's guide, a programmer's guide. 

Date  January 1995  
Report 
Compressed PostScript: 