2025/05/15 by Amazigh Amrane, Hugo Bazille, Amrane, Amazigh +9
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2505.10461
openalex publication_date 2025/05/15 · openalex created_date 2025/10/06 · openalex updated_date 2026/07/28
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.