Unambiguous Acceptance of Thin Coalgebras
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912931183067136 |
|---|---|
| author | Chernev, Anton Cîrstea, Corina Hansen, Helle Hvid Kupke, Clemens |
| author_facet | Chernev, Anton Cîrstea, Corina Hansen, Helle Hvid Kupke, Clemens |
| contents | Automata admitting at most one accepting run per structure, known as unambiguous automata, find applications in verification of reactive systems as they extend the class of deterministic automata whilst maintaining some of their desirable properties. In this paper, we generalise a classical construction of unambiguous automata from thin trees to thin coalgebras for analytic functors. This achieves two goals: extending the existing construction to a larger class of structures, and providing conceptual clarity and parametricity to the construction by formalising it in the coalgebraic framework. As part of the construction, we link automaton acceptance of languages of thin coalgebras to language recognition via so-called coherent algebras, which were previously introduced for studying thin coalgebras. This link also allows us to establish an automata-theoretic characterisation of languages recognised by finite coherent algebras. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26371 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unambiguous Acceptance of Thin Coalgebras Chernev, Anton Cîrstea, Corina Hansen, Helle Hvid Kupke, Clemens Formal Languages and Automata Theory Automata admitting at most one accepting run per structure, known as unambiguous automata, find applications in verification of reactive systems as they extend the class of deterministic automata whilst maintaining some of their desirable properties. In this paper, we generalise a classical construction of unambiguous automata from thin trees to thin coalgebras for analytic functors. This achieves two goals: extending the existing construction to a larger class of structures, and providing conceptual clarity and parametricity to the construction by formalising it in the coalgebraic framework. As part of the construction, we link automaton acceptance of languages of thin coalgebras to language recognition via so-called coherent algebras, which were previously introduced for studying thin coalgebras. This link also allows us to establish an automata-theoretic characterisation of languages recognised by finite coherent algebras. |
| title | Unambiguous Acceptance of Thin Coalgebras |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2510.26371 |