The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

LAA

Seminar

On the complexity of infinite computations

Niwinski, D (Warsaw)
Thursday 22 June 2006, 11:00-12:00

Seminar Room 1, Newton Institute

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.

Presentation

[pdf ]

Back to top ∧