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.

---