Nie jesteś zalogowany | Zaloguj się

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.