The equality problem for vector addition systems is undecidable
From MaRDI portal
Publication:1238997
DOI10.1016/0304-3975(76)90008-6zbMath0357.68038OpenAlexW1970398023WikidataQ126981974 ScholiaQ126981974MaRDI QIDQ1238997
Publication date: 1976
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(76)90008-6
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Algorithms in computer science (68W99)
Related Items (39)
Marking fairness in Petri nets ⋮ The theory of ends, pushdown automata, and second-order logic ⋮ Catalytic P systems, semilinear sets, and vector addition systems ⋮ Causality, Behavioural Equivalences, and the Security of Cyberphysical Systems ⋮ Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Subsystems of Peano Arithmetic ⋮ The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups ⋮ Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ Unnamed Item ⋮ Context-free commutative grammars with integer counters and resets ⋮ Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems ⋮ Deciding a class of path formulas for conflict-free Petri nets ⋮ Completeness results for conflict-free vector replacement systems ⋮ Persistence of vector replacement systems is decidable ⋮ Classifying the computational complexity of problems ⋮ On the reachability problem for 5-dimensional vector addition systems ⋮ Regularity and firing sequences of computation graphs ⋮ Program verification: state of the art, problems, and results. II ⋮ Petri nets and regular processes ⋮ Composition/décomposition de réseaux de Pétri et de leurs graphes de couverture ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ Undecidability of bisimilarity for Petri nets and some related problems ⋮ Complexity results for 1-safe nets ⋮ Normal and sinkless Petri nets ⋮ Nonprimitive recursive complexity and undecidability for Petri net equivalences ⋮ Concurrency, Synchronization, and Conflicts in Petri Nets ⋮ Decidable problems on the strong connectivity of Petri net reachability sets ⋮ The covering and boundedness problems for vector addition systems ⋮ The equivalence of vector addition systems to a subclass of Post canonical systems ⋮ Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems ⋮ On the finite containment problem for Petri nets ⋮ Complexity Hierarchies beyond Elementary ⋮ Homomorphisms between models of parallel computation ⋮ Modular implementation of concurrency ⋮ Normal Petri nets ⋮ The residue of vector sets with applications to decidability problems in Petri nets ⋮ Verifying lossy channel systems has nonprimitive recursive complexity. ⋮ Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups. ⋮ Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems ⋮ A taxonomy of fairness and temporal logic problems for Petri nets
Cites Work
This page was built for publication: The equality problem for vector addition systems is undecidable
