skip to content

On the complexity of infinite computations

Thursday 22nd June 2006 - 11:00 to 12:00
INI Seminar Room 1

Finite-state automata constitute the very basic level in classical complexity theory. In contrast, when applied to infinite words and trees, they reveal a remarkable definability power, going beyond the Borel hierarchy. Still, some good properties of finite automata remain, like decidability of normal forms.

The talk will compare various complexity hierarchies with the emphasis on decidability questions, and present some recent results obtained by the author in collaboration with Igor Walukiewicz and Filip Murlak.

For deterministic automata on infinite trees, the situation is by now clarified; both the automata-index hierarchy and the Wadge hierarchy are decidable. In contrast, the non-deterministic case challenges for new techniques and ideas.

We will present some modest step in this direction, showing that the so-called game languages (essentially non-deterministic) form a hierarchy w.r.t. the Wadge reducibility.

Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons