Persistence of vector replacement systems is decidable

DOI10.1007/BF00289268MaRDI QIDQ1149775zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

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

Cited in

(25)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1149775)