The decidability of persistence for vector addition systems

DOI10.1016/0020-0190(80)90026-5zbMath0444.68045OpenAlexW2162339458MaRDI QIDQ1144929

Jan Grabowski

Publication date: 1980

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90026-5

zbMATH Keywords

persistencePetri netreachability problemPresburger arithmeticvector addition systems

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25)

Related Items (12)

Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ Deciding a class of path formulas for conflict-free Petri nets ⋮ Completeness results for conflict-free vector replacement systems ⋮ Problems concerning fairness and temporal logic for conflict-free Petri nets ⋮ Decomposition Theorems for Bounded Persistent Petri Nets ⋮ On weak persistency of Petri nets ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ Normal and sinkless Petri nets ⋮ A decomposition theorem for finite persistent transition systems ⋮ PATH DECOMPOSITION AND SEMILINEARITY OF PETRI NETS ⋮ Equality of languages coincides with isomorphism of reachable state graphs for bounded and persistent Petri nets ⋮ Normal Petri nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decidability theorem for a class of vector-addition systems
• Decidable problems on the strong connectivity of Petri net reachability sets
• Semigroups, Presburger formulas, and languages
• Parallel program schemata
• Synchronisationsgraphen
• Properties of Conflict-Free and Persistent Petri Nets

This page was built for publication: The decidability of persistence for vector addition systems