Myhill-Nerode Theorem for Higher-Dimensional Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917388049448960 |
|---|---|
| author | Fahrenberg, Uli Ziemiański, Krzysztof |
| author_facet | Fahrenberg, Uli Ziemiański, Krzysztof |
| contents | We establish a Myhill-Nerode type theorem for higher-dimensional automata (HDAs), stating that a language is regular if and only if it has finite prefix quotient. HDAs extend standard automata with additional structure, making it possible to distinguish between interleavings and concurrency. We also introduce deterministic HDAs and show that not all HDAs are determinizable, that is, there exist regular languages that cannot be recognised by a deterministic HDA. Using our theorem, we develop an internal characterisation of deterministic languages. Lastly, we develop analogues of the Myhill-Nerode construction and of determinacy for HDAs with interfaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_08298 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Myhill-Nerode Theorem for Higher-Dimensional Automata Fahrenberg, Uli Ziemiański, Krzysztof Formal Languages and Automata Theory We establish a Myhill-Nerode type theorem for higher-dimensional automata (HDAs), stating that a language is regular if and only if it has finite prefix quotient. HDAs extend standard automata with additional structure, making it possible to distinguish between interleavings and concurrency. We also introduce deterministic HDAs and show that not all HDAs are determinizable, that is, there exist regular languages that cannot be recognised by a deterministic HDA. Using our theorem, we develop an internal characterisation of deterministic languages. Lastly, we develop analogues of the Myhill-Nerode construction and of determinacy for HDAs with interfaces. |
| title | Myhill-Nerode Theorem for Higher-Dimensional Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2210.08298 |