Nonprimitive recursive complexity and undecidability for Petri net equivalences (Q5941099)

From MaRDI portal
scientific article; zbMATH DE number 1635264
Language Label Description Also known as
English
Nonprimitive recursive complexity and undecidability for Petri net equivalences
scientific article; zbMATH DE number 1635264

    Statements

    Nonprimitive recursive complexity and undecidability for Petri net equivalences (English)
    0 references
    0 references
    20 August 2001
    0 references
    The aim of this note is twofold. Firstly, it shows that the undecidability result for bisimilarity in [the author, ibid. 148, No. 2, 281-301 (1985; Zbl 0873.68147)] can be immediately extended for the whole range of equivalences (and preorders) on labelled Petri nets. Secondly, it shows that restricting our attention to nets with finite reachable space, the respective (decidable) problems are nonprimitive recursive; this approach also applies to \textit{E. W. Mayr} and \textit{A. R. Meyer}'s result [J. Assoc. Comput. Mach. 28, 561-576 (1981; Zbl 0462.68020)] for the reachability set equality, yielding a more direct proof.
    0 references
    0 references
    Petri-nets
    0 references
    decidability
    0 references
    complexity
    0 references
    0 references
    0 references