An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems (Q1097037): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: A decidability theorem for a class of vector-addition systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of the word problem for commutative semigroups of fixed dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complete problems for deterministic polynomial time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of some problems in Petri nets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallel program schemata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Properties of Conflict-Free and Persistent Petri Nets / rank
 
Normal rank
Property / cites work
 
Property / cites work: The covering and boundedness problems for vector addition systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A multiparameter analysis of the boundedness problem for vector addition systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Depth-First Search and Linear Graph Algorithms / rank
 
Normal rank

Latest revision as of 13:08, 18 June 2024

scientific article
Language Label Description Also known as
English
An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
scientific article

    Statements

    An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems (English)
    0 references
    0 references
    0 references
    0 references
    1987
    0 references
    Vector addition systems (VASs), introduced by \textit{R. M. Karp} and \textit{R. E. Miller} [J. Comput. Syst. Sci. 3, 147-195 (1969; Zbl 0198.326)] are known to be equivalent to Petri nets. For a subclass of VASs called conflict-free VASs an upper bound of exponential time for solving the boundedness problem is given by \textit{L. H. Landweber} and \textit{E. L. Robertson} [J. Assoc. Comput. Mach. 25, 352-264 (1978; Zbl 0384.68062)]. The paper first introduces the notion of conflict-free vector replacement systems (VRSs), that is general enough to include both conflict-free VASs and Petri nets as special cases. Then an \(O(n^{1.5})\) algorithm for determining boundedness of conflict-free VRSs is proved. The proof relies on the assumption that no number in any addition rule is less than -1.
    0 references
    complexity of algorithms
    0 references
    Vector addition systems
    0 references
    Petri nets
    0 references
    vector replacement systems
    0 references
    boundedness
    0 references
    0 references

    Identifiers