Mike Cox will talk about the linear time hierarchy. (The second of two talks.)
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:)