CS9646  

Title  Colour and Reflectance in Image Synthesis  
Authors  T. Pflaum  
Abstract  In recent years substantial research has been done on physically based image synthesis, which includes the algorithms used to create synthetic images using models and algorithms based on the underlying physics of light. The work presented in this thesis focuses on two particular aspects of image synthesis that have not gained much attention in the past: how to represent colour and how to describe the reflection of light by surfaces. A simulation system is presented that takes a model of the micro structure of a surface and creates a representation of the bidirectional reflectance function (BRDF) of a surface having that micro structure. In addition, a technique is presented that creates a colour space, used for rendering, that is adapted to the surface colours actually appearing in the scene. 

Date  December 1996  
Report  Colour and Reflectance in Image Synthesis (PDF)  Compressed PostScript: Colour and Reflectance in Image Synthesis (PS.Z) 
CS9645  

Title  A Simple, General and Efficient Implementation of Geometric Operators and Predicates  
Authors  E. Chan and J.N.H. Ng  
Abstract  Shape and location of objects in a spatial database are commonly represented by geometric data such as points, lines and regions. Numerous geometric operators and predicates have been proposed for spatial database systems. Existing work on their implementation concentrate on individual operators and predicates. This approach makes the realization of geometric operators and predicates in a spatial database system difficult since they are diverse and their implementation in general are complex. In this paper, we present a simple planesweep algorithm that can be easily modified to realizeefficiently a set of frequently used lineregion and regionregion geometric operators and predicates. The design of this unified algorithm is based on the observation that the covering of elementary regions along the sweep line are updated locally and the implementation of these operators and predicates differ only with the output actions at an intersection point. Any geometric operator or predicate, the output of which can be determined by examing incident edges and covering information at intersection pints, can be implemented easily with the algorithm. To demonstrate its generality, extendibility, simplicity and efficiency, we concentrate on several popular geometric operators and predicates. All these operators and predicates can be realized in O((N+1) logN) time in the worst case, where N is the number of edges in the operands and I is the number of intersection pairs. The proposed algorithms is fully implemented in C++ and is tested on a Sun workstation. Although the paper focuses on operators and predicates involving at most two regions, this algorithm can be generalized nicely to r regions, where r>2. We describe what changes are needed to make to the basic algorithm to accommodate this generalization.  
Date  November 1996  
Report  A Simple, General and Efficient Implementation of Geometric Operators and Predicates (PS) 
CS9644  

Title  Querying and Visualization of Geometric Data  
Authors  E. Chan and J.M.T. Wong  
Abstract  This paper describes the retrieval, browsing and visualization of data for a spatial database system developed at the University of Waterloo. The prototype, called QL/G, suppports geometric data types like general regions, lines and points as builtin data types. A Graphical User Inter face (GUI), written in X/Motif and a persistent version of C++, is provided for users as an effective tool for querying and visualizing data retrieved. The interface is simple, userfriendly and flexible, and provides the necessary functionality identified in existing literature for geographic applications.  
Date  November 1996  
Report  Querying and Visualization of Geometric Data (PS) 
CS9643  

Title  The GUI For A Spatial Database Management System  
Authors  E. Chan, J.M.T. Wong, P.Y. Abbott and S. Tan  
Abstract  This paper documents the functionality provided by a spatial database management system (SDBMS) developed at the University of Waterloo. The prototype,called QL/G, supports data types. The functionality is described through the Graphical User Interface (GUI) provided by the system. The user interface component is an especially important part of a SDBMS. In particular, a SDBMS should provide a convenient frontend for definition, entry, visualization and manipulation of spatial data. The system should also address the complex issue of spatial processing and analysis. The GUI of QL/G is designed with the above objective in mind. The interface is simple, userfriendly and flexible, and yet provides the user with the necessary functionality identified in existing literature for geographic applications.  
Date  November 1996  
Report  The GUI For A Spatial Database Management System (PS) 
CS9642  

Title  Symbolic Computation Group Annual Report 1996  
Authors  Symbolic Computation Group  
Abstract  The Symbolic Computation Group has as its primary goal the research and development of algorithms for computer algebra, including both symbolic computation and hybrid symbolicnumeric computation. The algorithms developed are incorporated into the Maple computer algebra system. Particular areas of research and development which have been targeted during the past year include symbolic integration, computing solutions of ordinary and partial differential equations (both symbolically and numerically), extendedprecision numerical evaluation of special functions, facilities for handling piecewise functions, pattern matching, matrix computations, and tensor computations. 

Date  November 1996  
Report  Symbolic Computation Group Annual Report 1996 (PDF)  Compressed PostScript: Symbolic Computation Group Annual Report 1996 (PS.Z) 
CS9640  

Title  Grammars++ for Modelling Information in Text  
Authors  A. Salminen and F.Wm. Tompa  
Abstract  Grammars provide a convenient means to describe the set of valid strings in a language, and thus they seem natural for describing the set of valid instances in a text database. It is wellknown that a given language can be described by many grammars, and similarly text database designers have a choice of grammar for specifying valid documents. This flexibility can be exploited to provide information modelling capability by designing productions in the grammar to represent entities and relationships of interest to the database applications. Additional constraints can be specified by attaching predicates to selected nonterminals in the grammar. In this paper, we formalize and illustrate the use of extended grammars for text databases. When used for database definition, grammars can provide the functionality that users have come to expect of database schemas. Extended grammars can also be used to specify database manipulation, including query, update, view definition, and index specification. 

Date  November 1996  
Report  Grammars++ for Modelling Information in Text (PDF)  Compressed PostScript: Grammars++ for Modelling Information in Text (PS.Z) 
CS9639  

Title  The Management of Data, Events, and Information Presentation for Network Management  
Authors  M. Hasan  
Abstract  The purpose of a network management (NM) system is to monitor and control a network. Monitoring and control functions entail deal ing with large volumes of data, events, and the presentation of relevant information on a management station. The management of data, events, and information presentation pose a major research and development challenge. In this thesis we focus on data and events management and information presentation issues of an NM system. Existing NM systems either use traditional da tabase systems which are not well suited for a NM system or they lack intelligent event and information presentation management frameworks. None of the systems provide a unified framework for managing data, events and information presentation tasks on an NM station. We believe that the complexities of network management posed by the issues mentioned above can be reduced substantially by ex ploiting, enhancing and combining the features of new generation database systems, such as, active temporal and database visu alization systems. An active database system where active behaviors are specified as EventConditionAction (ECA) rules is a suitable framework for NM data and events management. The Hy+ database visualization system with its sophisticated abstrac tion and visualization capabilities is wellsuited to meet the requirements of NM information presentation. By viewing the network as a conceptual global database, the network management functions can be specified as declarative database manipulation operations and EventConditionAction (ECA) rules. But the facilities provided by existing active database systems are not enough for an NM system. For example, NM events manage ment requires sophisticated systems for event correlation based on domain knowledge on the events and other relationships, such as, structural and temporal relationships between events. A number of existing active temporal database systems provide sup port for a composite event specification language (CESL) (used in the E part of an ECA rule) that allows one to relate events in the temporal dimension. But these languages lack features that otherwise are required by certain applications. In this thesis we propose a CESL, called CEDAR that extends the powers of existing languages. CEDAR allows a user to specify various event management functionalities in the NM domain, which otherwise is difficult or impossible to specify in existing languages. An implementation model of the language operators using Colored Petri Nets is also proposed. We also propose a model of a network management database system that incor porates CEDAR with an active database system, and various other features required by NM functionalities, such as, event defini tion, sampling or polling, etc. The resulting system is in tegrated with the Hy+ database visualization system. The deductive capability provided by the Hy+ system further enhances the power of data and events management, and information presen tation capabilities. 

Report  Table of Contents (PDF)  The Management of Data, Events, and Information Presentation for Network Management (PDF)  Compressed PostScript: The Management of Data, Events, and Information Presentation for Network Management (PS.Z) 
CS9638  

Title  Distributed Scientific Data Processing Using the DBC  
Authors  J. Duff, K. Salem and M. Livny  
Abstract  The Distributed Batch Controller (DBC) supports scientific batch data processing. The DBC distributes batch jobs to one or more pools of workstations and monitors and controls their execution. The pools themselves may be geographically distributed, and need not be dedicated to processing batch jobs. We describe the use of the DBC in a large scientific data processing application, namely the generation of atmospheric temperature and humidity profiles from satellite data. This application shows that the DBC can be an effective platform for distributed batch processing. It also highlights several design and implementation issues that arise in distributed data processing systems.  
Date  November 1996  
Report  Distributed Scientific Data Processing Using the DBC (PDF)  Compressed PostScript: Distributed Scientific Data Processing Using the DBC (PS.Z) 
CS9636  

Title  Application of a Stochastic Grammatical Inference Method to Text Structure  
Authors  M. YoungLai  
Abstract  For a document collection where structural elements are identified with markup, it is sometimes necessary to retrospectively construct a grammar that constrains element nesting and ordering. An approach to this problem is described based on a grammatical inference method that generates stochastic finite automata. Improvements are made to the algorithm based on experiments with data from the Oxford English Dictionary. The problems of understanding results and interactively adjusting the algorithm's parameters are also considered.  
Date  October 1996  
Comments  This technical report is a reprint of my Master's thesis.  
Report  Application of a Stochastic Grammatical Inference Method to Text Structure (PDF)  Compressed PostScript: Application of a Stochastic Grammatical Inference Method to Text Structure (GZIP) 
CS9635  

Title  Designing Subdivision Surfaces through Control Mesh Refinement  
Authors  H. Sheikh  
Abstract  I present a technique for designing subdivision surfaces through the repeated process of refining the control mesh of the surface. The refinement is performed using the surfaces subdivision algorithm. An abstract structure for subdivision surfaces is developed that involves the control mesh and the subdivision algorithm. This structure is used to build a generic editor that assists in the design of surfaces represented by classes of control meshes and subdivision algorithms. The theory of subdivision surfaces, in particular, tensor product cardinal splines and box splines is described in detail. From the theory, subdivision algorithms for these surfaces are constructed and then used to create Refiners. The concept of trimming these surfaces is also introduced to aid in rendering of the surface. Several C++ spline classes used in the implementation are described. The subdivision surface editor uses these classes and Open Inventor to provide a prototype 3D surface design, manipulation and editing environment. 

Date  September 1996  
Comments  My thesis supervisor was Richard Bartelswho is probably the best person to get in touch with regarding current progress with the thesis.  
Report  Designing Subdivision Surfaces through Control Mesh Refinement (PDF)  Compressed PostScript: Designing Subdivision Surfaces through Control Mesh Refinement (PS.Z) 
CS9634  

Title  Using Inverted Lists to Match Structured Text  
Authors  S. Li  
Abstract  Inverted files have long been used as an effective way to implement secondary key retrieval in traditional database systems. For information retrieval systems, postings lists use a similar inverted file structure to accommodate the special characteristics of text data. This thesis explores extensions to these ideas for structured text databases, especially concerning direct containment of structures. Two kinds of data structures are presented, and for each structure, six basic operations are described and analyzed. Two complex forms of query expressions concerning hierarchical and lateral relationships between text structures are also examined. Examples are presented to demonstrate the effect on performance of each data structure. 

Date  September 1996  
Comments  This report is a reprint of a thesis that embodies the results of research done in partial fulfillment of the requirements for the degree of Master of Mathematics in Computer Science at the University of Waterloo.  
Report  Using Inverted Lists to Match Structured Text (PDF)  Compressed PostScript: Using Inverted Lists to Match Structured Text (PS.Z) 
CS9633  

Title  A Method of Program understanding Using Constraint Satisfaction for Software ReverseEngineering  
Authors  S. Woods  
Abstract  The process of understanding a source code in a highlevel programming language is a complex cognitive task. The provision of helpful decision aid subsystems would be of great benefit to software maintainers. Given a library of program plan templates, generating a partial understanding of a piece of software source code can be shown to correspond to the construction of mappings between segments of the source code and particular program plans represented in a library of domain source programs (plans). These mappings can be used as part of the larger task of reverse engineering source code, to facilitate many software engineering tasks such as software reuse, and for program maintenance. We present a novel model of program understanding using constraint satisfaction. The model composes a partial global picture of source program code by transforming knowledge about the problem domain and the program structure into constraints. These constraints facilitate the efficient construction of mappings between code and library knowledge. Under this representational framework, earlier heuristic approaches to program understanding may be unified, contrasted, and compared. We describe an empirical study which demonstrates the feasibility of our model in the program understanding subtask of partial local explanation. In addition, we incorporate this local model into the larger task of combining these local explanations into a coherent global picture of the code. While many heuristic global models are possible, we describe an encompassing structure and demonstrate, through a careful depiction of the algorithm and several domain examples, how constraint satisfaction offers a rich paradigm for the larger task of reverse engineering source code, to exploiting both library and program structural constraint information. One primary advantage of the constraint satisfaction paradigm (CSP) is its generality; many previous program understanding efforts can be more easily compared. Another advantage is the improvement in search efficiency using various heuristic techniques in CSP. 

Date  September 1996  
Report  A Method of Program understanding Using Constraint Satisfaction for Software ReverseEngineering (PDF)  Compressed PostScript: A Method of Program understanding Using Constraint Satisfaction for Software ReverseEngineering (PS.Z) 
CS9632  

Title  World Space User Interface for Surface Pasting  
Authors  L.K.Y. Chan  
Abstract  Surface pasting is a composition method that applies Bspline surfaces, called features, to any number of other Bspline surfaces, called base surfaces, in order to add details on the base surfaces. The locations as well as the size of the features are determined by transformations of feature domains. By modifying the domain layout of pasted surfaces, we can manipulate the appearances of features interactively in a Domain Space User Interface. However, this domain user interface is inadequate because the user cannot interact with the threedimensional model directly. In this thesis, I propose a World Space User Interface that attempts to map threedimensional user actions to twodimensional domain operations and aims at providing a more intuitive and efficient modelling interface for surface pasting.  
Date  September 1996  
Report  World Space User Interface for Surface Pasting (PDF)  Compressed PostScript: World Space User Interface for Surface Pasting (PS.Z) 
CS9631  

Title  Query Based Stemming  
Authors  E. Tudhope  
Abstract  In information retrieval the relevancy of a document to a particular query is based on a comparison of the terms appearing in the query with the terms appearing in the document. Morphological variants of words (i.e. locate, locates, located, locating) often carry the same or similar meaning. Such terms should be considered equivalent for information retrieval purposes. Stemming is a simple application of natural language processing that is commonly applied at index time to reduce morphological variants to a common root form. This report first examines several approaches to stemming. Some of the problems associated with the use of stemming as a query expansion technique are then discussed. The construction of equivalence classes of words for stemming at query time is presented as a possible alternative method to address some of these problems.  
Date  September 1996  
Report  Appendix  Query Based Stemming (PDF)  Compressed PostScript: Query Based Stemming (PS.Z) 
CS9630  

Title  Finding the Loneliest Point  
Authors  K.Y.Yeung  
Abstract  We study the following problem which finds application in solving equations. Given a Euclidean domain, there are two operations, INSERT and ISOLATE. INSERT adds points to the domain. ISOLATE returns a point in the domain which is satisfactorily far from the points already inserted in the domain. The objective is to perform INSERT and ISOLATE in constant amortized time per operation, linear space and a constant worst case ratio. Worst case ratio measures how far the answer from ISOLATE differs from the best possible answer. We concentrate on the case with a two dimensional domain. The basic approach is to divide the domain into geometric shapes and build a hierarchy of that shape. We have studied the three regular polygons that tile a given two dimensional domain: squares, hexagons and triangles. It turns out that the worst case ratio is smaller when the domain is divided into hexagons than when the domain is divided into squares, the worst case ratio for squares is in turn smaller than that of the triangles. We have also explored other techniques to improve the worst case ratio while keeping constant amortized running time per operation and linear space. We have explored overlapping, embedding (or diamonds), and multiple grids. The worst case ratio can be improved further when these techniques are combined. We have also shown that the square technique can be extended to cubes in a three dimensional domain. 

Date  August 1996  
Report  Finding the Loneliest Point (PDF)  Compressed PostScript: Finding the Loneliest Point (PS.Z) 
CS9629  

Title  Algorithms from Blossoms  
Authors  S. Mann  
Abstract  Blossoming is a theoretical technique that been used to develop new CAGD theory. However, once we have developed this theory, we need to devise algorithms to implement it. In this paper, I will discuss converting blossoming equations into code, noting techniques that can be used to develop efficient algorithms. These techniques are illustrated by considering the operations of basis conversion and polynomial composition.  
Date  October 1996  
Report  Algorithms from Blossoms (PDF)  Compressed PostScript: Algorithms from Blossoms (PS.Z) 
CS9628  

Title  Robust Numberical Methods for PDE Models of Asian Options  
Authors  R. Zvan, P.A. Forsyth and K. Vetzal  
Abstract  We explore the pricing of Asian options by numerically solving the associated partial differential equations. We demonstrate that numerical PDE techniques commonly used in finance for standard options are inaccurate in the case of Asian options and illustrate modifications which alleviate this problem. In particular, the usual methods generally produce solutions containing spurious oscillations. We adapt flux limiting techniques originally developed in the field of computational fluid dynamics in order to rapidly obtain accurate solutions. We show that flux limiting methods are total variation diminishing (and hence fre eof spurious oscillations) for nonconservative PDEs such as those typically encountered in finance, for fully explicit, and fully and partically implicit schemes. We also modify the van Leer flux limiter so tht the secondorder variation diminishing property is preserved for nonuniform grid spacing.  
Date  September 1996  
Report  Robust Numberical Methods for PDE Models of Asian Options (PDF)  Compressed PostScript: Robust Numberical Methods for PDE Models of Asian Options (PS.Z) 
CS9627  

Title  Aposteriori Error Estimation for CFD  
Authors  B. van Straalen  
Abstract  A technique for numerically estimating the discretization error in upwind based finite volume fluid flow simulation was developed. The technique is based on residual estimation, followed by solving the global error equation over the computational domain. One and two dimensional analysis of the error estimation process was performed for a simple homogeneous advectiondiffusion equation. The technique was then extended to encompass the laminar NavierStokes equations. The effectiveness of the technique was investigated for flow over a two dimensional backwardfacing step. The results show promise for future implementations of effective and practical error estimation.  
Date  July 1996  
Report  Aposteriori Error Estimation for CFD (PDF)  Compressed PostScript: Aposteriori Error Estimation for CFD (PS.Z) 
CS9625  

Title  On Line Target Searching in Bounded and Unbounded Domains  
Authors  A. LopezOrtiz  
Abstract  In this work we study the problem of a robot searching for a target on bounded and unbounded domains, specifically in one and two dimensions. We present some relevant results in the field, and within this framework, the contributions of this work. We show that onesided searches on the real line have an average competitive ratio of 9 and we apply this result for the case of known destination searches on Gstreet polygons. For this class of polygons we also show that the best known upper bound of sqrt(82) is indeed optimal for the case of unknown destination searches. For orthogonal street polygons we prove that knowing the location of the destination does not reduce the competitive ratio. We present the first robust algorithm for searches inside street polygons under navigational errors, as well as for other important classes of impaired robots such as robots lacking triangulation and depth measurement mechanisms. In particular, we propose a \pi+1competitive strategy which is robust under navigational error, and equally efficient for oblivious robots. We also present an 1.92competitive strategy which does not require depth perception from the robot. We also give the bestknown strategy for searching inside street polygons, at a competitive ratio of 1.76. This significantly improves over the best previously known ratio of 2.8. We give the first nontrivial lower bound for searching and walking into the kernel of a polygon. We provide upper and lower bounds for searching for a target inside street polygons. These results are the first constant competitive ratio strategies inside a class of polygons which is independent of the location of the start and target points. We also prove negative results regarding the optimality of several wellknown family of strategies for searching inside simple polygons. In particular we show that Kleinberg's strategy is 2.6competitive, and that continuous bisector, which is in many respects a good strategy, is at least 1.68competitive. Lastly we show that any strategy which does not respond to the absence of new extreme points has a competitive ratio strictly larger than sqrt(2). 

Date  July 1996  
Report  On Line Target Searching in Bounded and Unbounded Domains (PDF)  Compressed PostScript: On Line Target Searching in Bounded and Unbounded Domains (PS.Z) 
CS9624  

Title  DoubleBlind Scores of an ObjectOriented Modeling Survey  
Authors  R.S.C. Yiu  
Date  June 1996  
Report  DoubleBlind Scores of an ObjectOriented Modeling Survey (PDF)  Compressed PostScript: DoubleBlind Scores of an ObjectOriented Modeling Survey (GZIP) 
CS9623  

Title  Optimal adaptive polygonal approximation of parametric surfaces  
Authors  L. Velho and L.H. de Figueiredo  
Date  July 1996  
Report  Only available in printed format 
CS9622  

Title  SplineBased Tools for Conventional and Reflective Image Reproduction  
Authors  I.E. Bell  
Date  May 1996  
Report  Only available in printed format 
CS9621  

Title  Length of Finite Pierce Series: Theoretical Analysis and Numerical Computations  
Authors  V. Keselj  
Abstract 
Any real number x from the interval (0,1] can be represented as a unique Pierce series 1 1 1    +   ... q1 q1*q2 q1*q2*q3 where {q1, q2, q3, ...} is an increasing sequence of positive integers. The series is finite if and only if the number x is rational. This paper discusses the length of the series and the final results are a new upper bound (Theorem 2) and a new lower bound (Theorem 3) on the length. The numerical computations concerning the length are done by computer and the algorithms used and results are presented. The numerical results are an extension to the tables previously published. 

Date  September 1996  
Report  Length of Finite Pierce Series: Theoretical Analysis and Numerical Computations (PDF)  Compressed PostScript: Length of Finite Pierce Series: Theoretical Analysis and Numerical Computations (PS.Z) 
CS9620  

Title  The Empirical Derivation of a Design Space and Design Rules for Software Architecture  
Authors  K. Reddy  
Abstract  The empirical derivation of a design space and design rules for software architecture is presented. The research presented in this paper represents and effort to begin capturing what is known by experienced designers about designing for nonfunctional qualities, such as performance, portability, reusability etc., in a rigorous, statistically validated fashion. The design space and design rules are codified by synthesizing information collected by the administration of a survey to experienced designers of large scale systems. They capture the relationships between six unit operations which are structure transforming mechanisms ubiquitous in software design, and eleven nonfunctional qualities. Their use enables design for nonfunctional qualities to occur at an earlier development stage than current practice. The creation, administration and analysis of the survey is presented along with the resultant design space and design rules.  
Date  May 1996  
Report  Only available in printed format 
CS9618  

Title  Data Transfer Using Controlled Compression  
Authors  A.Y.D. Cheung  
Abstract  In a scenario in which a large amount of data is to be transferred from one site to another, it is desirable to optimize the throughput of data transfer. There are two transmission options. One option is to compress the data before the transfer, and to decompress them at the receiving site. The other option is to send the data without doing any compression. Ideally, we would like to choose the option that accomplishes the transfer as quickly as possible. This choice is complicated by many factors such as the load of the machines, and the degree of traffic congestion of the network. These factors affect the transmission rate differently depending on whether or not we use compression. This thesis proposes and evaluates two algorithms for automatically determining whether compression should be used. One algorithm is based on sampling past performance with and without compression. The other directly exploits feedback from the network. These algorithms have been implemented and evaluated under different conditions. The evaluation shows that both algorithms can pick the correct mode of data transfer to use in different environments. The algorithm based on network feedback is more complicated and requires tuning to perform well.  
Date  April 1996  
Report  Data Transfer Using Controlled Compression (PDF)  Compressed PostScript: Data Transfer Using Controlled Compression (PS.Z) 
CS9617  

Title  The DBC: Processing Scientific Data Over the Internet  
Authors  C. Chen, K. Salem and M. Livny  
Abstract  We present the Distributed Batch Controller (DBC), a system built to support batch processing of large scientific datasets. The DBC implements a federation of autonomous workstation pools, which may be widelydistributed. Individual batch jobs are executed using idle workstations in these pools. Input data are staged to the pool before processing begins. We describe the architecture and implementation of the DBC, and present the results of experiments in which it is used to perform image compression.  
Date  March 1996  
Report  The DBC: Processing Scientific Data Over the Internet (PDF)  Compressed PostScript: The DBC: Processing Scientific Data Over the Internet (PS.Z) 
CS9615  

Title  Overview of GSM: The Global System for Mobile Communications  
Authors  J. Scourias  
Date  March 1996  
Report  Overview of GSM: The Global System for Mobile Communications (PDF)  Compressed PostScript: Overview of GSM: The Global System for Mobile Communications (PS.Z) 
CS9614  

Title  A Normal Form for Function Rings of Piecewise Functions  
Authors  M.von Mohrenschildt  
Abstract  Computer algebra systems often have to deal with piecewise defined functions, for example, the absolute value function. We present a new approach to this kind of problem. This paper provides a normal form for function rings containing piecewise functions. We give a compiled rule system to compute the normal form of a function. With a normal form, we can decide equality in our function ring. In this ring, we can define supremum and infimum of two functions. In fact we show that the function ring is a compiled lattice. We present a method to solve equalities and inequalities in this function ring.  
Date  March 1996  
Comments  This paper has been submitted to ISSAC'96.  
Report  A Normal Form for Function Rings of Piecewise Functions (PDF)  Compressed PostScript: A Normal Form for Function Rings of Piecewise Functions (PS.Z) 
CS9613  

Title  Some improvements of a lemma of Rosenfeld  
Authors  F. Boulier  
Abstract  We give two improvements of a lemma of Rosenfeld which permit us to optimize some algorithms in differential algebra: we prove the lemma with stronger hypotheses and we demonstrate an analogue of Buchberger's second criterion, which avoids non necessary reductions for detecting coherent sets of differential polynomials. We try also to clarify the relations between the theorems in differential algebra and some more widely known results in the Groebner bases theory. Keywords: Differential algebra. Rewrite systems. Polynomial differential equations. Rosenfeld's lemma. 

Date  April 1996  
Comments  Submitted to IMACS'96  
Report  Some improvements of a lemma of Rosenfeld (PDF) 
CS9612  

Title  A Multicollaborative PushCaching HTTP Protocol for the WWW  
Authors  Alex LopezOrtiz  
Abstract  We propose a caching protocol designed to automatically mirror heavily accessed WWW pages in a distributed and temporal fashion. The proposed caching mechanism differs from proxy type mechanisms in that it caches according to load pattern at the server side, instead of access patterns at the clientside LAN, in a Demandbased Document Dissemination (DDD) system fashion. This type of server initiated caching scheme has been termed pushcaching. As well, the proposed caching scheme incorporates topological caching functions. The proposed protocol is orthogonal to other extensions to the HTTP protocol and other caching schemes already in use.  
Date  October 1996  
Report  A Multicollaborative PushCaching HTTP Protocol for the WWW (PDF)  Compressed PostScript: A Multicollaborative PushCaching HTTP Protocol for the WWW (PS.Z) 
CS9609  

Title  Tabular Abstraction, Editing and Formatting  
Authors  X. Yang  
Abstract  This dissertation investigates the composition of highquality tables with the use of electronic tools. A generic model is designed to support the different stages of tabular composition, including the editing of logical structure, the specification of layout structure, and the formatting of concrete tables. The model separates table's logical structure from its layout structure, which consists of tabular topology and typographic style. The notion of an abstract table, which describes the logical relationships among tabular items, is formally defined and a set of logical operations is proposed to manipulate tables based on these logical relationships. An abstract table can be visualized through a layout structure specified by a set of topological rules, which determine the relative placement of t abular items in two dimensions, and a set of style rules, which determine the final appearance of different items. The absolute placement of a concrete table can be automatically generated by applying a layout specification to an abstract table. An NPcomplete problem arises in the formatting process that uses automatic line breaking and determines the physical dimension of a table to satisfy userspecified size constraints. An algorithm has been designed to solve the formatting problem in polynomial time for typical tables. Based on the tabular model, a prototype tabular composition system has been implemented in a UNIX, X Windows environment. This prototype provides an interactive interface to edit the logical structure, the topology and the styles of tables. It allows us to manipulate tables based on the logical relationships of tabular items, regardless of where the items are placed in the layout structure, and is capable of presenting a table in different topologies and styles so that we can select a highquality layout structure.  
Date  January 1996  
Report  Tabular Abstraction, Editing and Formatting (PDF)  Compressed PostScript: Tabular Abstraction, Editing and Formatting (PS.Z) 
CS9607  

Title  The Use of a Combined Text/Relational Database System to Support Document Management  
Authors  K.Y. Ng  
Abstract 
In this thesis, we study the problem of representing and manipulating a document to facilitate browsing, editing, string/content searches and document assembly.


Date  January 1996  
Report  The Use of a Combined Text/Relational Database System to Support Document Management (PDF)  Compressed PostScript: The Use of a Combined Text/Relational Database System to Support Document Management (PS.Z) 
CS9604  

Title  Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices  
Authors  A. Storjohann and G. Labahn  
Abstract  This paper presents a new algorithm for computing the Hermite normal form H of an n x m rank m integral matrix A together with a unimodular premultiplier matrix U such that UA=H . Our algorithm requires O~(m^(\theta1) n M(m log A)) bit operations to produce both H and a candidate for U . Here, A =\max_{ij} A_{ij} , M(t) bit operations are sufficient to multiply two tbit integers, and \theta is the exponent for matrix multiplication over rings: two m x m matrices over a ring R can be multiplied in O(m^\theta) ring operations from R . The previously fastest algorithm of Hafner & McCurley requires O~(m^2 n M(m log A)) bit operations to produce H , but does not produce a candidate for U . Previous methods require on the order of O~(n^3 M(m log A)) bit operations to produce a candidate for U  our algorithm improves on this significantly in both a theoretical and practical sense.  
Date  January 1996  
Comments  This paper has been submitted to ISSAC'96.  
Report  Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices (PDF)  Compressed PostScript: Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices (PS.Z) 
CS9603  

Title  Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices  
Authors  A. Storjohann  
Abstract  We present new algorithms for computing Smith normal forms of matrices over the integers and over the integers modulo N . For the case of matrices over Z/(N) , we present an algorithm that computes the Smith form S of an n x m matrix A over Z/(N) in only O(n^\theta m) operations from Z/(N) . Here, \theta is the exponent for matrix multiplication over rings: two n x n matrices over a ring R can be multiplied in O(n^\theta) operations from R . We apply our algorithm for matrices over Z/(N) to get an algorithm for computing the Smith form S of an n x m matrix A over Z in O~(n^(\theta1) m M(n log A)) bit operations (where A = max A_{i,j} and M(t) bounds the cost of multiplying two tbit integers). These complexity results improve significantly on the complexity of previously best known Smith form algorithms (both deterministic and probabilistic) which guarantee correctness.  
Date  January 1996  
Comments  This paper has been submitted to ISSAC'96.  
Report  Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices (PDF)  Compressed PostScript: Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices (PS.Z) 