[Lrde Annonce] Paper accepted at PN 2023: A Myhill-Nerode Theorem for Higher-Dimensional Automata

We are happy to announce that the following article has been accepted at Application and Theory of Petri Nets and Concurrency (PETRI NETS): A Myhill-Nerode Theorem for Higher-Dimensional Automata Uli Fahrenberg, Krzysztof Ziemiański Abstract: We establish a Myhill-Nerode type theorem for higher-dimensional automata (HDAs), stating that a language is regular precisely if it has finite prefix quotient. HDAs extend standard automata with additional structure, making it possible to distinguish between interleavings and concurrency. We also introduce deterministic HDAs and show that not all HDAs are determinizable, that is, there exist regular languages that cannot be recognised by a deterministic HDA. Using our theorem, we develop an internal characterisation of deterministic languages. The paper is available at https://arxiv.org/abs/2210.08298