Layered automata: A canonical model for automata over infinite words
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912841149186048 |
|---|---|
| author | Casares, Antonio Löding, Christof Walukiewicz, Igor |
| author_facet | Casares, Antonio Löding, Christof Walukiewicz, Igor |
| contents | We introduce layered automata, a subclass of alternating parity automata that generalises deterministic automata. Assuming a consistency property, these automata are history deterministic and 0-1 probabilistic. We show that every omega-regular language is recognised by a unique minimal consistent layered automaton, and that this canonical form can be computed in polynomial time from every layered or deterministic automaton. We further establish that for layered automata both consistency checking and inclusion testing can be performed in polynomial time. Much like deterministic finite automata, minimal consistent layered automata admit a characterisation based on congruences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15940 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Layered automata: A canonical model for automata over infinite words Casares, Antonio Löding, Christof Walukiewicz, Igor Formal Languages and Automata Theory Logic in Computer Science 68Q45 F.4.3 We introduce layered automata, a subclass of alternating parity automata that generalises deterministic automata. Assuming a consistency property, these automata are history deterministic and 0-1 probabilistic. We show that every omega-regular language is recognised by a unique minimal consistent layered automaton, and that this canonical form can be computed in polynomial time from every layered or deterministic automaton. We further establish that for layered automata both consistency checking and inclusion testing can be performed in polynomial time. Much like deterministic finite automata, minimal consistent layered automata admit a characterisation based on congruences. |
| title | Layered automata: A canonical model for automata over infinite words |
| topic | Formal Languages and Automata Theory Logic in Computer Science 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2601.15940 |