Olivier Finkel ; Michał Skrzypczak - On the expressive power of non-deterministic and unambiguous Petri nets over infinite words

fi:8757 - Fundamenta Informaticae, December 23, 2021, Volume 183, Issues 3-4: Petri Nets 2020
On the expressive power of non-deterministic and unambiguous Petri nets over infinite wordsArticle

Authors: Olivier Finkel ; Michał Skrzypczak

    We prove that $\omega$-languages of (non-deterministic) Petri nets and $\omega$-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of $\omega$-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of $\omega$-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net $\omega$-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for $\omega$-languages of Petri nets are $\Pi_2^1$-complete, hence also highly undecidable. Additionally, we show that the situation is quite the opposite when considering unambiguous Petri nets, which have the semantic property that at most one accepting run exists on every input. We provide a procedure of determinising them into deterministic Muller counter machines with counter copying. As a consequence, we entail that the $\omega$-languages recognisable by unambiguous Petri nets are $\Delta^0_3$ sets.


    Volume: Volume 183, Issues 3-4: Petri Nets 2020
    Published on: December 23, 2021
    Accepted on: November 25, 2021
    Submitted on: November 25, 2021
    Keywords: Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 192 times.
    This article's PDF has been downloaded 262 times.