Midlands Logic Seminar 2012: Session 10, Thursday 15th March

3.30pm Study group session on Arithmetic and Complexity Theory

Mike Cox will talk about the linear time hierarchy. (The second of two talks.)

4.45pm Research Seminar ("Networks of finite state machines") Richard Kaye and Alain Hurst.

This concerns some particularly interesting PSPACE problems. In particular the problem of what one can say about networks in which all nodes are (copies of) the very simplest 2-state Moore machine. The basic problem asks if some reasonable questions concerning networks of these automata are PSPACE complete. The results we have are that (1) for a rather mild extension of the class of automata, the questions are indeed PSPACE complete, but (2) that this extension is a proper extension. The problem seems combinatorial (perhaps the most important part of it concerns digraphs in which all vertices have out-valency 2 and arbitrary in-valency, rather than the automata) and entertaining but nevertheless somewhat frustrating. (Maybe someone in the audience can spot something I've missed:)


Midlands Logic Seminar 2012