Büchi-Elgot-Trakhtenbrot Theorem for Higher-Dimensional Automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913839954526208 |
|---|---|
| author | Amrane, Amazigh Bazille, Hugo Clement, Emily Fahrenberg, Uli Fortin, Marie Ziemiański, Krzysztof |
| author_facet | Amrane, Amazigh Bazille, Hugo Clement, Emily Fahrenberg, Uli Fortin, Marie Ziemiański, Krzysztof |
| contents | In this paper we explore languages of higher-dimensional automata (HDAs) from an algebraic and logical point of view. Such languages are sets of finite width-bounded interval pomsets with interfaces (ipomsets) closed under order extension. We show that ipomsets can be represented as equivalence classes of words over a particular alphabet, called step sequences. We introduce an automaton model that recognize such languages. Doing so allows us to lift the classical Büchi-Elgot-Trakhtenbrot Theorem to languages of HDAs: we prove that a set of interval ipomsets is the language of an HDA if and only if it is simultaneously MSO-definable, of bounded width, and closed under order refinement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10461 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Büchi-Elgot-Trakhtenbrot Theorem for Higher-Dimensional Automata Amrane, Amazigh Bazille, Hugo Clement, Emily Fahrenberg, Uli Fortin, Marie Ziemiański, Krzysztof Formal Languages and Automata Theory In this paper we explore languages of higher-dimensional automata (HDAs) from an algebraic and logical point of view. Such languages are sets of finite width-bounded interval pomsets with interfaces (ipomsets) closed under order extension. We show that ipomsets can be represented as equivalence classes of words over a particular alphabet, called step sequences. We introduce an automaton model that recognize such languages. Doing so allows us to lift the classical Büchi-Elgot-Trakhtenbrot Theorem to languages of HDAs: we prove that a set of interval ipomsets is the language of an HDA if and only if it is simultaneously MSO-definable, of bounded width, and closed under order refinement. |
| title | Büchi-Elgot-Trakhtenbrot Theorem for Higher-Dimensional Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2505.10461 |