In: Journal of Computer and System Sciences, Vol. 37, pages 349-366. 1988.
Abstract: In this paper, completeness results are given for the reachability, containment, and equivalence problems for conflict-free vector replacement systems. An NP algorithm is given for deciding reachability. The main result shows that the containment and equivalence problems are complete for the set of all languages whose complements are in the second level of the polynomial-time hierarchy.