On the reachability problem for 5-dimensional vector addition systems
From MaRDI portal
Publication:1155361
DOI10.1016/0304-3975(79)90041-0zbMath0466.68048OpenAlexW2017315323MaRDI QIDQ1155361
John E. Hopcrofts, Jean-Jacques Pansiot
Publication date: 1979
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6102
Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25) Applications of computability and recursion theory (03D80)
Related Items
Catalytic P systems, semilinear sets, and vector addition systems, Unnamed Item, Guiding Craig interpolation with domain-specific abstractions, Alternating two-way AC-tree automata, Decidability of $$k$$-Soundness for Workflow Nets with an Unbounded Resource, Bounded self-stabilizing Petri nets, Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, Vector Groups and the Equality Problem for Vector Addition Systems, Petri Nets and Semilinear Sets (Extended Abstract), Context-free commutative grammars with integer counters and resets, Metric propositional neighborhood logic with an equivalence relation, Deciding a class of path formulas for conflict-free Petri nets, Universality in Molecular and Cellular Computing, Completeness results for conflict-free vector replacement systems, Unnamed Item, On selective unboundedness of VASS, Problems concerning fairness and temporal logic for conflict-free Petri nets, Linear logic automata, High undecidability of weak bisimilarity for Petri nets, Investigations on the power of matrix insertion-deletion systems with small sizes, Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks, Speed faults in computation by chemical reaction networks, Coverability in 2-VASS with one unary counter is in NP, Computing with chemical reaction networks: a tutorial, Unnamed Item, Unnamed Item, The polynomial complexity of vector addition systems with states, Unnamed Item, The computational power of population protocols, Purely Catalytic P Systems over Integers and Their Generative Power, Parikh Images of Matrix Ins-Del Systems, ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE, Data flow analysis of asynchronous systems using infinite abstract domains, A unified approach for deciding the existence of certain petri net paths, Undecidability of bisimilarity for Petri nets and some related problems, Minimalist Grammars in the Light of Logic, The context-freeness of the languages associated with vector addition systems is decidable, A structure to decide reachability in Petri nets, Exhibition of a Structural Bug with Wings, On the Boundedness Property of Semilinear Sets, Normal and sinkless Petri nets, Reachability solution characterization of parametric real-time systems, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Parameterized verification of monotone information systems, ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS, The Invariance Problem for Matrix Semigroups, Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion, Flatness and Complexity of Immediate Observation Petri Nets, PATH DECOMPOSITION AND SEMILINEARITY OF PETRI NETS, A multiparameter analysis of the boundedness problem for vector addition systems, Boundedness, empty channel detection, and synchronization for communicating finite automata, Analyzing Reachability for Some Petri Nets With Fast Growing Markings, Projections of vector addition system reachability sets are semilinear, Robustness of Expressivity in Chemical Reaction Networks, Unnamed Item, An approach to automating the verification of compact parallel coordination programs. I, Normal Petri nets, On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words, Flat Petri nets (invited talk)
Cites Work
