Completeness results for conflict-free vector replacement systems
type: Item
instance of: scholarly article
title: Completeness results for conflict-free vector replacement systems
zbMATH Open document ID: 0661.68061
DOI: 10.1016/0022-0000(88)90013-X
author: Rodney R. Howell
author: Louis E. Rosier
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
review text: 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 [\textit{N. D. Jones}, \textit{L. H. Landweber} and \textit{Y. E. Lien}, Theor. Comput. Sci., 277-299 (1977; Zbl 0357.68048)], it follows that the problem is NP- complete. Next, we show as our main result that the containment and equivalence problems are \(\Pi^ p_ 2\)-complete, where \(\Pi^ p_ 2\) 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 in part a strategy introduced by \textit{Thiet-Dung Huynh} [Electron. Informationsverarbeitung Kybernetik 18, 291-338 (1982; Zbl 0519.68060)] (concerning SLSs) to complete our upper bound proof.
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4080930
zbMATH Keywords: Petri nets
zbMATH Keywords: reachability
zbMATH Keywords: containment
zbMATH Keywords: equivalence
zbMATH Keywords: conflict-free vector replacement systems
zbMATH Keywords: primitive recursive algorithm
zbMATH Keywords: NP-complete
zbMATH Keywords: \(\Pi ^ p_ 2\)-complete
MaRDI profile type: Publication
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations
cites work: Q4152749
cites work: On the finite containment problem for Petri nets
cites work: A decidability theorem for a class of vector-addition systems
cites work: Vector addition systems and regular languages
cites work: The decidability of persistence for vector addition systems
cites work: The equality problem for vector addition systems is undecidable
cites work: On the reachability problem for 5-dimensional vector addition systems
cites work: Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
cites work: An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
cites work: Q3668872
cites work: Q4727433
cites work: Complexity of some problems in Petri nets
cites work: Parallel program schemata
cites work: Properties of Conflict-Free and Persistent Petri Nets
cites work: The Complexity of the Finite Containment Problem for Petri Nets
cites work: The complexity of the word problems for commutative semigroups and polynomial ideals
cites work: Persistence of vector replacement systems is decidable
cites work: Petri nets and large finite sets
cites work: Q3939247
cites work: A multiparameter analysis of the boundedness problem for vector addition systems
cites work: The polynomial-time hierarchy
cites work: Q5603731
cites work: Petri nets and regular languages
cites work: A Bound on Solutions of Linear Integer Equalities and Inequalities
full work available at URL: 0022-0000(88)90013-x
OpenAlex ID: W2087907688
description: scientific article; zbMATH DE number 4080930