From: farrell@coral.cs.jcu.edu.au (John Farrell)
Newsgroups: comp.doc.techreports
Subject: JCU Comp Sci, early technical reports
Date: Thu, 1 Oct 92 16:47:00 +1000
Organization: James Cook University
NNTP-Posting-Host: oak.ucsc.edu
Originator: golding@oak


These are the earlier technical reports issued by the department. These were
not included in my earlier posting.
---

			 Department of Computer Science
			      James Cook University
				Technical Reports

  Single copies of Technical Reports are available free of charge by writing
to farrell@coral.cs.jcu.edu.au, or

Department of Computer Science
James Cook University
Townsville 4811
AUSTRALIA

  Multiple copies are available by arrangement.

Technical Report 87/1

AUTHOR: D.R. Sweet

TITLE: The Use of Pivoting to Improve the Numerical Performance of Toeplitz
       Matrix Algorithms

ABSTRACT:

Classical O(n^2) solvers break down if any leading principal submatrices are
singular, and as might be expected, the occurrence of nearly-singular leading
submatrices can cause a serious loss of accuracy in these solvers. In this
paper, a pivoting scheme has been incorporated into the Toeplitz solver of
Bareiss which allows near-singularities to be treated without significant
loss of accuracy. As special cases, the pivoted Toeplitz solver also handles
exact singularities and numerical singularities - the latter appear as near
singularities when finite-precision floating-point arithmetic is used.
Bareiss's algorithm can also be used to compute the LU factors of a Toeplitz
matrix, and it is shown that a restricted version of the pivoted Toeplitz
solver produces an LU factorization of a row and column permuted version of
the original Toeplitz matrix. Finally, it is shown how the inverter of Trench
and Zohar can be derived from the multipliers produced by the Bareiss
algorithm, and this connexion is used to derive a pivoted version of the
Trench-Zohar algorithm from the pivoted Bareiss algorithm.


Technical Report 87/2

AUTHOR: R. Joyce

TITLE: Humor Generation

ABSTRACT:

Artificial Intelligence is concerned with emulating various aspects of human
intelligence. Although no general theory of human intelligence exists, it is
apparent that intelligence is manifest in many different forms of behaviour.
In our attempt to reach the Turing Test goal, we try to embody models of
human cognitive processes in programs to generate intelligent behaviour.
Although much work has been done to develop systems that display
intelligence/expertise in some domain(s), human-like behaviour is often
judged as such for reasons other than the direct display of formal reasoning.
One such type of uniquely human behaviour is the exhibition of creativity.
This paper describes work towards modelling the creative process of humor
generation. Humor theory is introduced and an algorithm is presented that
embodies part of the current incongruity-resolution model of humor for
generation of a type of verbal humor. World knowledge is encoded in a
knowledge representation environment based on conceptual graphs [Sowa 1984].


Technical Report 88/3

AUTHOR: R. Joyce

TITLE: A Knowledge Representation Environment for Shared World Knowledge

ABSTRACT:

One of the main problems of artificial intelligence is the representation and
use of shared common background knowledge. While AI projects have
successfully modelled human behaviour in some areas, they are typically
limited to operation within a narrow domain of knowledge. As human
communication relies heavily on a database of shared background knowledge,
the integration of existing AI projects and techniques to yield systems of
more general intelligence depends in part on a shared, well defined, uniform
knowledge base.  
KRE is a knowledge representation environment designed to manage and
manipulate large bodies of diverse knowledge that can be shared by various AI
applications. It provides a manager for, and interface to, a centralized
knowledge database. The notable features of the system include a conceptual
level knowledge base with a mapping onto FOL, a kernel of formation rules for
canonically generating new knowledge, a set of graph manipulation routines, a
rudimentary natural language interface, and automatic accretion of concepts
and language tokens. The architecture of the system is presented along with a
description of its main features. An application program is then shown to
demonstrate the use of KRE.


Technical Report 88/4

AUTHOR: D.R. Sweet

TITLE: The Propagation of Rounding Errors in Pivoting Techniques for Toeplitz
       Matrix Solvers

ABSTRACT:

Classical O(n^2) methods for solving systems of equations whose coefficient
matrix is Toeplitz suffer a serious loss of accuracy if any leading principal
sub-matrices are ill-conditioned, but a pivoting technique can be used to
overcome this problem in most cases. However, in some cases, this technique
does not terminate normally, but requires the reduction of a small
non-Toeplitz matrix at the end. We propose a method of augmenting the system
so that it still terminates in O(n^2) operations in these cases. A rounding
error analysis is carried out which shows that the error bounds of the
pivoted solver are much less than those of the classical solver. This
conclusion is supported by experimental results from a variety of Toeplitz
matrices.


Technical Report 89/5

AUTHOR: R. Joyce & G.K. Gupta

TITLE: User Authorisation Based on Keystroke Latencies

ABSTRACT:

A handwritten signature is commonly used as a unique static identifier for an
individual. The differences in training, physiology, psychology, etc, that
help make a handwritten signature unique also provide a unique digital
signature in the form of a stream of latency periods between keystrokes.
This digital signature can be especially strong for well known key sequences
such as username, password, surname, etc. This paper describes an
implementation of a method of verifying the identity of a user based on such
a digital signature derived from a modified Unix(*) login sequence. The
addition of keystroke latency information to passwords can provide another
dimension to computer security. Results from trial usage of the system are
presented.


Technical Report 89/6

AUTHOR: R. Joyce & J. Bell

TITLE: Mapping Conceptual Graphs onto Natural Language

ABSTRACT:

An algorithm for mapping conceptual graphs [Sowa 1984] onto natural language
is presented. The algorithm provides a compact and efficient method of
generating English sentences and is compared to a similar algorithm given by
Sowa. In addition to allowing a conceptual graph to be uttered as a sentence,
the algorithm can construct queries regarding the validity of any relation in
the graph. The algorithm relies on natural language generation rules, the
number of which is proportional to the number of known conceptual relations.
A variety of sentences can be generated from one graph by allowing the
traversal path to start at any relation node in the graph.


Technical Report 89/7

AUTHOR: R. Joyce & P. Stephenson

TITLE: Blue Skies to Red Sunsets

ABSTRACT:

The sun paints a complex and beautiful picture using the sky as a canvas. A
common assumption in computer graphics is that a naturally lit scene is pure
white and that the medium through which the light is travelling has no effect
on it. To capture the rich and varied effects of atmospheric scattering, we
must use lighting models based on the physical light scattering theory
developed by Lord Raleigh. A variant of the common ray tracing model is used
to display the effects of molecular and particle scattering.


Technical Report 89/8

AUTHOR: Y. Jiang, P. Chaudhuri, G.K. Gupta

TITLE: Dynamic Data Balancing Algorithm for a Shared-Nothing Multiprocessor
       Database System

ABSTRACT:

This paper presents a dynamic data balancing algorithm for a shared-nothing
multiprocessor database system. Dynamic data balancing is important in most
multiprocessor and distributed database systems since even if the initial
data distribution is uniform, the distribution of data may become highly
non-uniform as random insertion and deletion operations take place. Balanced
distribution of data is likely to improve the overall system performance
since, in general, uniformly distributed data implies uniformly distributed
workload among the processors. The data balancing method proposed provides a
mechanism for dynamic redistribution of data whenever the distribution
becomes non-uniform. The algorithm presented, although developed for a
shared-nothing multiprocessor system, can easily be adapted to other
multiprocessor architectures as well as distributed database systems.

===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu