Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Damian Niwinski

LFCS Seminar: Damian Niwinski

— filed under:

Complexity of infinite tree languages -- when automata meet topology

  • LFCS Seminar
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

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 (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.

Document Actions