Student research opportunities

Eating, or Computation with Infinite Data

Project Code: CECS_933

This project is available at the following levels:
CS single semester, Honours, Summer Scholar, Masters, PhD

Keywords:

Infinite Data, Coinduction

Supervisor:

Dr Dirk Pattinson

Outline:

The term "eating" is a colloquial form to refer to functions that process infinite data streams. Such data streams arise in various areas: they could be the decimal expansions of real numbers, or the sequence of signals sent through a communication channel. Processing infinite streams then implements a function that takes one (or more) streams as an input, and produces another (infinite) stream as output. Clearly we have to ensure that streams flow (i.e. the output stream does not terminate), and we have to do this in a computational way. For streams, this is relatively well understood. However there's more to life than just streams: it is easy to see that a stream processing function can itself be represented as an infinite tree, so that the processing of stream processing functions (or higher order function on streams) again is an instance of computation over infinite data types. Interesting questions in that area concern the computability of (higher-order) stream processors, the complexity of these operations, and applications: how can one define a (higher order) stream processing function that represents intergration?

Goals of this project

The project can be developed into various different ways. Interesting questions in that area concern the computability of (higher-order) stream processors, the complexity of these operations, and applications: how can one define a (higher order) stream processing function that represents intergration?

Requirements/Prerequisites

Keen interest in theoretical aspects of computing and good mathematical ability. This project is not directly related to a course, but the ability to master topics discussed in the Theory of Computation Module would go a long way.

Student Gain

Familiarisation with techniques (mostly co-induction) to deal with infinite data, exposure to state-of-the art research.

Background Literature

An abstract and algebraic characterisation of stream processing functions is given in the paper

Representations of stream processors using nested fixed points (with Peter Hancock and Neil Ghani)

available at

http://arxiv.org/pdf/0905.4813v2

Contact: