Uli Fahrenberg ; Krzysztof Ziemiański - Myhill-Nerode Theorem for Higher-Dimensional Automata

fi:12761 - Fundamenta Informaticae, November 10, 2024, Volume 192, Issues 3-4: Petri Nets 2023
Myhill-Nerode Theorem for Higher-Dimensional AutomataArticle

Authors: Uli Fahrenberg ; Krzysztof Ziemiański

    We establish a Myhill-Nerode type theorem for higher-dimensional automata (HDAs), stating that a language is regular if and only 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. Lastly, we develop analogues of the Myhill-Nerode construction and of determinacy for HDAs with interfaces.


    Volume: Volume 192, Issues 3-4: Petri Nets 2023
    Published on: November 10, 2024
    Accepted on: August 19, 2024
    Submitted on: January 1, 2024
    Keywords: Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 18 times.
    This article's PDF has been downloaded 11 times.