Petri nets and large finite sets (Q1060848)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Petri nets and large finite sets
scientific article

    Statements

    Petri nets and large finite sets (English)
    0 references
    0 references
    1984
    0 references
    An upper bound is given for the complexity of the Karp-Miller decision procedure for the Finite Containment Problem for pairs of Petri nets; the procedure is shown to primitive recursive in the Ackermann function. Bounds for the lengths of the searches involved are obtained in terms of large finite sets in the sense of Paris-Harrington and of Ketonen- Solovay.
    0 references
    models of arithmetic
    0 references
    upper bound
    0 references
    complexity of the Karp-Miller decision procedure
    0 references
    Finite Containment Problem for pairs of Petri nets
    0 references

    Identifiers

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