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 to capture a subclass of alternating parity automata, extending deterministic ones. We show:
(1) All layered automata are history-deterministic and 0-1-probabilistic.
(2) Each omega-regular language can be recognised by a unique minimal layered automaton, admitting a congruence-based description.
(3) This minimal automaton is computable in polynomial time from a given layered automaton.
This is work in progress with Christof Löding and Igor Walukiewicz.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne