# [Please remove <h1>]

<1995 | 1997> |

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 | Adobe PDF | Compressed PostScript |

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 | PostScript |

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 | PostScript |

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 yetprovides the user with the necessary functionality identified in existing literature for geographic applications. | |||

Date | November 1996 | |||

Report | PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 Content | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 modeling interface for surface pasting. | |||

Date | September 1996 | |||

Report | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

CS-96-24 | ||||
---|---|---|---|---|

Title | Double-Blind Scores of an Object-Oriented Modeling Survey | |||

Authors | R.S.C. Yiu | |||

Abstract | ||||

Date | June 1996 | |||

Report | Adobe PDF | Compressed PostScript |

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 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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

CS-96-15 | ||||
---|---|---|---|---|

Title | Overview of GSM: The Global System for Mobile Communications | |||

Authors | J. Scourias | |||

Date | March 1996 | |||

Report | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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.Differential algebra. Rewrite systems. Polynomial differential
equations. Rosenfeld's lemma.
Keywords: | |||

Date | April 1996 | |||

Comments | Submitted to IMACS'96 | |||

Report | Adobe 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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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. - 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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

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 | Adobe PDF | Compressed PostScript |

<1995 | 1997> |