Completeness results for conflict-free vector replacement systems (Q1113674): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 02:15, 5 March 2024

scientific article
Language Label Description Also known as
English
Completeness results for conflict-free vector replacement systems
scientific article

    Statements

    Completeness results for conflict-free vector replacement systems (English)
    0 references
    0 references
    0 references
    1988
    0 references
    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.
    0 references
    Petri nets
    0 references
    reachability
    0 references
    containment
    0 references
    equivalence
    0 references
    conflict-free vector replacement systems
    0 references
    primitive recursive algorithm
    0 references
    NP-complete
    0 references
    \(\Pi ^ p_ 2\)-complete
    0 references

    Identifiers