An Isaac Newton Institute Programme

Logic and Algorithms

On the complexity of infinite computations

22nd June 2006

Author: Damian Niwinski (Warsaw)

Abstract

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.