Algebraic Characterization of FO-definable Languages of Higher-Dimensional Automata
For researchers in concurrency theory and automata theory, this work generalizes classical results from word languages to pomset languages, offering a new algebraic framework for higher-dimensional automata.
The paper provides an algebraic characterization of regular languages of pomsets recognized by higher-dimensional automata (HDA) and extends the McNaughton-Papert theorem to show that first-order definable languages correspond exactly to those recognized by aperiodic categories. It also introduces counter-free HDA and proves that languages accepted by them are first-order definable, though the converse remains open.
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.