LFCS Seminar: Damian Niwinski
Complexity of infinite tree languages  when automata meet topology
What 


When 
Nov 16, 2010 from 04:00 PM to 05:00 PM 
Where  IF 4.31+4.33, Informatics Forum 
Add event to calendar 
vCal iCal 
Damian Niwinski from University of Warsaw
Complexity of infinite tree languages  when automata meet topology
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 (nondeterminism, 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 automatatheoretic nonseparability 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 coBü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.