Logic and Languages of Higher-Dimensional Automata
<|reference_start|>Logic and Languages of Higher-Dimensional Automata: In this paper we study finite higher-dimensional automata (HDAs) from the logical point of view. Languages of HDAs are sets of finite bounded-width interval pomsets with interfaces (iiPoms<=k) closed under order extension. We prove that languages of HDAs are MSO-definable. For the converse, we show that the order extensions of MSO-definable sets of iiPoms<=k are languages of HDAs. As a consequence, unlike the case of all pomsets, order extension of MSO-definable sets of iiPoms<=k is also MSO-definable.<|reference_end|>
@article{amrane2024logic,
    title={Logic and Languages of Higher-Dimensional Automata},
    author={Amazigh Amrane, Hugo Bazille, Uli Fahrenberg and Marie Fortin},
    journal={arXiv preprint arXiv:2403.19526},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.19526},
    primaryClass={cs.FL cs.LO}
}