1995 Tech Reports
AUTHOR: Bruce Litow and Olivier de Vel
TITLE:
The Weighted Finite Automaton Inference Problem
ABSTRACT:
The problem of inferring a minimum state weighted finite automaton
(WFA) from a pixel image can be regarded as a problem of computational
algebraic geometry. In the case where the image has been WFA
generated, we give an impractical algorithm that produces a minimum
state WFA that generates the image. We also show that the same method
can be applied to the case of an arbitrary image. An immediate
consequence of the algebraic geometry approach is that weights can
always be taken to be (at worst) real algebraic numbers.
AUTHOR: James Bell
TITLE:
Compact Search Trees for Main Memory Indices
ABSTRACT:
The classical storage representation for binary search trees requires
two pointers per key value stored in the tree. The compact tree is an
alternative method of representing binary trees in memory which
requires on average between one and two pointers per key, depending on
the structure of the tree. The memory requirements for compact trees
are shown to depend on the degree of balance within the tree, and thus
the compact representation is best suited to trees such as the AVL
tree.
Our results show that compact trees require 11% less memory than
classical trees on average for randomly constructed binary search
trees. When used for the storage of AVL trees at least 16% less memory
is required in the worst case and typically 28% less memory is required
than for a classical AVL tree. As usual a penalty with respect to
execution efficiency must be paid. It was found that on average the
classical binary search tree performs insertion and search operations
approximately 21% and 31% faster respectively than the compact binary
search tree. The classical AVL tree performs insertion and search
operations approximately 26% and 23% faster than the compact AVL tree.
Compact trees are therefore recommended for applications where storage
space is at a premium, such as when building an index in main memory.
AUTHOR: Bruce Litow
TITLE:
Decidable Cases of the Rational Sequence Problem
ABSTRACT:
Partial results concerning the decidability of the Rational Sequence
Problem are presented. The two most notable make use of methods drawn
from transcendental number theory and computational commutative
algebra, respectively.
AUTHOR: Andrew Chiu, George Davida, and Bruce Litow
TITLE:
Integer Division is in NC
At request of the author this report has been made unavailable
AUTHOR: B. Litow
TITLE:
A Size Efficient Polylog Time Context-Free Language Recognition Algorithm
ABSTRACT:
Context-free language (CFL) recognition was first shown to be in NC by
Ruzzo. In fact the algorithm there is NC2, however it appears to
require 0(n6) processors in the PRAM model. This paper
presents a simple NC3 CFL recognition algorithm, using the Boolean
circuit model. The algorithm requires O(n2) processors and
involves a sequence of log n matrix powering operations. The NC3
algorithm is also interesting because it is a parallelization of the
Cocke-Younger-Kasami (CYK) algorithm and shows that other 2-dimensional
dynamic programming algorithms can be parallelized in a similar
fashion.
AUTHOR: Christian B. Suttner and Geoff Sutcliffe
TITLE:
The TPTP Problem Libarary
ABSTRACT:
This report provides a detailed description of the TPTP library of
problems for automated theorem proving systems. This library is
available via Internet, and is intended to form a common basis for the
development of and experimentation with automated theorem provers. To
support this goal, this report provides
- the motivations for building the library;
- a discussion of troublesome issues, and how they have been resolved;
- a description of the library structure, including overview information;
- information on each problem contained in the library;
- descriptions of supplementary utility programs;
- guidelines for obtaining and using the library
AUTHOR: Curtis E. Dyreson, Richard T. Snodgrass, and Marshall Freiman
TITLE:
Efficiently Supporting Temporal Granularities in a DBMS
ABSTRACT:
Granularity is an integral feature of temporal data. For instance, a
person's age is commonly given to the granularity of years and the time of
their next airline flight to the granularity of minutes. A granularity
creates a discrete image, in terms of granules, of a (possible
continuous) time-line. Pairs of granularities are related in that some
granularities are finer or coarser with respect to other
granularities. A granularity graph records all the relationships
between granularities, even among granularities in different
calendars. Indeterminacy, or ``don't know when'' information , is a
companion to granularity. A birthday, given to the granularity of
days, does not reveal precisely when a person was born, only that they
were born sometime during the indicated day. Temporal granularity and
indeterminacy are two sides of the same coin, in that a time at a given
granularity is indeterminate at all finer granularities. We present a
formal model for granularity in temporal operations. We also minimally
extend the syntax and semantics of SQL-92 to support mixed
granularities. This support rests on two operations, scale and cast,
that move times within the granularity graph, e.g., from days to
months. We demonstrate that our solution is practical by outlining an
efficient implementation. The implementation uses several optimisation
strategies to mitigate the expense of accommodating multiple
granularities.
AUTHOR: Anthony M. Sloane and Jason Holdsworth
TITLE:
Beyond Traditional Program Slicing
ABSTRACT:
Traditional program slices are based on variables and statements.
Slices consist of statements that potentially affect (or are affected
by) the value of a particular variable at a given statement. Two
assumptions are implicit in this definition: 1) that variables and
statements are concepts of the programming language in which the
program is written, and 2) that slices consist solely of statements.
Generalised slicing is an extension of traditional slicing where
variables are replaced by arbitrary named program entities and
statements by arbitrary program constructs. A model of generalised
slicing is presented that allows the essence of any slicing tool to be
reduced to a node marking process operating on a program syntax tree.
Slicing tools can thus be implemented in a straight-forward way as
reusable modules using tree-based techniques such as attribute
grammars.
A variety of useful program decompositions are shown to be instances
of generalised slicing. Examples include call graph generation and
interface extraction. To show the wide applicability of generalised
slicing examples are also given of how slicing can enhance
understanding of formal compiler specifications and make it possible
to create subset language specifications.
AUTHOR: Bernard Mans
TITLE:
Portable Distributed Priority Queues with MPI
ABSTRACT:
Part of this work has been presented in the Proc. of the IEEE
International Conference on High Performance Computing, pp. 16--21,
New Delhi, India, 27-30 December 1995, S. Sahni and V. Prasanna and
V. Bhatkar Editors, Tata-Mcgraw Hill.
This paper analyzes the performances of portable distributed priority
queues by examining the theoretical features required and by comparing
various implementations.
In spite of intrinsic bottlenecks and induced hot-spots, we argue that
tree topologies are attractive to manage the natural centralized
control required for the {\em deletemin} operation in order to detect
the site which holds the item with the largest priority. We
introduce an original perfect balancing to cope with the load
variation due to the priority queue operations which continuously
modify the overall number of items in the network.
For comparison, we introduce the d-heap and the binomial distributed
priority queue. The purpose of this experiment is to convey, through
executions on Cray-T3D and Meiko-T800, an understanding of the nature
of the distributed priority queues, the range of their concurrency and
a comparison of their efficiency to reduce requests latency. In
particular, we show that the d-heap combines an adjustable degree with
a small depth, which make it efficient in both theory and
practice. The Message Passing Interface (MPI) provides us with an
adequate portable code.
AUTHOR: Brendan McCane and Terry Caelli
TITLE:
Multi-scale Adaptive Segmentation using Edge and Region Based Attributes
ABSTRACT:
We present an adaptive multi-scale algorithm using edge and region
information for segmenting intensity images into closed regions. The
need for segmentation is determined by region statistics and
segmentation is actually performed using edge based
information. Results are shown for a number of images displaying
significant improvements over mono-scale segmentation.
AUTHOR: Curtis E. Dyreson and Anthony M. Sloane
TITLE:
The Boomerang White Paper: A Page As You Like It
ABSTRACT:
Boomerang is a dynamic HTML page reconfiguration system. A user
accesses Boomerang via the Common Gateway Interface. The user supplies
a page name and a template, Boomerang fetches the requested
page and uses the template to reconfigure it. The template is a
sequence of string manipulation rules. The rules are written in a
simple regular expression-based pattern matching language. Boomerang
also parses HTML variables in forms and query strings and makes those
variables available in the template.
By taking advantage of Boomerang's dynamic page reconfiguration
features, users can easily add navigational links, suppress images,
redefine HTML tags, and reshape a page as desired. Since Boomerang is
reached through the Common Gateway Interface and understands HTML
variables, Boomerang can also be used as a general form-handling
script. Several examples are given to show the utility of Boomerang.
Boomerang is compatible with existing browsers and servers and
does not compromise their security.
AUTHOR: Brendan McCane, Terry Caelli and Olivier de Vel
TITLE:
Learning to Recognise 3D Objects from 2D Views
ABSTRACT:
In this paper we further explore the use of machine learning (ML) for
the recognition of 3D objects in isolation or embedded in scenes. Of
particular interest is the use of a recent ML technique (specifically
CRG - Conditional Rule Generation) which generates descriptions of
objects in terms of object parts and part relational attribute bounds.
We show how this technique can be combined with intensity-based model
and scene views to locate objects and their pose. The system is
demonstrated with a number of real objects and scenes with promising
results.
AUTHOR: Lukito Nugroho and Geoff Sutcliffe
TITLE:
A Tool for Introducing Persistent Programming
ABSTRACT:
Programming languages, using conventional file systems, are known to be
ineffective at managing objects that outlive their creator programs.
Researchers have shown that persistent programming, that is programming
that involves persistent objects, can overcome the problem. Although
persistent programming has proved to be advantageous and persistence
systems designed for programmers are available, persistent programming
is not yet widely practiced. This work develops a persistent programming
tool for introducing programmers to persistent programming. The heart of
the tool is a persistent object structure manager (POSM) that lets
programmers create, use, and delete persistent object structures from
inside a C program.
AUTHOR: Curtis Dyreson
TITLE:
Automatic Filtering of Now-centric Data
ABSTRACT:
A now-centric collection of data is characterised by the property that
as data in the collection ages, each datum individually becomes less
relevant, but remains relevant in aggregate. Such data can be filtered
by materialising an aggregate view on the data and then compressing,
moving to backup, or deleting the data from which that view was
materialised, yielding a smaller collection of data.
This paper describes a tool to automatically filter data by building a
statistical database from the now-centric collection of data. To build
the statistical database, the user supplies a list of filters. Each
filter consists of a filter unit and a filter measure. The filter unit
specifies a pattern (a regular expression) to match as the now-centric
data is filtered. The filter measure is the system of measurement in
which occurrences of that pattern are counted. A key feature of the
tool is that users may define their own units and measures. Queries on
the filtered data are analysed to determine if sufficient information
has been filtered to satisfy the query. If necessary the filtered
information is automatically converted from the filter measure to the
query measure, resulting in a very flexible query mechanism.
AUTHOR: Geoff Sutcliffe and Christian B. Suttner
TITLE:
The Design of the CADE-13 ATP System Competition
ABSTRACT:
Running a competition for Automated Theorem Proving (ATP) systems is a
difficult and arguable venture. However, we belief that the potential
benefits of such an event by far outweigh the controversial aspects.
The motivations for this competition are to contribute to the
evaluation of the relative capabilities of ATP systems, to stimulate
ATP research and system development, and to expose ATP systems to
interested researchers both within and outside the ATP community. This
paper identifies and discusses the issues that determine the nature of
the CADE-13 ATP system competition. Choices and motivated decisions,
with respect to the issues, are given.
AUTHOR: Geoff Sutcliffe and Christian B. Suttner
TITLE:
ATP System Results for the TPTP Problem Library (upto TPTP v1.1.3)
ABSTRACT:
Since the first release of the TPTP problem library in 1993, many
researchers have used the TPTP as an appropriate and convenient basis
for ATP system evaluation. Some researchers, who have tested their ATP
systems over the entire TPTP, have made their result data available.
The data is tabulated in this report. This data does not
provide a basis for comparing the ATP systems. Rather, it documents
how individual ATP systems have performed on the TPTP, using their
specific calculus, implemented using specified software, and executing
on certain hardware within user determined resource constraints.
© James Cook University of North Queensland, Australia
Computer Science Home Page