Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.25253 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914598818414592 |
|---|---|
| author | Erlich, Enzo Ledent, Jérémy Ziemiański, Krzysztof |
| author_facet | Erlich, Enzo Ledent, Jérémy Ziemiański, Krzysztof |
| contents | Higher-dimensional automata (HDA) are a model of concurrency that models simultaneous execution of events using higher dimensional cells. HDA recognize languages of pomsets, a generalization of finite words whose letters are partially ordered. We prove a new algebraic characterization of HDA languages: a language of pomsets is regular if and only if it is the inverse image of a functor from the category of pomsets into a finite category. Furthermore, the language is definable in first-order logic exactly when it is recognized by an aperiodic category, generalizing the McNaughton-Papert theorem to HDA languages. We also investigate a notion of counter-free HDA, and show that if a language is accepted by a counter-free HDA, it must be definable in first-order logic. The converse, however, is still open. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25253 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algebraic Characterization of FO-definable Languages of Higher-Dimensional Automata Erlich, Enzo Ledent, Jérémy Ziemiański, Krzysztof Formal Languages and Automata Theory Higher-dimensional automata (HDA) are a model of concurrency that models simultaneous execution of events using higher dimensional cells. HDA recognize languages of pomsets, a generalization of finite words whose letters are partially ordered. We prove a new algebraic characterization of HDA languages: a language of pomsets is regular if and only if it is the inverse image of a functor from the category of pomsets into a finite category. Furthermore, the language is definable in first-order logic exactly when it is recognized by an aperiodic category, generalizing the McNaughton-Papert theorem to HDA languages. We also investigate a notion of counter-free HDA, and show that if a language is accepted by a counter-free HDA, it must be definable in first-order logic. The converse, however, is still open. |
| title | Algebraic Characterization of FO-definable Languages of Higher-Dimensional Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2605.25253 |