A canonical model of automata over infinite words

Speaker(s)

Antonio Casares

Affiliation

University of Warsaw

Language of the talk

English

Date

May 21, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

A canonical model of automata over infinite words

Seminar

Seminar Automata Theory

---

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.

---