University of Warsaw
4pm Tuesday, 16th November, 2010
Room 4.31/33, Informatics Forum
Automata on infinite trees, originally introduced by M.O. Rabin as a tool in his landmark proof of decidability of the theory S2S (1969), have since then been an object of continuous investigations. They can be used to model reactive systems, and the features of automata (non-determinism, alternation of positive and negative events) are relevant for the computational complexity of the respective problems in system verification.
On the other hand, infinite trees can be viewed as elements of the Cantor discontinuum (or as real numbers). Perhaps not surprisingly, the complexity induced by automata often interplays with the complexity induced by the Borel measurability etc. We show in particular how a topological argument can yield an automata-theoretic non-separability result of the form: two ``difficult'' disjoint sets cannot, in general, be separated by a ``simple'' set. Our example is based on parity games and the level of difficulty in consideration is the co-Büchi level of the alternating index hierarchy. The analogous problem for the whole hierarchy is a subject of current investigations.
The talk is based on results obtained in collaboration with Andre Arnold, Szczepan Hummel, and Henryk Michalewski.