A canonical model of automata over infinite words
- Prelegent(ci)
- Antonio Casares
- Afiliacja
- University of Warsaw
- Język referatu
- angielski
- Termin
- 21 maja 2025 14:15
- Pokój
- p. 5440
- Tytuł w języku polskim
- A canonical model of automata over infinite words
- Seminarium
- Seminarium „Teoria automatów”
Contrary to the case of automata over finite words, deterministic parity automaton cannot be minimised in polynomial time, and omega-regular languages do not admit a unique, minimal deterministic automaton. Yet, not all hope is lost!
In this talk I will introduce layered automata, a subclass of alternating parity automata, defined by syntactic conditions and extending deterministic ones. We show:
- All layered automata are history-deterministic.
- Each omega-regular language can be recognised by a unique minimal layered automaton, computable in polynomial time from a given layered automaton.
This is a work in progress with Christof Löding and Igor Walukiewicz.