1996 technical reports

CS-96-46
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)

CS-96-45
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 plane-sweep algorithm that can be easily modified to realizeefficiently a set of frequently used line-region and region-region 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)

CS-96-44
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 built-in 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, user-friendly 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)

CS-96-43
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 front-end 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, user-friendly 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)

CS-96-42
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 symbolic-numeric 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), extended-precision 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)

CS-96-40
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 well-known 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 non-terminals 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)

CS-96-39
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 Event-Condition-Action (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 well-suited 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 Event-Condition-Action (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)

CS-96-38
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)

CS-96-36
Title	Application of a Stochastic Grammatical Inference Method to Text Structure
Authors	M. Young-Lai
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)

CS-96-35
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)

CS-96-34
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)

CS-96-33
Title	A Method of Program understanding Using Constraint Satisfaction for Software Reverse-Engineering
Authors	S. Woods
Abstract	The process of understanding a source code in a high-level 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 Reverse-Engineering (PDF)			Compressed PostScript: A Method of Program understanding Using Constraint Satisfaction for Software Reverse-Engineering (PS.Z)

CS-96-32
Title	World Space User Interface for Surface Pasting
Authors	L.K.Y. Chan
Abstract	Surface pasting is a composition method that applies B-spline surfaces, called features, to any number of other B-spline 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 three-dimensional model directly. In this thesis, I propose a World Space User Interface that attempts to map three-dimensional user actions to two-dimensional 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)

CS-96-31
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)

CS-96-30
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)

CS-96-29
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)

CS-96-28
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 non-conservative 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 second-order variation diminishing property is preserved for non-uniform 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)

CS-96-27
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 advection-diffusion equation. The technique was then extended to encompass the laminar Navier-Stokes equations. The effectiveness of the technique was investigated for flow over a two dimensional backward-facing 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)

CS-96-25
Title	On Line Target Searching in Bounded and Unbounded Domains
Authors	A. Lopez-Ortiz
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 one-sided 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 G-street 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+1-competitive strategy which is robust under navigational error, and equally efficient for oblivious robots. We also present an 1.92-competitive strategy which does not require depth perception from the robot. We also give the best-known 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 non-trivial 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 well-known family of strategies for searching inside simple polygons. In particular we show that Kleinberg's strategy is 2.6-competitive, and that continuous bisector, which is in many respects a good strategy, is at least 1.68-competitive. 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)

CS-96-24
Title	Double-Blind Scores of an Object-Oriented Modeling Survey
Authors	R.S.C. Yiu
Date	June 1996
Report	Double-Blind Scores of an Object-Oriented Modeling Survey (PDF)			Compressed PostScript: Double-Blind Scores of an Object-Oriented Modeling Survey (GZIP)

CS-96-23
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

CS-96-22
Title	Spline-Based Tools for Conventional and Reflective Image Reproduction
Authors	I.E. Bell
Date	May 1996
Report	Only available in printed format

CS-96-21
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 q1q2 q1q2*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)

CS-96-20
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 non-functional 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 non-functional qualities. Their use enables design for non-functional 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

CS-96-18
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)

CS-96-17
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 widely-distributed. 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)

CS-96-15
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)

CS-96-14
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)

CS-96-13
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)

CS-96-12
Title	A Multicollaborative Push-Caching HTTP Protocol for the WWW
Authors	Alex Lopez-Ortiz
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 client-side LAN, in a Demand-based Document Dissemination (DDD) system fashion. This type of server initiated caching scheme has been termed push-caching. 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 Push-Caching HTTP Protocol for the WWW (PDF)			Compressed PostScript: A Multicollaborative Push-Caching HTTP Protocol for the WWW (PS.Z)

CS-96-09
Title	Tabular Abstraction, Editing and Formatting
Authors	X. Yang
Abstract	This dissertation investigates the composition of high-quality 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 NP-complete problem arises in the formatting process that uses automatic line breaking and determines the physical dimension of a table to satisfy user-specified 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 high-quality layout structure.
Date	January 1996
Report	Tabular Abstraction, Editing and Formatting (PDF)			Compressed PostScript: Tabular Abstraction, Editing and Formatting (PS.Z)

CS-96-07
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. Two major data models in which documents are represented and stored are: a relational data model, where all text contents in a document are represented in relations, each with several attributes, or a text data model, where documents are represented as contiguous characters, typically interspersed with tags to capture their various logical, semantic, and presentational features and relationships. Each approach has its own strengths and limitations. In our work, we study how a hybrid system based on a combined text/relational model can support document management. We describe database design trade-offs involving the appropriate placement of information in the text and relational database components. With an appropriate design, the advantages of both models can be exploited, while the shortcomings of using them individually are diminished. We propose a set of primitive operations and a methodolgy for using them to evaluate the various alternatives for data placement. The methodology consists of simulating pre-defined, representative, document management tasks using the primitive operations and studying the numbers, types, and the time performance of the operations involved. Using some representative document management tasks as examples, we demonstrate the use of the methodology and the primitive operations to study and compare the processing of the tasks in the various data models mentioned above.
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)

CS-96-04
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 pre-multiplier matrix U such that UA=H . Our algorithm requires O~(m^(\theta-1) 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 t-bit 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)

CS-96-03
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^(\theta-1) m M(n log \|\|A\|\|)) bit operations (where \|\|A\|\| = max \|A_{i,j}\| and M(t) bounds the cost of multiplying two t-bit 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)