scientific article; zbMATH DE number 4024808
[For the entire collection see Zbl 0616.00013.] In this paper, we give completeness results for the reachability, containment, and equivalence problems for conflict-free vector replacement systems (VRSs). We first give an NP algorithm for deciding reachability, thus giving the first primitive recursive algorithm for this problem. Since Jones, Landweber, and Lien have shown this problem to be NP-hard, it follows that the problem is NP-complete. Next, we show as our main result that the containment and equivalence problems are \(\Pi_ 2^{P}\)-complete, where \(\Pi_ 2^{P}\) is the set of all languages whose complements are in the second level of the polynomial-time hierarchy. In showing the upper bound, we first show that the reachability set has a semilinear set (SLS) representation that is exponential in the size of the problem description, but which has a high degree of symmetry. We are then able to utilize a strategy introduced by Huynh (concerning SLSs) to complete our upper bound proof.
- Completeness results for conflict-free vector replacement systems
- scientific article; zbMATH DE number 4035164
- scientific article; zbMATH DE number 3878366
- An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
- Rewriting systems for reachability in vector addition systems with pairs
- Co-finiteness and co-emptiness of reachability sets in vector addition systems with states
- Co-finiteness and co-emptiness of reachability sets in vector addition systems with states
- scientific article; zbMATH DE number 4092784
- Demystifying Reachability in Vector Addition Systems
- The general vector addition system reachability problem by Presburger inductive invariants
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3766869)