Persistence of vector replacement systems is decidable

DOI10.1007/BF00289268zbMath0454.68048OpenAlexW1971231744MaRDI QIDQ1149775

Ernst W. Mayr

Publication date: 1981

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289268

zbMATH Keywords

Petri netreachable states

Mathematics Subject Classification ID

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

Related Items (25)

Catalytic P systems, semilinear sets, and vector addition systems ⋮ Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ Equivalence between model-checking flat counter systems and Presburger arithmetic ⋮ Completeness results for conflict-free vector replacement systems ⋮ Unnamed Item ⋮ Problems concerning fairness and temporal logic for conflict-free Petri nets ⋮ Petri nets for modelling metabolic pathways: a survey ⋮ Verifying chemical reaction network implementations: a pathway decomposition approach ⋮ On weak persistency of Petri nets ⋮ Behavioural equivalence for infinite systems — Partially decidable! ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE ⋮ A unified approach for deciding the existence of certain petri net paths ⋮ Verification of membrane systems with delays via Petri nets with delays ⋮ ON YEN'S PATH LOGIC FOR PETRI NETS ⋮ The 4C Spectrum of Fundamental Behavioral Relations for Concurrent Systems ⋮ Normal and sinkless Petri nets ⋮ Local time membrane systems and time Petri nets ⋮ ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS ⋮ PATH DECOMPOSITION AND SEMILINEARITY OF PETRI NETS ⋮ On Yen’s Path Logic for Petri Nets ⋮ Deciding reachability problems in Turing-complete fragments of Mobile Ambients ⋮ Equality of languages coincides with isomorphism of reachable state graphs for bounded and persistent Petri nets ⋮ Normal Petri nets ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws

Cites Work

• The equality problem for vector addition systems is undecidable
• Decidable problems on the strong connectivity of Petri net reachability sets
• Synchronization and computing capabilities of linear asynchronous structures
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• Semigroups, Presburger formulas, and languages
• Parallel program schemata
• Properties of Conflict-Free and Persistent Petri Nets
• On Context-Free Languages
• Tree-Manipulating Systems and Church-Rosser Theorems

This page was built for publication: Persistence of vector replacement systems is decidable