2026/05/24 by Enzo Erlich, Jérémy Ledent, Krzysztof Ziemiański · 1 voice
Computer Science · #cs.FL
paper · pdf · doi:10.48550/arxiv.2605.25253
arxiv published 2026/05/24 · arxiv updated 2026/06/29
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.