Nonprimitive recursive complexity and undecidability for Petri net equivalences

DOI10.1016/S0304-3975(00)00100-6zbMath0974.68130OpenAlexW2081063330WikidataQ127908569 ScholiaQ127908569MaRDI QIDQ5941099

Petr Jančar

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00100-6

zbMATH Keywords

complexitydecidabilityPetri-nets

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Unnamed Item ⋮ Context-free commutative grammars with integer counters and resets ⋮ Petri nets and regular processes ⋮ Complexity Hierarchies beyond Elementary ⋮ Verifying lossy channel systems has nonprimitive recursive complexity.

Cites Work

• Modular construction and partial order semantics of Petri nets
• Undecidability of bisimilarity for Petri nets and some related problems
• The equality problem for vector addition systems is undecidable
• The covering and boundedness problems for vector addition systems
• Decidability of bisimilarity for one-counter processes.
• The Complexity of the Finite Containment Problem for Petri Nets
• Infinite results
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item