Logic and Languages of Higher-Dimensional Automata
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914732157435904 |
|---|---|
| author | Amrane, Amazigh Bazille, Hugo Fahrenberg, Uli Fortin, Marie |
| author_facet | Amrane, Amazigh Bazille, Hugo Fahrenberg, Uli Fortin, Marie |
| contents | In this paper we study finite higher-dimensional automata (HDAs) from the logical point of view. Languages of HDAs are sets of finite bounded-width interval pomsets with interfaces (iiPoms<=k) closed under order extension. We prove that languages of HDAs are MSO-definable. For the converse, we show that the order extensions of MSO-definable sets of iiPoms<=k are languages of HDAs. As a consequence, unlike the case of all pomsets, order extension of MSO-definable sets of iiPoms<=k is also MSO-definable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19526 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Logic and Languages of Higher-Dimensional Automata Amrane, Amazigh Bazille, Hugo Fahrenberg, Uli Fortin, Marie Formal Languages and Automata Theory Logic in Computer Science In this paper we study finite higher-dimensional automata (HDAs) from the logical point of view. Languages of HDAs are sets of finite bounded-width interval pomsets with interfaces (iiPoms<=k) closed under order extension. We prove that languages of HDAs are MSO-definable. For the converse, we show that the order extensions of MSO-definable sets of iiPoms<=k are languages of HDAs. As a consequence, unlike the case of all pomsets, order extension of MSO-definable sets of iiPoms<=k is also MSO-definable. |
| title | Logic and Languages of Higher-Dimensional Automata |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2403.19526 |