Student research opportunities
Coalgebraic Automata Theory
Project Code: CECS_932
This project is available at the following levels:
CS single semester, Honours, Summer Scholar, Masters, PhD
Keywords:
Finite Automata, Minimisation, Bryzowski Derivative, Coalgebra
Supervisor:
Dr Dirk PattinsonOutline:
Finite Automata have been studies for decades and are now firmly established as a cornerstone of computer science theory. Recently, a new perspective on finite automata has emerged: Automata as Coalgebras. This presents an algebraic (as opposed to operational) perspective and enables elegant treatments of minimisation, composition, determinisation and others which is applicable not only to finite automata in the standard sense, but moreover to generalisations involving, e.g. probabilities, weights or input/output behaviour.
Goals of this project
This project can be developed into several directions. Possible goals are to investigate determinisation in the coalgebraic context, to generalise the Bryzowski-derivative to more general forms of automata or a generalisation of the Myhill-Nerode or Kleene Theorem. The more adventurous may even consider automata on infinite words! Another avenue for this project may be a compositional implementation that applies coalgebraic methods uniformly to a large class of automata.
Requirements/Prerequisites
Good knowledge of automata theory as provided e.g. in the Theory of Computation module.
Student Gain
Exposure to advanced automata theory, possibly implementation experience, exposure to current research.
Background Literature
A basic introduction to the field of coalgebraic methods is the tutorial by Jacobs and Rutten:
A Tutorial on Coalgebras and Coinduction
available at http://www.cs.ru.nl/~bart/PAPERS/JR.pdf.
