On the finite containment problem for Petri nets (Q1819937): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0304-3975(86)90169-6 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1985986492 / rank
 
Normal rank

Revision as of 22:00, 19 March 2024

scientific article
Language Label Description Also known as
English
On the finite containment problem for Petri nets
scientific article

    Statements

    On the finite containment problem for Petri nets (English)
    0 references
    1986
    0 references
    The finite containment problem (FCP) for vector addition systems (VAS) is to determine, given two VAS with finite reachability sets \(R_ 1\), \(R_ 2\), whether \(R_ 1\subset R_ 2\). The paper shows that FCP is DTIME(Ackermann)-complete, sharpening previous results due to \textit{K. McAloon} [Theor. Comput. Sci. 32, 173-183 (1984; Zbl 0569.68046)] and to \textit{E. W. Mayr} and \textit{A. R. Meyer} [J. Assoc. Comput. Mach. 28, 561- 576 (1981; Zbl 0462.68020)]. The principal technique is to replace an application of the infinite Ramsey theorem by a certain finite Ramsey theorem yielding an upper bound for the height of the Karp-Miller- covering-tree (coinciding with the reachability tree in the case of finite reachability sets).
    0 references
    Ackermann function
    0 references
    finite containment problem
    0 references
    vector addition systems
    0 references
    finite Ramsey theorem
    0 references
    Karp-Miller-covering-tree
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references