Coverability and Termination in Recursive Petri Nets

DOI10.1007/978-3-030-21571-2_23OpenAlexW2950465720MaRDI QIDQ6144226

Igor Khmelnitsky, Serge Haddad, Alain Finkel

Publication date: 29 January 2024

Published in: Application and Theory of Petri Nets and Concurrency (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-21571-2_23

zbMATH Keywords

complexityterminationexpressivenesscoverabilityrecursive Petri nets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A structure to decide reachability in Petri nets
• The covering and boundedness problems for vector addition systems
• The emptiness problem for valence automata or: another decidable extension of Petri nets
• The covering and boundedness problems for branching vector addition systems
• Recursive Petri nets
• Model Checking Vector Addition Systems with one zero-test
• Nonelementary Complexities for Branching VASS, MELL, and Extensions
• The Reachability Problem for Vector Addition System with One Zero-Test
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• An Algorithm for the General Petri Net Reachability Problem
• Concurrently controlled grammars
• The Complexity of Coverability in ν-Petri Nets
• Reachability in Petri Nets with Inhibitor Arcs
• Well-structured transition systems everywhere!

This page was built for publication: Coverability and Termination in Recursive Petri Nets