Antonio Casares (RPTU, University of Kaiserslautern-Landau) will give the following talk on Thursday March 12, 3pm in Aurigny (room D165).

Layered automata: A canonical model of automata over infinite words

Contrary to the case of automata over finite words, omega-regular languages do not admit unique, minimal deterministic automata. Yet, not all hope is lost! In this talk, I will introduce layered automata, a formalism capturing a subclass of alternating parity automata, extending deterministic ones.

We show:

(1) Each omega-regular language is recognised by a unique minimal layered automaton, admitting a congruence-based description.
(2) This minimal automaton is computable in polynomial time from a given layered automaton.
(3) All layered automata are history-deterministic and 0-1 probabilistic. Moreover, emptiness and language-inclusion can be checked in polynomial time.

This is a joint work with Christof Löding and Igor Walukiewicz.