computer science

OUCS-2017-07

Richard O'Keefe
Department of Computer Science, University of Otago

Complex Arithmetic is Complex

Abstract:
Floating-point arithmetic is tricky. This report examines the apparently simple case of basic complex arithmetic in order to illustrate this.

OUCS-2017-06

Richard O'Keefe
Department of Computer Science, University of Otago

Logic Programming Modules as Possible Worlds

Abstract:
Existing module systems for logic programming, such as ISO Prolog part 2 or Mercury are basically syntactic in nature. They are intended to be compatible with the usual semantics of logic programming. Taking a semantic view leads to the idea of modules as possible worlds, and cross- module calling as a modal operator. This opens up additional possibilities, including some useful for software engineering.

OUCS-2017-05

Richard O'Keefe
Department of Computer Science, University of Otago

Child Modules for Erlang and Prolog

Abstract:
Prolog and Erlang have similar module systems, where modules in a flat namespace are both the sole form of encapsulation and the units of code loading and replacement. They also support the inclusion of text files as a way of sharing declarations and private functions between modules. This note proposes a replacement for text inclusion inspired by child modules in Ada.

OUCS-2017-04

Alistair Knott
Department of Computer Science, University of Otago

Sensorimotor cognition and natural language syntax Part II

Abstract:
This book is a continuation of the idea I developed in my earlier book, 'Sensorimotor Cognition and Natural Language Syntax' (Knott, 2010). In that book, I suggested that the syntactic structure of a sentence reporting a concrete episode could be interpreted as a description of sensorimotor processing. I expressed this idea using the syntactic framework of Minimalism (Chomsky, 1995), in which every sentence has two syntactic representations: a phonetic form (PF) and an underlying logical form (LF). My proposal was that the LF of a sentence S reporting a concrete episode E can be characterised as a description of the sensorimotor processes involved in actually experiencing the episode E. In the earlier book, I focussed on a single syntactic construction (a transitive clause) when presenting and motivating this proposal. Obviously I must consider a wider range of constructions. In the current book I examine how the original proposal extends to other syntactic constructions.

OUCS-2017-03

Alistair Knott, Lech Szymanski, Brendan McCane
Department of Computer Science, University of Otago

Martin Takac
Centre for Cognitive Science, Comenius University, Slovakia

A model of object property representations: visual object classification, working memory and the syntax of predication

OUCS-2017-02

Alistair Knott
Department of Computer Science, University of Otago

An extended model of deictic routines, supporting a wider-coverage SM interpretation of syntax

OUCS-2017-01

Alistair Knott
Department of Computer Science, University of Otago

Road map for an embodied model of language and cognition

OUCS-2016-04

Alistair Knott
Department of Computer Science, University of Otago

Martin Takac
Centre for Cognitive Science, Comenius University, Slovakia

A simulationist model of episode representations in working memory: syntactic interpretation, nested episodes and storage requirements

Abstract:
This report supplements Takac and Knott's model of working memory (WM) for episodes and individuals. In Section 1 we introduce our interpretation of syntactic heads in relation to this WM model in more detail. In Section 2 we present some ideas about how the WM model can be extended to handle nested episodes. In Section 3 we discuss the storage requirements of the model, and assess whether it can be extended to represent a realistic number of episodes and individuals.

OUCS-2016-03

Richard O'Keefe
Department of Computer Science, University of Otago

How to compute a mean?

Abstract:
Computing the mean of a sequence of numbers is easy; computing means of other kinds of measurements, and for other kinds of container, is harder. This note presents some algorithms and benchmarks.

OUCS-2016-02

Lahiru Ariyasinghe, Zhiyi Huang, David Eyers
Department of Computer Science, University of Otago

The Impact of IP Network Impairments on Optimal Playback Buffer Size in Video Streaming

Abstract:
A key challenge for online video streaming services is how to deliver their data over networks that suffer packet losses and delays while maintaining a good Quality of Experience (QoE). Metrics such as start-up delay, the count of the number of times that re-buffering occurs and re-buffering delays provide useful indicators to the streaming services to measure the impact of IP network impairments (e.g. packet loss and delay) on overall video stream quality. Playback buffering is one of the key application-level techniques that can mitigate the impact of network impairments and protect the video quality by sensibly balancing the effect of the above metrics. However for the mitigation to be effective, while maximising user QoE, setting an optimal playback buffer size is vital. In this paper, a comprehensive analysis is performed to investigate the impact of packet loss and link delay on optimal playback buffer sizing, with respect to video files that contain different amounts of motion. Experimental results indicate that the buffer size that delivers an optimal start-up delay with acceptable levels of playback disruption remains reasonably constant, when changing the degree of motion in the video, and in response to minor variation of link delay and small amounts of packet loss. This is in contrast to the buffer size that ensures no interruptions to playback, which, as expected, rises steadily.

OUCS-2014-04

Glenn Blanchette, Brendan McCane, Willem Labuschagne and Anthony Robins
Department of Computer Science, University of Otago

Representing Symbolic Logic in an Artifical Neural Network

Abstract:
We report detailed experimental results for the paper 'Representing Symbolic Logic in an Artificial Neural Network, Part I: the Static Case'.

OUCS-2014-02

Lech Szymanski, David Eyers
Department of Computer Science, University of Otago

Practical use of SELinux for enhancing the security of web applications

Note: If readers wish to run through examples, the report is also available here. This has links to Virtual Machine files so that people working through the tutorial can choose to start off at any chapter.

Abstract:
The Security-Enhanced Linux (SELinux) module has been available in the mainline kernel for many years (since 2003), and is included as part of a growing number of popular Linux distributions. However adopting its new and powerful security capabilities has been daunting to many. On forums, the advice regarding many SELinux related issues is simply, 'Disable SELinux'. The earlier sections of this document should provide enough practical SELinux context to avoid the need for such blunt solutions. The later sections will demonstrate how to write your own SELinux policy to enhance the security of a web-based content-management system. This tutorial came about as a result of an investigation into the viability of using SELinux to secure multi-tier web systems that process sensitive data, as inspired by the SafeWeb project .

OUCS-2014-01

Jeremy Lee-Hand and Alistair Knott
Department of Computer Science, University of Otago

A neural network model of causative actions

Abstract:
In this paper we present a neural network model of motor learning and motor control that learns a class of actions termed causative actions. A causative action is an action that brings about a speci ed e ect or movement in a target object: for instance the action of causing a lever to bend, or of causing a door to open. The network comprises a layered set of motor learning circuits that associate motor actions with their sensory e ects, as proposed by Hommel et al. [1]. The circuit for learning simple manual actions is trained by sensory representations in the haptic modality that function as rewards, as previously proposed by Oztop and Arbib [2]. We propose that the circuit responsible for learning causative actions makes similar use of sensory representations as reward signals. The key novel idea is that the sensory representations in this case come not from the tactile system, but from a high-level perceptual module that registers arbitrary movements taking place in external objects in the world. 

OUCS-2013-13

Adeel Javed, Haibo Zhang, and Zhiyi Huang
Department of Computer Science, University of Otago

Jeremiah Deng
Department of Information Science, University of Otago

BWS: Beacon-driven Wake-up Scheme for Train Localization using Wireless Sensor Networks

Abstract:
Real-time train localization using wireless sensor networks (WSNs) offers huge benefits in terms of cost reduction and safety enhancement in railway environments. A challenging problem in WSN-based train localization is how to guarantee timely communication between the anchor sensors deployed along the track and the gateway deployed on the train with minimum energy consumption. This paper presents an energyefficient scheme for timely communication between the gateway and the anchor sensors, in which each anchor sensor runs an asynchronous duty-cycling protocol to conserve energy and wakes up only when it goes into the communication range of the gateway on the train. A beacon-driven wake-up scheme is designed and we establish the upper bound on the amount of time that an anchor sensor can sleep in one duty cycle to guarantee timely wake up once a train approaches. We also give a thorough theoretical analysis for the energy efficiency of our scheme and give the optimal amount of time that an anchor sensor should sleep in terms of minimizing the total energy consumption at each anchor sensor. We evaluate the performance of our scheme through simulations. Simulation results show that our scheme can timely wake up anchors sensors at a very low cost on energy consumption.

OUCS-2013-12

Supporting data files:

connectivity_analysis.tbz2 (3.8MB)
global_analysis.tbz2 (535KB)
network_data_awith.tbz2 (473MB)
network_data_awout.tbz2 (551MB)
network_data_young.tbz2 (576MB)
networks_awith.tbz2 (2.2GB)
networks_awout.tbz2 (2.5GB)
networks_young.tbz2 (2.5GB)
regional_analysis.tbz2 (7.3MB)
voxelwise_analysis.tbz2 (492MB)

If you want these data files, please email Robert Pollock - rpollock@cs.otago.ac.nz - for a download link.

Paul McCarthy, Lubica Benuskova
Department of Computer Science, University of Otago

Elizabeth Franz
Department of Psychology, University of Otago

Functional network analysis of aging and Alzheimer's Disease: Results

Abstract:
This report, and the associated data files, present the results of a functional network analysis conducted upon a fMRI data set, with the aim of identifying differences, in various functional network properties, between a group of healthy young individuals, a group of healthy aged individuals, and a group of individuals diagnosed with probable to mild Alzheimer's Disease. This report is intended as a complement to the PhD thesis Functional network analysis of aging and Alzheimer's Disease, by Paul McCarthy, submitted for the degree of Doctor of Philosophy, at the University of Otago, Dunedin, New Zealand. 

These data files may be used for research purposes. Please cite this report if you do so.

OUCS-2013-11

Jeremy Lee-Hand and Alistair Knott 

Department of Computer Science, University of Otago

Training and testing of a neural network model of motor control

Abstract:
This paper is an appendix to Lee-Hand and Knott (in submission) - A neural network model of causative motor actions and causative alternation. It describes the training and testing of the network model of motor control presented in that paper. 

OUCS-2013-10

Mira Guise, Alistair Knott, Lubica Benuskova

Department of Computer Science, University of Otago

Response Fingerprinting: a probabilistic method for evaluating the network response to stimuli 

Abstract:
Spiking neural networks that have variable connection delays have the interesting property that they are sensitive to both spatial and temporal patterns of input. Each neuron in the network receives input from spatially-distributed input neurons whose precise firing times interact with connection delays to determine whether the neuron can exceed the firing threshold and produce an output. The network is therefore most responsive to spatio-temporal stimuli whose temporal components match the delays in the connected structure of the network. Izhikevich (2006a) has shown that certain strongly connected groups of neurons known as polychronous neural groups (or PNGs) exist in large numbers within the network structure. The activation of these neural groups is stimulus-specific and produces unique firing signatures that are detectable in the firing data. Previous methods for detecting PNG activation have relied on a template matching technique that assumes a deterministic response to each stimulus presentation (Izhikevich, 2006a; Martinez and Paugam-Moisy, 2009; Guise et al., 2013a). Here we present an alternative probabilistic view of the stimulus response and demonstrate the application of this new detection method.

OUCS-2013-09

Note: updated 13.9.13

Hayden Walles, Anthony Robins and Alistair Knott

Department of Computer Science, University of Otago

A neural network model of visual attention and object classification: technical details

Abstract:
This document provides technical details of our neural network model of visual object classification and attention.

OUCS-2013-08

Mira Guise, Alistair Knott, Lubica Benuskova

Department of Computer Science, University of Otago

Consistency of polychronous neural group activation supports a role as an underlying mechanism for representation and memory: detailed methods and results

Abstract:
Izhikevich (2006a) has proposed that certain strongly connected groups of neurons known as polychronous neural groups (or PNGs) might provide the neural basis for representation and memory. Polychronous groups exist in large numbers within the connection graph of a spiking neural network, providing a large repertoire of structures that can potentially match an external stimulus (Izhikevich, 2006a; Izhikevich et al., 2004). In this paper we examine some of the requirements of a representational system and test the idea of PNGs as the underlying mechanism against one of these requirements, the requirement for consistency in the neural response to stimuli. The results provide preliminary evidence for consistency of PNG activation in response to known stimuli, although these results are limited by problems with the current methods for detecting PNG activation.

OUCS-2013-07

Not available: to be published

Yawen Chen, Jason Mair, Zhiyi Huang, David Eyers

Department of Computer Science, University of Otago

A State-based Energy/Performance Model for A Parallel Application on Multicore Computers

Abstract:
In this paper, we design a state-based energy/ performance model for a given parallel application on multicore computer systems. Given the application properties of parallel degree and computation intensity, and the system energy features, we derive the optimal number of cores and the optimal frequencies for the application to achieve the minimum energy consumption. By estimating and quantifying the energy cost for each component in different states, the impact of energy costs for serial/parallel portions and computation/memory portions are revealed when different number of cores and CPU frequencies are assigned. Our proposed model provides an insight on estimating the energy/performance impact of an application on multicore computers, and provides the guidance for achieving tradeoffs between performance and energy consumption.

OUCS-2013-06

Not available: to be published

Yawen Chen, Haibo Zhang

Department of Computer Science, University of Otago

Ke Chen, Huaxi Gu

State Key Laboratory of Integrated Service Networks, Xidian University, Xi'an, China

TWC-based approach for Improving Communication Reliability in Optical Network-on-chip

Abstract:
Optical Network-on-Chip (ONoC) architectures are emerging as a new paradigm to interconnect a large number of processing cores at chip level, thereby enabling to meet the pressing demands for extremely high bandwidth and low power consumption. Some existing ONoC architectures are implemented in an electronic-controlled way in a two-layer 3D chip based on TSV (Through-Silicon-Via). However, on-chip thermal effect is an inherent deficiency and chip temperature can fluctuate spatially, which can affect the operation of silicon nanophotonic devices. This leads to significant influence on the reliability of communications. To minimize the thermal impacts and improve reliability, we propose a novel approach by adding a tunable wavelength converter (TWC) in the router for mesh-based ONoC. Simulation results show that our proposed approach can increase the signal-to-noise ratio (SNR) effectively.

OUCS-2013-05

Not available: to be published

Yawen Chen, Haibo Zhang

Department of Computer Science, University of Otago

Liu Bai, Huaxi Gu

Xidian University, China

A Hierarchical Hybrid Optical-Electronic Clos Architecture for Network-on-Chip

Abstract:
With more and more processor cores integrated on a chip, Networks-on-chip (NoC) is emerging as a candidate architecture for multiprocessor systems-on-chip (MPSoC). Traditional metallic interconnects have become the bottleneck of NoC due to the limited bandwidth, long delay, and high power consumption. Optical Network-on-Chip (ONoC) can decrease interconnect delay and provide higher bandwidth with lower power consumption. In this paper, we propose a Clos-based Hierarchical Optical-Electronic NoC, called CHONoC, which can take advantage of both optical routers and interconnects in a hierarchical manner. CHONoC employs novel designs including two different topologies in optical layer and electric layers, communication mechanism with high path diversity, and two optical symmetric routers with strictly non-blocking property. Simulation results show that CHONoC can achieve small latency and high throughput especially for high local traffic compared with Mesh-based, Cmesh-based and Clos(8,8,8)-based ONoCs.

OUCS-2013-04

Not available: to be published

Yawen Chen, Haibo Zhang

Department of Computer Science, University of Otago

Zheng Chen, Huaxi Gu

State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an, China

Source- and Destination-based Wavelength Assignment Approach in Optical Network-on-Chip: Design and Performance

Abstract:
Photonic interconnect can provide ultra-high bandwidth with low power consumption, which makes Optical Network-on-Chips (ONoCs) a promising alternative for the next generation high performance chip multiprocessors. To make better use of the optical interconnect, Wavelength Division Multiplexing (WDM) is commonly used to provide high bandwidth and decrease the contention possibility. In this paper, we propose two wavelength assignment methods for Mesh ONoCs: source-based wavelength assignment (SW) and destination-based wavelength assignment (DW). These two low complexity approaches allow us to use a limited number of wavelengths according to the source and destination addresses. We evaluate their performance in simulations, and results show that allocating wavelengths according to the source node outperforms destination-based assignment in terms of latency and throughput.

OUCS-2013-thesis01

Kai-Cheung Leung

Department of Computer Science, University of Otago

PhD Thesis: View-Oriented Parallel Programming and its Performance Evaluation on Multicore Architectures

Abstract:
Shared-memory multicore architectures have become pervasive, and there is a pressing need for parallel programming models to facilitate both performance and convenience. However, most existing shared-memory programming models are tedious for programming and are prone to errors such as data race, which are difficult to debug.

To solve this problem, this thesis proposes a data race prevention scheme in the View-Oriented Parallel Programming (VOPP) paradigm. VOPP was proposed for distributed shared memory systems. It is adapted to shared-memory multicore architectures in this thesis. VOPP is a shared-memory data-centric parallel programming model, which uses views to bundle mutual exclusion with data access. In VOPP, programmers partition the shared memory into “views”, which are non-overlapping sets of shared data objects. The data race prevention scheme proposed for VOPP can prevent data race through the memory protection mechanism while keeping the extra overhead low.

To improve the programmability of VOPP, this thesis proposes an automatic view access management scheme where a view is automatically acquired upon its first access, and automatically released when no longer needed, thus relieving programmers from arranging locks to protect critical sections.

To further improve performance and programmability, this thesis proposes the View-Oriented Transactional Memory (VOTM) system, which uses Restricted Admission Control (RAC) to manage the number of processes holding each view according to its contention. In VOTM, RAC can restrict the number of processes holding the view when its contention is high, and in extreme cases, RAC can fall back to the locking mode, in order to avoid abort overheads of transactions. On the other hand, RAC allows unlimited concurrent access to other low-contention views to maximize concurrency, just as in transactional memory. Therefore, VOTM has the merits of both the locking mechanism and the transactional memory (TM) and integrated them nicely through RAC.

This thesis has also provided a theoretical analysis for RAC to investigate factors that indicate performance gain by restricting admission to a view, including disproportionately large portion of time spent in aborted transactions due to high contention and excessive TM mechanism overheads.

Experimental results demonstrate that in many cases, RAC correctly responds to these situations by restricting admission to a view, thus improves the performance. Apart from the improvements of programmability in VOPP, this thesis has done extensive experiments on two multicore architectures, a 16-core machine and a 64-core machine. Experimental results demonstrate that VOPP can provide a data race free environment with low overheads on multicore architectures, and VOTM outperforms both traditional transactional memory models and lock-based models in most benchmark applications.

OUCS-2013-03

Note: This report was updated 31.10.2014

Mira Guise, Alistair Knott, Lubica Benuskova

Department of Computer Science, University of Otago

Spinula: software for simulation and analysis of spiking network models

Abstract:
Spinula is a software package for the simulation and analysis of spiking neural network models. It consists of a core library that provides the simulation environment, and additional libraries that support analysis and visualization of the resulting data. This report examines each of these libraries and provides a detailed description of the included services and examples of how they might be used.

OUCS-2013-02

Mira Guise, Alistair Knott, Lubica Benuskova

Department of Computer Science, University of Otago

Experiments on the effect of synaptic disruption on polychronous group formation: detailed methods and results

Abstract:
Izhikevich (2006a) claims that groups of strongly connected neurons known as polychronous neural groups (PNGs) could provide the basis for memory in the brain. Polychronous groups exist as spatio-temporal patterns of connection lengths and weights; when activated by a matching input pattern, they are able to produce a causal chain of firing events that is not synchronous but is nevertheless precisely timed and consistently reproducible.

Izhikevich et al. (2004) have previously shown that synaptic disruption produces a dramatic decrease in PNG counts, leading them to the conclusion that PNG formation depends on activity-dependent changes in synaptic plasticity. However, despite the disruption some polychronous groups remain in the network, suggesting that polychronous groups can sometimes be formed by chance arrangements of synaptic weights in the network. In the following report we reproduce and extend the work of Izhikevich et al. (2004) by delving further into the nature of PNG formation: firstly, we examine the effects of synaptic disruption on the groups that remain; we then examine the considerable inter-network variation in PNG counts over the time-course of network maturation and categorize the resulting pro.les into discrete classes of behavior.

The first experiment found a highly signifcant decrease in PNG count following synaptic disruption (paired t(19) = 9:0; p < 0:001), reproducing the previous report (Izhikevich et al., 2004). However, we also found a highly significant decrease in both size (paired t(19) = 10:7; p < 0:001) and temporal length (paired t(19) = 10:8; p < 0:001) in the remaining polychronous groups. A further experiment employing sampling at multiple time-points found two previously unreported phenomena: firstly, there is a consistent small peak in the PNG counts immediately following initialization; secondly, comparison of the temporal profiles of multiple networks over the course of maturation shows two broad classes of network behavior: either cyclic, or an initial burst of productivity followed by a slow decline. These results are discussed in the context of a model of PNG formation involving an activity- dependent interaction between supported and adapted groups which is at the heart of PNG formation.

OUCS-2013-01

Martin Takac

Centre for Cognitive Science, Comenius University, Slovakia

Alistair Knott

Department of Computer Science, University of Otago

A neural network model of working memory for episodes

Abstract:
We present a neural network model of the storage of episode representations in working memory (WM). Our key idea is that episodes are encoded in WM as prepared sensorimotor routines: i.e. as prepared sequences of attentional and motor operations. Our network reproduces several experimental findings about the representation of prepared sequences in prefrontal cortex. Interpreted as a model of WM episode representations, it has useful applications in an account of long-term memory for episodes and in accounts of sentence processing.

Now
published

Alistair Knott

Department of Computer Science, University of Otago

Sensorimotor Cognition and Natural Language Syntax

Abstract:
(17/9/2012 - Report has been removed as the book was published in October 2012. See the publisher page.)

This book is about the interface between natural language and the sensorimotor system. It is obvious that there is an interface between language and sensorimotor cognition, because we can talk about what we see and do. The main proposal in the book is that the interface is more direct than is commonly assumed.

OUCS-2011-04

Richard O'Keefe

Department of Computer Science, University of Otago

Specifying Exact Scaled Decimal Arithmetic

Abstract:
The ANSI Smalltalk standard includes a ScaledDecimal class for decimal fixed point arithmetic, but the specification is so vague that implementations vary greatly. The Language Independent Arithmetic standard has nothing to say about this data type. This article presents one reasonable specification, treating these numbers as exact.

OUCS-2011-03

Martin Takac, Lubica Benuskova and Alistair Knott

Department of Computer Science, University of Otago

A connectionist model of language acquisition and sentence generation: Technical appendix

Abstract:
In this report we present technical details of a neural network model of sentence generation, including details of the artificial languages it was trained on, its training regime, and of the performance of the trained network.

OUCS-2011-02

Hayden Walles, Anthony Robins and Alistair Knott

Department of Computer Science, University of Otago

Performance of a convolutional classifier network on the MNIST handwritten digit database

Abstract:
This report describes an experiment in which the convolutional neural network of Walles et al. (2008) is trained and tested on the MNIST database of handwritten digits (LeCun et al, 1999).

OUCS-2011-01

Martin Takac, Lubica Benuskova, Alistair Knott

Department of Computer Science, University of Otago

Mapping sensorimotor sequences to word sequences: A connectionist model of language acquisition and sentence generation

Abstract:
In this article we present a neural network model of sentence generation. The main technical novelty in the model is in its semantic representations: the messages which form the input to the network are structured as sequences, which are delivered to the network one at a time. Rather than learning to linearise a static semantic representation as a sequence of words, our network rehearses a sequence of semantic signals, and learns to generate words from selected signals. Our use of sequences to encode semantic representations has several benefits, both conceptual and technical. Conceptually, the use of rehearsed sequences of semantic signals connects to work in embodied cognition, which posits that the structure of semantic representations has its origin in the serial structure of sensorimotor processing. It also connects to nativist models of language development: we argue that some of the linguistic universals proposed within Chomskyan models of syntax can be interpreted as reflections of sensorimotor processing. Technically, the use of sequentially structured semantic representations permits a novel answer to the question of how a neural network can learn genuinely abstract syntactic rules (a vexed question in connectionist models of language). Equally importantly, it supports a way of using abstract syntactic rules in combination with rules about surface patterns in language. In summary, sequentially structured semantic representations allow a neural network model which combines elements from nativist, empiricist and embodied theories of language in a novel way.

OUCS-2010-04

K. Leung and Z. Huang

Department of Computer Science, University of Otago

View-Oriented Transactional Memory

Abstract:
This paper proposes a View-Oriented Transactional Memory (VOTM) model to seamlessly integrate different concurrency control methods including locking mechanism and transactional memory. The model allows programmers to partition the shared memory into “views” which are nonoverlapping sets of shared data objects. A Restricted Admission Control (RAC) scheme is proposed to control the number of processes accessing each view in order to reduce the number of aborts of transactions. The RAC scheme has the merits of both the locking mechanism and the transactional memory. Experimental results demonstrate that VOTM outperforms traditional transactional memory models such as TinySTM by up to five times. Also VOTM outperforms pure lockbased models in applications with long critical sections and has comparable performance with lock-based models in other cases.

OUCS-2010-03

Michael Albert

Department of Computer Science, University of Otago

Young classes of permutations

Abstract:
We characterise those classes of permutations having the property that for every tableau shape either every permutation of that shape or no permutation of that shape belongs to the class. The characterisation is in terms of the dominance order for partitions (and their conjugates) and shows that for any such class there is a constant k such that no permutation in the class can contain both an increasing and a decreasing sequence of length k.

OUCS-2010-02

Martin Takac, Alistair Knott, Lubica Benuskova

Department of Computer Science, University of Otago

Generation of idioms in a simple recurrent network architecture

Abstract:
Idioms are an ideal testbed for studying the interplay of lexical (content preparing) and syntactic (structure building) mechanisms in language production. This article contributes to the debate about the nature of these mechanisms and their relationship from the viewpoint of computational modeling. We present a neural network model of sentence generation, which is able to produce continuous and discontinuous idioms within regular compositional sentences. The model is a simple recurrent network extended to include a semantic episode representation as an extra input. Our main contribution consists in a detailed analysis of the representational space of the network's hidden layer, which shows that (1) an implicit structure-content division can arise as a result of internal space reorganization within a single SRN during learning, (2) idioms can be produced by the same general sequencing mechanism that works for regular sentences, (3) the production of idioms is modulated by content-specific mechanisms.

OUCS-2010-01

This report is now available here

Benuskova L (2012)

Why is it hard to induce LTD?

Proc. IEEE International Joint Conference on Neural Networks (IJCNN), pp. 3329-3335.

Digital Object Identifier: 10.1109/IJCNN.2012.6252827

OUCS-2009-01

Kai-Cheung Leung

Zhiyi Huang

Qihang Huang

Paul Werstein

University of Otago

Data Race: Tame the Beast

Abstract:
This paper proposes a data race prevention scheme, which can eliminate data races in the View-Oriented Parallel Programming (VOPP) model. VOPP is a novel shared-memory data-centric parallel programming model, which uses views to bundle mutual exclusion with data access. We have implemented the data race prevention scheme with a memory protection mechanism. Experimental results show that the extra overhead of memory protection is trivial in our data race free applications. We also present a new VOPP implementation - Maotai 2.0, which has advanced features such as deadlock avoidance, producer/consumer view and system queues, apart from the data race prevention scheme. The performance of Maotai 2.0 is evaluated and compared with modern programming models such as OpenMP and Cilk.

OUCS-2008-03

Philip McLeod
University of Otago

Fast, Accurate Pitch Detection Tools for Music Analysis

Abstract:

Precise pitch is important to musicians. We created algorithms for real-time pitch detection that generalise well over a range of single ‘voiced’ musical instruments. A high pitch detection accuracy is achieved whilst maintaining a fast response using a special normalisation of the autocorrelation (SNAC) function and its windowed version, WSNAC. Incremental versions of these functions provide pitch values updated at every input sample. A robust octave detection is achieved through a modified cepstrum, utilising properties of human pitch perception and putting the pitch of the current frame within the context of its full note duration. The algorithms have been tested thoroughly both with synthetic waveforms and sounds from real instruments. A method for detecting note changes using only pitch is also presented.

Furthermore, we describe a real-time method to determine vibrato parameters - higher level information of pitch variations, including the envelopes of vibrato speed, height, phase and centre offset. Some novel ways of visualising the pitch and vibrato information are presented. Our project ‘Tartini’ provides music students, teachers, performers and researchers with new visual tools to help them learn their art, refine their technique and advance their fields.

OUCS-2008-02

Hans van Ditmarsch
University of Otago, New Zealand and IRIT, France

Andreas Herzig
IRIT, France

Tiago de Lima
Eindhoven University of Technology, the Netherlands

An optimal method for reasoning about actions

Abstract:
In this paper we propose a novel method for reasoning about actions and knowledge that has optimal computational complexity. In our approach, we use two different extensions of public announcement logic (PAL). The first, PALA, extends PAL with assignments, and the second, that we call PALAT, extends PAL with assignments and tests; both are equally expressive. First, we encode Scherl & Levesque's solution to the frame problem with knowledge into PALAT, and show that this is a polynomial transformation. Then, by extending Lutz' method for PAL satisfiability checking to PALA, we establish an optimal decision procedure for PALA. Our method runs in nondeterministic polynomial time for one agent, in polynomial space for multiple agents and in deterministic exponential time when common knowledge is involved.

OUCS-2008-01

J. Zhang, W. Chen, W. Zheng
Department of Computer Science, Tsinghua University, Beijing, China

Z. Huang, Q. Huang
Department of Computer Science, University of Otago

View-Oriented Parallel Programming on CMT processors

Abstract:
View-Oriented Parallel Programming (VOPP) is a novel parallel programming model which uses views for communication between multiple processes. With the introduction of views, mutual exclusion and shared data access are bundled together, which offers both convenience and high performance to parallel programming. This paper presents the performance results of VOPP on Chip-Multithreading processors, e.g. UltraSPARC T1. We have compared VOPP with MPI and OpenMP in terms of programmability and performance. An implementation of helper threaded prefetching for VOPP has also been discussed and evaluated.

OUCS-thesis2-2007

Nathan Rountree

Initialising Neural Networks with Prior Knowledge

A thesis submitted for the degree of Doctor of Philosophy at the University of Otago, Dunedin, New Zealand

Abstract:
This thesis explores the relationship between two classification models: decision trees and multilayer perceptrons.

Decision trees carve up databases into box-shaped regions, and make predictions based on the majority class in each box. They are quick to build and relatively easy to interpret. Multilayer perceptrons (MLPs) are often more accurate than decision trees, because they are able to use soft, curved, arbitrarily oriented decision boundaries. Unfortunately MLPs typically require a great deal of effort to determine a good number and arrangement of neural units, and then require many passes through the database to determine a good set of connection weights. The cost of creating and training an MLP is thus hundreds of times greater than the cost of creating a decision tree, for perhaps only a small gain in accuracy.

The following scheme is proposed for reducing the computational cost of creating and training MLPs. First, build and prune a decision tree to generate prior knowledge of the database. Then, use that knowledge to determine the initial architecture and connection weights of an MLP. Finally, use a training algorithm to refine the knowledge now embedded in the MLP. This scheme has two potential advantages: a suitable neural network architecture is determined very quickly, and training should require far fewer passes through the data.

In this thesis, new algorithms for initialising MLPs from decision trees are developed. The algorithms require just one traversal of a decision tree, and produce four-layer MLPs with the same number of hidden units as there are nodes in the tree. The resulting MLPs can be shown to reach a state more accurate than the decision trees that initialised them, in fewer training epochs than a standard MLP. Employing this approach typically results in MLPs that are just as accurate as standard MLPs, and an order of magnitude cheaper to train.

OUCS-thesis1-2007

Simon McCallum

Catastrophic Forgetting and the Pseudorehearsal Solution in Hopfield Networks

A thesis submitted for the degree of Doctor of Philosophy at the University of Otago, Dunedin, New Zealand - 29 June 2007

Abstract:
Most artificial neural networks suffer from the problem of catastrophic forgetting, where previously learnt information is suddenly and completely lost when new information is learnt. Memory in real neural systems does not appear to suffer from this unusual behaviour. In this thesis we discuss the problem of catastrophic forgetting in Hopfield networks, and investigate various potential solutions. We extend the pseudorehearsal solution of Robins (1995) enabling it to work in this attractor network, and compare the results with the unlearning procedure proposed by Crick and Mitchison (1983). We then explore a familiarity measure based on the energy profile of the learnt patterns. By using the ratio of high energy to low energy parts of the network we can robustly distinguish the learnt patterns from the large number of spurious “fantasy” patterns that are common in these networks. This energy ratio measure is then used to improve the pseudorehearsal solution so that it can store 0.3N patterns in the Hopfield network, significantly more than previous proposed solutions to catastrophic forgetting. Finally, we explore links between the mechanisms investigated in this thesis and the consolidation of newly learnt material during sleep.

OUCS-2007-01

K. Britz
School of Computing, University of South Africa, Pretoria

J. Heidema
Department of Mathematics, University of South Africa, Pretoria

W. Labuschagne
Department of Computer Science, University of Otago

ENTAILMENT, DUALITY, AND THE FORMS OF REASONING

Abstract:
We explore the notion of duality for defeasible entailment relations induced by preference orderings on states. We then show that such preferential entailment relations may be used to characterise Peircean inductive and abductive reasoning. Interpreting the preference relations as accessibility relations establishes modular Gödel-Löb logic as the modal logic of inductive and abductive reasoning.

OUCS-2006-12

Anthony Robins, Chris Gillum
Department of Computer Science, University of Otago

Rehearsal and stability profiles in Hopfield type networks

Abstract:
This document describes a preliminary investigation of rehearsal and stability profiles in Hopfield type networks. Section 1 contains basic descriptions of the network itself followed by Section 2 which shows the methods used to both create a new network and to remove it. Section 3 describes the training and cycling of the networks, Section 4 describes the utility functions associated with the rehearsal functions, while Section 5 details the four rehearsal methods employed and the results produced.

OUCS-2006-11

Hans van Ditmarsch
Department of Computer Science, University of Otago

Barteld Kooi
Department of Philosophy, University of Groningen

The logic of ontic and epistemic change

Abstract:
We propose an epistemic logic incorporating dynamic operators to describe information changing events, both informative actions, where agents become more informed about the non-changing state of the world, as ontic changes, wherein the world and the facts describing it change themselves as well. A complete axiomatisation is provided. There are some independent semantic results, for example that assignments in programs can be restricted to those to false or true only. We apply the logic to model systems for card deals and to model protocols.

OUCS-2006-10

NB: This report was updated 11-Oct-06

Simon McCallum
Department of Computer Science, University of Otago

Computer Science Graduate Shortage

Abstract:
There has been a sudden and dramatic drop in the numbers of students enrolling in ICT degrees in the last 5 years. At the same time there has been a strong increase in the number of people employed in ICT positions. This divergence in the supply and demand for programming staff, raises a serious concern over the number of well trained programmers that will be available for employment within New Zealand in the next 5 years. These trends are global and will impact on the New Zealand economy severely and will limit growth.

OUCS-2006-09

M.H. Albert
Department of Computer Science, University of Otago

Micah Coleman, Ryan Flynn
Department of Mathematics, University of Florida

Imre Leader
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge

Permutations Containing Many Patterns

Abstract:
It is shown that the maximum number of patterns that can occur in a permutation of length n is asymptotically 2ⁿ. This significantly improves a previous result of Coleman.

OUCS-2006-08

Zhiyi Huang
Department of Computer Science, University of Otago

View-Oriented Parallel Programming

Abstract:
Traditional parallel programming styles have many problems which hinder the development of parallel applications. The message passing style can be too complex for many programmers. While shared memory based parallel programming is relatively easy, it requires programmers to guarantee there is no data race in programs. Data race conditions are generally difficult to debug and difficult to prevent as well. The View-Oriented Parallel Programming (VOPP) is a novel shared-memory-based programming style. It removes the burden of checking data race conditions from the programmers. With the VOPP approach, shared data objects are divided into views according to the memory access pattern of the parallel algorithm. One advantage of VOPP is that programmers don't need to worry about mutual exclusion, such as locks, since mutual exclusion is automatically done by the underlying system when a view is accessed. By removing data races from programs, VOPP makes it easier to code and less difficult to debug programs. It also provides potential performance advantages on multi-core systems as well as cluster computers.

OUCS-2006-07

Hans van Ditmarsch
Department of Computer Science, University of Otago

Ji Ruan
Computer Science, University of Liverpool

What is my number? - A new epistemic riddle

Abstract:
A common theme in epistemic riddles is that announcements of ignorance may eventually result in knowledge. We present a fairly new epistemic riddle, including some variants that were partly accidentally designed due to a miscommunication between logic puzzle enthusiasts. The design was facilitated because such riddles can be specified, and fairly easily checked, in 'public announcement logic', a modal logic with both dynamic and epistemic operators; and because of the availability of epistemic model checking tools for the finetuning and verification of results. Logic puzzle design could benefit from similar future efforts.

OUCS-2006-06

Philippe Balbiani, Andreas Herzig, and Tiago De Lima
Institut de Recherche en Informatique de Toulouse (IRIT), Toulouse, France.

Hans van Ditmarsch
Department of Computer Science, University of Otago

What becomes true after arbitrary announcements

Abstract:
Public announcement logic is an extension of multi-agent epistemic logic with dynamic operators to model the informational consequences of announcements to the entire group of agents. We propose an extension of public announcement logic with a dynamic modal operator that expresses what is true after arbitrary announcements. Intuitively, [!] phi expresses that phi is true after an arbitrary announcement !psi. We show completeness for a Hilbert-style axiomatization of this logic, and also provide a labelled tableau-calculus.

OUCS-2006-05

M. H. Albert, M. D. Atkinson
Department of Computer Science, University of Otago

R. Brignall
School of Mathematics and Statistics, University of St Andrews

Permutation Classes of Polynomial Growth

Abstract:
A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterized as those permutations not involving a particular set of forbidden permutations. A simple collection of necessary and sufficient conditions on sets of forbidden permutations which ensure that the associated pattern class is of polynomial growth is determined. A catalogue all such sets of forbidden permutations having three or fewer elements is provided together with bounds on the degrees of the associated enumerating polynomials.

OUCS-2006-04

M. H. Albert, M. D. Atkinson, C. C. Handley
Department of Computer Science, University of Otago

R. E. L. Aldred, D. J. McCaughan
Department of Mathematics and Statistics,University of Otago

B. E. Sagan
Department of Mathematics, Michigan State University

Monotonic Sequence Games

Abstract:
In a monotonic sequence game, two players alternately choose elements of a sequence from some fixed ordered set. The game ends when the resulting sequence contains either an ascending subsequence of length a or a descending one of length d. We investigate the behaviour of this game when played on finite linear orders or the rational numbers and provide some general observations for play on arbitrary ordered sets.

OUCS-2006-03

30/8/2006: This paper was revised.

Important Note: This .pdf may be unreadable on your monitor - please save it and print it to read it.

Hans van Ditmarsch and Willem Labuschagne, Department of Computer Science, University of Otago

My beliefs about your beliefs - a case study in theory of mind and epistemic logic

Abstract:
We model three examples of beliefs that agents may have about other agents' beliefs, and provide motivation for this conceptualization from the theory of mind literature. We assume a modal logical framework for modelling degrees of belief by partially ordered preference relations. In this setting, we describe that agents believe that other agents do not distinguish among their beliefs ('no preferences'), that agents believe that the beliefs of other agents are in part as their own ('my preferences'), and the special case that agents believe that the beliefs of other agents are exactly as their own ('preference refinement'). This multi-agent belief interaction is frame characterizable. We provide examples for introspective agents. We investigate which of these forms of belief interaction are preserved under three common forms of belief revision.

OUCS-2006-02

Joost van Oijen, visiting student from the University of Twente

A model of the relationship between language and sensorimotor cognition

Abstract:
The goal of this report is to simulate how a child learns a language. First children learn single words; later they begin to associate events they see with sentences describing the events. They accomplish this with the help of a tutor, usually the parent. Here the relationship between the perception of an event and a sentence describing the event is investiated. Knott's hypothesis about event perception is used, resulting in a sensorimotor model where event perception is described as a sequence of sensorimotor items. The theory of Minimalism is used to map sentences onto an underlying syntactic structure. Knott's proposal is that there is a direct mapping of the sensorimotor items to items in the syntactic structure. The mapping is explored using neural networks.

OUCS-2006-01

Hans van Ditmarsch, Department of Computer Science, University of Otago
J. Ruan, Computer Science, University of Liverpool, United Kingdom
L.C. Verbrugge, Artificial Intelligence, University of Groningen, the Netherlands

Sum and Product in Dynamic Epistemic Logic

Abstract:
The Sum-and-Product riddle was first published in [Freudenthal,1969]. We provide an overview on the history of the dissemination of this riddle through the academic and puzzle-math community. This includes some references to precursors of the riddle, that were previously (as far as we know) unknown.

We then model the Sum-and-Product riddle in a modal logic called public announcement logic. This logic contains operators for knowledge, but also operators for the informational consequences of public announcements. The logic is interpreted on multi-agent Kripke models. The information in the riddle can be represented in the traditional way by number pairs, so that Sum knows their sum and Product their product, but also as an interpreted system, so that Sum and Product at least know their local state. We show that the different representations are isomorphic. We also provide characteristic formulas of the initial epistemic state of the riddle. Finally we analyze one of the announcements towards the solution of the riddle as a so-called unsuccessful update: a formula that become false because it is announced.

The riddle is then implemented and its solution verified in the epistemic model checker DEMO. This can be done, we think, surprisingly elegantly. The results are compared with other work in epistemic model checking.

OUCS-2005-10

Hans van Ditmarsch & Ji Ruan, Department of Computer Science, University of Otago
Rineke Verbrugge, University of Groningen, Netherlands

Model Checking Sum and Product

Abstract:
We model the well-known Sum-and-Product problem in a modal logic, and verify its solution in a model checker. The modal logic is public announcement logic. This logic contains operators for knowledge, but also for the informational consequences of public announcements. The logic is interpreted on multi-agent Kripke models.

The information in the riddle can be represented in the traditional way by number pairs, so that Sum knows their sum and Product their product, but also as an interpreted system, so that Sum and Product at least know their local state. We show that the different representations are isomorphic.

The riddle is then implemented and its solution verified in the epistemic model checker DEMO. This can be done, we think, surprisingly elegantly. It involves reformulations to facilitate the computation.

OUCS-2005-09

Maarten van der Veen, Jeroen van Dijk
Department of Computer Science, University of Otago (visiting students from the University
of Groningen)

Implementation of a model of the relation between language and sensorimotor cognition

Abstract:
This report describes the implementation of a model of sensorimotor experience and episodic memory, and an associated model of the sensorimotor grounding of syntactic representations, both developed by Alistair Knott. We begin by outlining the two models, and proposing refinements to the models in various places. We then describe implementations of each model, along with the results of various experiments to test their validity.

OUCS-2005-08

Michael H. Albert
Department of Computer Science, University of Otago

On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation

Abstract:
We consider the distribution of the length of the longest subsequence avoiding a given pattern in a random permutation of length n. The well-studied case of a longest increasing subsequence corresponds to avoiding the pattern 21. We show that there is some constant c such that the mean value of this length is asymptotic to twice the square root of c times n and that the distribution of the length is tightly concentrated around its mean. We observe some apparent connections between c and the Stanley-Wilf limit of the class of permutations avoiding the given pattern.

OUCS-2005-07

Hans van Ditmarsch
Department of Computer Science, University of Otago

Wiebe van der Hoek
Liverpool University

Ron van der Meyden
NICTA/UNSW, Sydney

Ji Ruan
China

Model Checking Russian Cards

Abstract:
We implement a specific protocol for bit exchange among card-playing agents in three different state-of-the-art epistemic model checkers and compare the results.

OUCS-2005-06

Edwin van der Ham
Visiting student, University of Twente

Diagnosing and responding to student errors in a dialogue-based computer-aided language-learning system

Abstract:
The task of a Computer Aided Language Learning (CALL) system is to assist students in learning a new language. This is a complex task which requires amongst other things error detection and error correction techniques to detect and respond to the students' mistakes. Te Kaitito is a dialogue-based CALL system, primarily designed to teach the Maori language to native speakers of English. This report describes a new module developed for this system that uses perturbation of the input sentences entered by the user to diagnose errors in these sentences. Perturbations which result in sentences which the system can parse and/or which are more plausible in the given context than the original sentence are identified as possible corrections of the user's sentence. The technique of perturbing input sentences is combined with other techniques to make it more efficient. The information gathered by the module is then used to give feedback which will give the student a better understanding of his error.

OUCS-2005-05

Michael H. Albert
Department of Computer Science, University of Otago

Steve Linton
School of Computer Science, University of St. Andrews

Nik Ruškuc
School of Mathematics and Statistics, University of St. Andrews

The Insertion Encoding of Permutations

Abstract:
We introduce the insertion encoding, an encoding of finite permutations. Classes of permutations whose insertion encodings form a regular language are characterized. Some necessary conditions are provided for a class of permutations to have insertion encodings that form a context free language. Applications of the insertion encoding to the evaluation of generating functions for classes of permutations, construction of polynomial time algorithms for enumerating such classes, and the illustration of bijective equivalence between classes are demonstrated.

OUCS-2005-04

M. H. Albert, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley
Department of Computer Science, University of Otago

R. E. L. Aldred, D. A. Holton, D. J. McCaughan
Department of Mathematics and Statistics, University of Otago

Sorting Classes

Abstract:
Weak and strong sorting classes are pattern-closed classes that are also closed downwards under the weak and strong orders on permutations. They are studied using partial orders that capture both the subpermutation order and the weak or strong order. In both cases they can be characterised by forbidden permutations in the appropriate order. The connection with the corresponding forbidden permutations in pattern-closed classes is explored. Enumerative results are found in both cases.

OUCS-2005-03

M.H. Albert
Department of Computer Science, University of Otago

M. Elder
School of Mathematics and Statistics, University of St. Andrews, St. Andrews, Scotland

A. Rechnitzer
Department of Mathematics and Statistics, University of Melbourne, Melbourne, Australia

P. Westcott
Melbourne, Australia

M. Zabrocki
Department of Mathematics and Statistics, York University, Toronto, Canada

On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia.

Abstract:
We construct a sequence of finite automata that accept subclasses of the class of 4231-avoiding permutations. We thereby show that the Wilf-Stanley limit for the class of 4231-avoiding permutations is bounded below by 9.35. This bound shows that this class has the largest such limit among all classes of permutations avoiding a single permutation of length 4 and refutes the conjecture that the Wilf-Stanley limit of a class of permutations avoiding a single permutation of length k cannot exceed the square of (k-1).

OUCS-2005-02

Nanda Slabbers
Affiliation: Department of Computer Science, University of Twente, the Netherlands
(Intern, Artificial Intelligence Group, Department of Computer Science, University of Otago)

A system for generating teaching initiatives in a computer-aided language learning dialogue

Abstract:
This document describes an extension made to a dialogue-based CALL system, to allow the system to take initiatives in the dialogue. The initiative module is triggered when the user passes the initiative to the system during the course of a dialogue. The system will then generate a set of "possible initiatives'' and decide which one is best based on a number of criteria.

The initiative module supports two different goals. The first one is the formal goal of generating an initiative which is appropriate in the context. Furthermore the dialogue system is used for second language learning and therefore the module also supports the substantive goal of teaching the student a number of syntactic constructions.

OUCS-2005-01

Note: this report will be made available later.

Alexis Angelidis
Department of Computer Science, University of Otago

Fabrice Neyret
Evasion-GRAVIR

Simulation of Smoke based on Vortex Filament Primitives

Abstract:
We describe a method that permits the high performance simulation of fluids phenomena such as smoke with a high level of control by an artist. Our key primitives are vortex filament and vortex ring: vorticity defines a flow as well as velocity does, and for numerous interesting flows such as smoke or explosions this information is very compact and tightly linked to the visual features of the fluid. We treat these vortices as 1D Lagrangian primitives (i.e. connected particles), which permits unbounded fluids and very accurate positioning of the features. The simulation of passive density particles for rendering is totally independent of the fluid animation itself. Thus, the animation can be efficiently simulated, edited and even stored, while the fluid resolution used for rendering can be arbitrarily high. We aim at plausible fluids rather than physically accurate. For efficiency and stability, we introduce a new formalization of the Biot-Savart law and a modified Biot-Savart kernel. Our model also introduces a hierarchical filament structure for animation LOD, turbulent noise, and an original scheme for density particles.

Stewart Fleming
Department of Computer Science, University of Otago

Biometric security: Concepts, Issues and Flaws

Abstract:
Information security is concerned with the assurance of confidentiality, integrity and availability of information in all forms. There are many tools and techniques that can support the management of information security and systems based on biometrics have evolved to support some aspects of information security. Biometric systems support the facets of identification/authorization, authentication and non-repudiation in information security.

Biometric systems have grown in popularity as a way to provide personal identification. Personal identification is crucially important in many applications and the upsurge in credit-card fraud and identity theft in recent years indicates that this is an issue of major concern in wider society. Individual passwords, PIN identification, cued keyword personal questions or even token-based arrangements all have deficiencies that restrict their applicability in a widely-networked society. The advantage claimed by biometric systems is that they can establish an unbreakable one-to-one correspondence between an individual and a piece of data.

The drawback with biometric systems is their perceived invasiveness and the general risks that can emerge when biometric data is not properly handled. There are good practices which, when followed, can provide the excellent match between data and identity that biometrics promise; if not followed, can lead to enormous risks to privacy for an individual.

Alexis Angelidis
Department of Computer Science, University of Otago

Hexanions: 6D Space for Twists

Abstract:
Some of the popular representations for the motion of a rigid object are 4x4 real matrices or combinations of vector and quaternion. A drawback of using 4x4 real matrices is their over-general purpose. A real matrix is capable of representing a far too rich set of transformations, for instance scaling and shear. Another drawback with matrices is the accumulation of numerical errors, which impose the need to renormalize the matrix once in a while. On the other hand, a drawback of using a combination of vector and quaternion is the separation of the motion in two components that have to be handled individually. This component separation can make implementation on computing devices unclear or unnecessarily long. While there are surely other alternatives for representing numerically rigid motion, we propose here a new representation called hexanion. A hexanion is a compact and natural representation of the rigid transformations: translations, rotations and twists. The number of dimensions of hexanion space is six, which is also the degrees of freedom of rigid transformations.

Michael H. Albert
Department of Computer Science, University of Otago

Nik Ruškuc
School of Mathematics and Statistics, University of St. Andrews

Steve Linton
School of Computer Science, University of St. Andrews

On the Permutational Power of Token Passing Networks

Abstract:
A token passing network is a directed graph with one or more specified input vertices and one or more specified output vertices. A vertex of the graph may be occupied by at most one token, and tokens are passed through the graph. The reorderings of tokens that can arise as a result of this process are called the language of the token passing network. It was known that these languages correspond through a natural encoding to certain regular languages. We show that the collection of such languages is relatively restricted, in particular that only finitely many occur over each fixed alphabet.

Hans van Ditmarsch
Department of Computer Science, University of Otago

Wiebe van der Hoek
Department of Computer Science, University of Liverpool

Barteld Kooi
Department of Philosophy, University of Groningen

Playing cards with Hintikka

Abstract:
This contribution is a gentle introduction to so-called dynamic epistemic logics, that can describe how agents change their knowledge and beliefs. We start with a very concise introduction in epistemic logic, by the example of one, two and finally three players holding cards; and, mainly for the purpose of motivating the dynamics, we also very summarily introduce the concepts of general and common knowledge. We then pay ample attention to the logic of public announcements, wherein agents change their knowledge as the result of, indeed, public announcements. One crucial topic in that setting is that of unsuccessful updates: formulas that become false when announced. The Moore-sentences that were already extensively discussed at the conception of the area of epistemic logic in Hintikka's 'Knowledge and Belief' (1962) give rise to such unsuccessful updates. Our closing observations are on recent developments that link the 'standard' topic of (theory) belief revision to the dynamic epistemic logics introduced here.

Stewart Fleming and Sonil Gohil
Department of Computer Science, University of Otago

Further Reflection on Homage Anonymous Group Authentication Protocol

Abstract:
Anonymous group authentication provides an individual with the ability to prove membership of a group without revealing their identity. The Homage protocol proposed by Handley provides an efficient mechanism for anonymous group authentication. Attacks have been proposed on this protocol which suggest weaknesses in its security. We revisit the original protocol to investigate the nature of the proposed attacks and we propose modifications to the protocol that address them while maintaining the spirit of the original. We then go on to address a remaining weakness in the Homage protocol by considering how non-transferability might be accomplished through the use of biometrics, while preserving anonymity.

Sonil Gohil, Stewart Fleming
Department of Computer Science, University of Otago

Attacks on Homage Anonymous Group Authentication Protocol

Abstract:
The Homage anonymous group authentication was originally proposed by Handley. This report describes an implementation of the attacks on the protocol proposed by Jaulmes & Poupard. All of the proposed attacks are shown to be valid, given the assumptions made by the authors.

We propose slight modifications to the original protocol that take all of Handley’s assertions into account and eliminate the ability of the authority to cheat. We believe that this secures the basic protocol and we report on an implementation that demonstrates the protocol in action.

As an extension to the original protocol, we propose a number of options to incorporate biometric authentication into Homage without compromising anonymity and preserving efficiency. We critique the various options, showing which are and are not compatible with the basic objectives of Homage.

This report is an edited version of the original report submitted by Sonil Gohil (see separate Technical Report) to summarize the work done during summer bursary project in December 2003-January 2004. It incorporates the additional work that was done in refactoring the implementation and critiquing the biometric options that was done in preparation for publication in Financial Cryptography conference in 2005 (see Report oucs-2004-17 above).

Stewart T. Fleming
Department of Computer Science, University of Otago

Talking Past Each Other – Student And Staff Reflection In Undergraduate Software Projects

Abstract:
Group projects are an important part of Software Engineering education. However, conflicts that arise from group work can affect overall class learning and performance. It can be difficult for teachers to fully understand the social context of these issues.

We explore the nature of self-, peer- and staff-reflection to identify and mediate issues within a class. We have used a protocol that encourages reflection to explore conflicts that arise from group work in a Software Engineering paper.

We have found a way to explore and mediate student impressions and expectations and to identify conflicts with staff expectations and course objectives. We present a lightweight and flexible approach for such investigations.

OUCS-2004-14

Note: this report was updated 29/9/2004

Stewart T. Fleming
Department of Computer Science, University of Otago

Open Source Intellectual Property Rights - Issues and Trends

Abstract:
The Open Source Software movement exists as a loose collection of individuals, organizations and philosophies roughly grouped under the intent of making software source code as widely available as possible. While the movement as such can trace its roots back over 30 years to the development of academic software, the Internet and World Wide Web etc, the popularization of the movement grew significantly from the mid-80’s.

The Free Software movement takes open source one step further, asserting that, in addition to freedom of availability through publication, there should be legally-enforceable rights to ensure that it stays freely available and that such protections should extend to derived works.

The impetus of both movements has resulted in the widespread distribution of a significant amount of free software, particularly GNU/Linux and Apache Web server. The nature of this software and the scale of installation appears to be an emerging concern for “closed” software vendors. At this time, we are seeing the emergence of legal challenges to the open source movement and a clash with the changing landscape of intellectual property and copyright protection.

There is spirited debate within and between both movements regarding the nature of open source software and the concerns over the extent to which software should remain free or become proprietary. This article concentrates on the issues directly relating to open source licenses and their impact on copyright and intellectual property rights and the legal risks that may arise. For more general reference, the reader is directed to the Web sites of the Free Software Foundation (http://www.fsf.org), Open Source Initiative (http://www.opensource.org) and the excellent bibliography maintained by Stefan Koch (http://wwwai.wu-wien.ac.at/~koch/forschung/sw-eng/oss_list.html)

OUCS-2004-13

Note: this report was updated 29/9/2004

Stewart T. Fleming
Department of Computer Science, University of Otago

Virtual Learning Communities - Supporting Learning through Interaction

Abstract:
The synthesis of global communication networks available at low cost, enormous growth in popular uptake of personal computers and communication devices and the need for more sophisticated discussion of complex issues are continually pushing the boundaries of our expertise. Virtual learning communities (VLCs) are emerging constructs that depend on the notion of socially constructed learning to provide a focus for informed discussion and lifelong learning. They make use of increasingly sophisticated technologies to establish, support and maintain communities – collections of individuals with a common purpose, acting in social settings, geographically disparate.

Virtual learning communities are defined as groups of individuals that come together to study some area of common interest. They are virtual communities in the sense that they depend on a variety of Information and Communication Technologies (ICT) to coordinate their activities. They share many characteristics with virtual communities of practice. The nature of the relationships between these three constructs is explored below. The role of ICT and multimedia in supporting VLCs is reviewed. This article concludes with a summary of the challenges facing both organizations in stimulating the presence and growth of VLCs and the individuals who participate in such communities.

M. H. Albert, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley
Department of Computer Science, University of Otago

R. E. L. Aldred, D. A. Holton, D. J. McCaughan
Department of Mathematics and Statistics, University of Otago

Compositions of pattern restricted sets of permutations

Abstract:
The composition of two pattern restricted classes X,Y is the set of all permutation products θφ where θ ε X, φ ε Y. This set is also defined by pattern restrictions. Examples are given where this set of restrictions is finite and where it is infinite. The composition operation is studied in terms of machines that sort and generate permutations. The theory is then applied to a multistage sorting network where each stage can exchange any number of adjacent disjoint pairs.

M. H. Albert
Department of Computer Science, University of Otago

S. Linton
Centre for Interdisciplinary Research in Computational Algebra, University of St. Andrews

A Practical Algorithm for Reducing Non-deterministic Finite
State Automata

Hans van Ditmarsch
Department of Computer Science, University of Otago

Barteld Kooi
Department of Philosophy, University of Groningen

The Secret of My Success

Z. Huang, P. Werstein
Department of Computer Science, University of Otago

M. Purvis
Department of Information Science, University of Otago

View-Oriented Parallel Programming and View-based Consistency

M. H. Albert
Department of Computer Science, University of Otago

M.S. Paterson
Department of Computer Science, University of Warwick

Bounds For The Growth Rate Of Meander Numbers

Hans van Ditmarsch
Department of Computer Science, University of Otago

The case of the hidden hand

Maarten van Schagen
Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, the Netherlands
(Intern, Artificial Intelligence Group, Department of Computer Science, University of Otago)

Tauira: A bilingual dialogue-based lexical acquisition system

A Knott, I Bayard and P Vlugter
Department of Computer Science, University of Otago

Multi-agent human-machine dialogue: issues in dialogue management and referring expression semantics

OUCS-2004-04

Note: this paper was updated 29/9/04

Lorene Earnshaw, Stewart Fleming, Alistair Knott
Department of Computer Science, University of Otago
Victoria Weatherall
School of Maori, Pacific and Indigenous Studies, University of Otago

Analysis Of Errors Made By Learners Of Maori In An Introductory University Course

Z. Huang
Department of Computer Science, University of Otago
C. Sun
School of Computing & Information Technology
Griffith University, Brisbane, Australia
S. Cranefield, and M. Purvis
Department of Information Science, University of Otago

A View-based Consistency Model based on Transparent Data Selection in Distributed Shared Memory

Logic and game theory of Pit

Spherical Springs

Simple permutations and pattern restricted permutations

OUCS-2003-07

Note: Report updated 15/3/04

Proceedings of the 2004 annual conference of the Australasian Association for Logic

OUCS-2003-06

Note: Report and Status updated 15/3/04

R.E.L. Aldred
Department of Mathematics and Statistics, University of Otago

Safe communication for card players by combinatorial designs for two-step protocols

Abstract:

Two parties A and B select a cards and b cards from a known deck and a third party C receives the remaining c cards. We consider methods whereby A can, in a single message, publicly inform B of her hand without C learning any card held by A or by B. Conditions on a; b; c are given for the existence of an appropriate message.

OUCS-2003-05

Note: Status updated 15/3/04

M.Klazar
Charles University, Prague, Czech Republic

The enumeration of simple permutations

Abstract:

A simple permutation is one which maps no proper non-singleton interval onto an interval. We consider the enumeration of simple permutations from several aspects. Our results include a straightforward relationship between the ordinary generating function for simple permutations and that for all permutations, that the coefficients of this series are not P-recursive, an asymptotic expansion for these coefficients, and a number of congruence results.

Grounding syntactic representations in an architecture for sensorimotor control

Abstract:

The aim of this paper is to suggest a way of characterising the syntactic structure of a sentence as a description or trace of a sensorimotor process. My starting point is the idea (see also Hurford, 2003; Jackendoff, 2002) that the logical form of a sentence should be thought of not as a direct representation of the world, but rather as an evocation of a cognitive process which interfaces with the world via various perceptual and motor mechanisms. I will argue, departing from Hurford and Jackendoff, that the structure of this evoked cognitive process has extensive reflexes in the syntax of sentences as well as in their semantics.

Marie-Paule Cani
GRAVIR-IMAG

Modeling by Deformation Using Swept User-Defined Tools

Abstract:

We present a new class of space deformations suitable for interactive virtual sculpture. The artist describes a basic deformation as a path through which a tool is moved. Our tools are simply shapes, subsets of 3D space. So we can use shapes already created as customized tools to make more complex shapes or to simplify the modeling process. When a tool is moved it causes a deformation of the working shape along the path of the tool. This is in accordance with a clay modeling metaphor and easy to understand and predict. More complicated deformations are achieved by using several tools simultaneously in the same region. It is desirable that deformations for modeling are 'foldover-free', that is parts of deformed space cannot overlap so that the deformations are reversible. There are good intuitive reasons to believe that our deformations are foldover-free but we have not yet completed a proof. We have an efficient formulation for a single tool following a simple path (translation, scaling or rotation) and we can demonstrate the effects of multiple tools used simultaneously. The prototype implementation described has been used to create a variety of models quickly and conveniently.

Proceedings, Permutation Patterns 2003

Abstract:

PP2003 was the first conference devoted exclusively to the study of permutation patterns and related results. These proceedings are intended as a set of abstracts and extended abstracts. The formatting of some of the submissions has been changed slightly to provide a (somewhat) uniform style. Many of the papers (and others) will appear as full versions in the special issue of the Electronic Journal of Combinatorics on Permutation Patterns.

W. van der Hoek
Department of Computer Science, University of Liverpool

B.P. Kooi
Department of Computer Science, Groningen

Concurrent dynamic epistemic logic

Abstract:

For an abstract, see the abstract for OUCS-2002-09. The underlying report is a (40 pages) book chapter, the results of which are condensed into the (8 pages) conference proceedings article that will be presented at AAMAS 2003 Melbourne and that is listed as OUCS-2002-09. The last is focussed on multiagent system applications and the underlying on the logical foundations of the proposed formalism.

OUCS-2002-12

Lindsay I Smith
Department of Computer Science, University of Otago

A tutorial on Principal Components Analysis

Abstract:
This tutorial is designed to give the reader an understanding of Principal Components Analysis (PCA). PCA is a useful statistical technique that has found application in fields such as face recognition and image compression, and is a common technique for finding patterns in data of high dimension.

Before getting to a description of PCA, this tutorial first introduces mathematical concepts that will be used in PCA. It covers standard deviation, covariance, eigenvectors and eigenvalues. This background knowledge is meant to make the PCA section very straightforward, but can be skipped if the concepts are already familiar.

There are examples all the way through this tutorial that are meant to illustrate the concepts being discussed. If further information is required, the mathematics textbook 'Elementary Linear Algebra 5e' by Howard Anton, Publisher John Wiley & Sons Inc, ISBN 0-471-85223-6 is a good source of information regarding the mathematical background.

The fine structure of 321 avoiding permutations

Abstract:

Bivariate generating functions for various subsets of the class of permutations containing no descending sequence of length three or more are determined. The notion of absolute indecomposability of a permutation is introduced, and used in enumerating permutations which have a block structure avoiding 321, and whose blocks also have such structure (recursively). Generalizations of these results are discussed.

R.E.L. Aldred, D.A. Holton
Department of Mathematics and Statistics, University of Otago

Restricted permutations and queue jumping

Abstract:

A connection between permutations that avoid 4231 and a certain queueing discipline is established. It is proved that a more restrictive queueing discipline corresponds to avoiding both 4231 and 42513, and enumeration results for such permutations are given.

W. van der Hoek
Department of Computer Science, University of Liverpool

B.P. Kooi
Department of Computer Science, University of Groningen

Concurrent dynamic epistemic logic for MAS

Abstract:

When giving an analysis of knowledge in multiagent systems, one needs a framework in which higher-order information and its dynamics can both be represented. A recent tradition starting in original work by Plaza treats all of knowledge, higher-order knowledge, and its dynamics on the same foot. Our work is in that tradition. It also fits in approaches that not only dynamize the epistemics, but also epistemize the dynamics: the actions that (groups of) agents perform are epistemic actions. Different agents may have different information about which action is taking place, including higher-order information. We demonstrate that such information changes require subtle descriptions. The contribution of our paper is that it provides a complete axiomatization for an action language of van Ditmarsch, where an action is interpreted as a relation between states and sets of states. The applicability of the framework is found in every context where multiagent strategic decision making is at stake, and already demonstrated in game-like scenarios such as Cluedo and card games.

The Russian cards problem: a case study in cryptography with public announcements

Abstract:

Suppose we have a stack of cards that is divided over some players. It may be possible to communicate your hand of cards to another player by public announcements, without yet another player learning any of your cards. A solution to this problem consists of some sequence of announcements and is called an exchange. It is called a direct exchange if it consists of (the minimum of) two announcements only. The announcements in an exchange have a special form: they are safe communications, an interesting new form of update. Certain unsafe communications turn out to be unsuccessful updates. A communication is a public announcement that is sknown to be true. Each communication may be about a set of alternative card deals only, and even about a set of alternatives to the communicating player's own hand only. There are 102 direct exchanges for a deal of seven cards where the two players holding three cards communicate their hands to each other. Our work can be used to design cryptographic protocols for 'perfect logicians' where secrets are not just computationally unfeasible to uncover but cannot be uncovered at all.

Het zeven-kaartenprobleem: kennislogica en multi-agentsystemen (The seven cards problem: epistemic logic and multiagent systems)

Abstract:

This is a Dutch-language publication on the 'seven cards problem', meaning: "Given seven all different cards, two players each draw three cards and a third player gets the remaining card. How can the players with three cards communicate to each other their hands, without the third player learning any of their cards?"

Sorting with a forklift

Abstract:

A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or dually, which permutations of a fixed input stream can be produced using a single forkstack. An algorithm is given to solve the sorting problem and the minimal unsortable sequences are found. The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time. In this context we also establish how to enumerate the collection of sortable sequences. Note: Now published in the Electronic Journal of Combinatoricshttp://www.combinatorics.org/Volume_9/v9i2toc.html

T. Caelli
Department of Computer Science, University of Alberta

Diagnostic Tools for Evaluating HMM Components

Abstract:

Although there are known algorithms for predicting observation and state sequences from HMM models there is little discussion on how to determine the contributions of the different types of HMM parameters to such predictions and consequently, temporal pattern recognition. In this note we discuss and compare a number of objective measures that provide insight into HMM performance in these terms.

N. Ruskuc
School of Mathematics and Statistics, University of St Andrews

Regular closed sets of permutations

Abstract:

Machines whose main purpose is to permute and sort data are studied. The sets of permutations that can arise are analysed by means of finite automata and avoided pattern techniques. Conditions are given for these sets being enumerated by rational generating functions.

H.P. van Ditmarsch
Epistemic actions and minimal models

Epistemic actions and minimal models

Abstract:

This paper is about the dynamics of epistemic models, i.e. multimodal S5 models. We investigate the effect of certain epistemic actions on such models, with special interest for minimality of the resulting models and the stream of information between groups of agents. Our choice of models and actions is inspired by epistemic states and moves that occur in knowledge games like Cluedo. We focus on intrinsic models M = <W,R,V>, where worlds w,v in W are structured objects, carrying enough information to define pairs (w,v) in accessibility relation R, and valuation Vw, in terms of w and v. Our main result is the reduction of epistemic models, resulting from epistemic actions, to minimal models (with respect to bisimulation). This proceeds in three steps: the first step corresponds with abstraction from the order of actions, the second step with downward transfer between groups of agents, and the third step with upward knowledge transfer between groups of agents.

Integer root finding, a functional perspective

Abstract:

We consider the problem of finding integer parts of roots to equations in a functional context. Standard techniques from numerical methods are extended to this case, providing both good performance, and guarantees of correctness. From an educational standpoint, the clear connection between the methods for finding roots and the functional code makes it easier to understand how different methods work, and to compare their relative effectiveness.

Keeping secrets with public communication

Abstract:

Is it possible to communicate your hand of cards to another player without yet another player learning any of your cards? Detailed description of the updates needed to solve this problem reveals an interesting form of update named a 'safe communication'. This in itself may be considered of interest to the research community. We solve a specific cards problem by giving sequences of such safe communications. For arbitrary deals we have few results yet, also this is more of combinatorial than of logical interest. References and background have been largely deleted from this extended abstract. Note that we assume faultless communication: this contribution is not in the area of transmission protocols, but in the area of communication protocols, as used in cryptography.

Reflections on 'The Importance of Being Formal'

Abstract:

In a 2001 issue of the Mathematical Intelligencer the following problem was discussed by Yuri and Konstantin Makarychev: 'From a pack of seven different cards, two players each draw three cards and the third player gets the remaining card. How can the players with three cards openly communicate each other all their cards without the third player learning from any of their cards who holds it?' The authors present a good and a bad solution for the problem and give a procedural requirement for a good solution. I had been working on the same problem. I was startled to discover that my wording of it was similarly prone to bad solutions. After consideration of the Mathematical Intelligencer article, and more in accordance with an epistemic logical approach, I suggest a different perspective: what a good solution is, can also be defined using 'common knowledge'. All relevant notions have a precise interpretation in relational structures. Further, I suggest a more interesting example of a 'bad solution'. Finally, I present some rather different good solutions.

A Preferential Semantics for Epistemic Logic

Abstract:

The development of agent communication languages casts a spotlight on epistemic logic and the enrichment of epistemic languages by additional operators, e.g. deontic operators or operators representing speech acts. In this paper we focus on two limitations of classical epistemic logic. The standard possible worlds semantics allows one to model either the knowledge or the beliefs of an agent, but it is not so easy to model both in a manner compatible with the intuition that knowledge shares the same 'dimension' as belief. Furthermore, the distinction between knowledge and belief is intimately tied up with defeasibility and non-monotonicity, which in turn (via total preorders) is connected with epistemic entrenchment. We therefore introduce a generalisation of the possible worlds semantics which not only accommodates knowledge and belief simultaneously but admits a hierarchy of belief operators reflecting different levels of entrenchment.

D. A. Holton
Department of Mathematics and Statistics, University of Otago

W. Stromquist
Berwyn, Pennsylvania, USA

On packing densities of permutations

Abstract:

The density of a permutation pattern p in a permutation s is the proportion of subsequences of s of length |p| that are isomorphic to p . The maximal value of the density is found for several patterns p, and asymptotic upper and lower bounds for the maximal density are found in several other cases. The results are generalised to sets of patterns and the maximum density is found for all sets of length 3 patterns.

Identifying the Danger Zones: Predictors of Success and Failure in a CS1 Course

Abstract:

We present the results of a survey which focuses on the backgrounds and expectations of a group of CS1 students in the first weeks of semester. When comparing their survey answers to their final grades on the course, we saw some surprising things: the group which indicated an intention to continue in computer science did no better than any other, and the strongest single indicator of success seems to be "expecting to get an A from the course." In order to see if there were any particular combinations of answers that indicated success or failure, we ran a decision-tree classifier over the survey data. This resulted in the identification of differing "danger zones" for each year of study, in which we observed about twice the expected proportion of failing students.

My program is correct but it doesn't run: A review of novice programming and a study of an introductory programming paper

Abstract:

In this paper we review the literature relating to the psychological / educational study of programming. We identify general trends comparing novice and expert programmers, programming knowledge and strategies, program generation and comprehension, and objectoriented vs. procedural programming. Our main focus is on novice programming, characteristic novice behaviour, and topics relating to novice teaching and learning. In the context of this review we briefly describe our own introductory programming paper, COMP103, and note ways in which it addresses key issues relating to programming strategies and mental models of programs. We present data regarding the kinds of problems that students meet while writing their own programs in laboratory sessions. These confirm and extend results noted in the literature. Most novice problems relate to algorithmic complexity in certain language features and in basic program design. A key issue which emerges, but has not previously been well addressed, is the distinction between effective and ineffective novices. What characterizes effective novices? Is it possible to turn ineffective novices into effective ones? We explore these topics and suggest a framework for organizing the knowledge, strategies and models that are involved in programming so as to help diagnose and assist novices.

M. M. Murphy, N. Ruskuc
School of Mathematics and Statistics, University of St Andrews, UK

Partially well-ordered closed sets of permutations

Abstract:

It is known that the "pattern containment" order on permutations is not a partial well-order. Nevertheless, many naturally defned sub-sets of permutations are partially well-ordered, in which case they have a strong finite basis property. Several classes are proved to be partially well-ordered under pattern containment. Conversely, a number of new antichains are exhibited that give some insight as to where the boundary between partially well-ordered and not partially well-ordered classes lies.

R.E.L. Aldred, D.A. Holton
Department of Computer Science, University of Otago

Algorithms for pattern involvement in permutations

Abstract:

We consider the problem of developing algorithms for the recognition of a fixed pattern within a permutation. These methods are based upon using a carefully chosen chain or tree of subpatterns to build up the entire pattern. Generally, large improvements over brute force search can be obtained. Even using on-line versions of these methods provides such improvements, though these are often not as great as for the full method. Furthermore, by using carefully chosen data structures to fine tune the methods, we establish that any pattern of length 4 can be detected in O(n log n) time. We also improve the complexity bound for detection of a separable pattern from O(n6) to O(n5log n).

Descriptions of game actions

Abstract:

To describe simultaneous knowledge updates for different subgroups we propose an epistemic language with dynamic operators for actions. The language is interpreted on equivalence states (S5 states). The actions are interpreted as state transformers. Two crucial action constructors are learningand local choice. Learning is the dynamic equivalent of common knowledge. Local choice aids in constraining the interpretation of an action to a functional interpretation (state transformer). Bisimilarity is preserved under execution of actions. The language is applied to describe various actions in card games.

OUCS-2001-02

The description of game actions in Cluedo

Abstract:

Game actions in the well-known murder game Cluedo involve interactions of different subgroups of players, that result in complex knowledge changes. We introduce a dynamic epistemic language to describe actions in Cluedo in formal detail. This provides us with a precise description of Cluedo strategies. Optimal strategies are not yet known.

OUCS-2001-01

Note: published and no longer available here.

A Job Brokering Shell for Interactive Single System Image Support

Abstract:

When users interact with computers, programs are run locally on the machine, and display on the local machine. Single System Image (SSI) is about taking a cluster of computers, and making them appear and behave as one system. SSI systems are typically non--interactive, batch systems. The Job Brokering Shell is a SSI model for running interactive processes on worker nodes, and having them appear to be running on the clusters gateway. The assumed environment is one of a gateway into a computer science student laboratory, where students can log in remotely to the gateway, and their programs run on the interior laboratory workstations.

(This report has been published in Proceedings of the Third International Conference on Parallel and Distributed Computing, Applications and Technologies (Editors S. Horiguchi and H. Shen), A&I Ltd, pp212-217, Kanazawa, September 2002. )