Petri nets and large finite sets
type: Item
instance of: scholarly article
title: Petri nets and large finite sets
zbMATH Open document ID: 0569.68046
DOI: 10.1016/0304-3975(84)90029-X
author: Kenneth McAloon
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03C62
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 3909749
zbMATH Keywords: models of arithmetic
zbMATH Keywords: upper bound
zbMATH Keywords: complexity of the Karp-Miller decision procedure
zbMATH Keywords: Finite Containment Problem for pairs of Petri nets
MaRDI profile type: Publication
cites work: Parallel program schemata
cites work: Rapidly growing Ramsey functions
cites work: Q4138726
cites work: Q3926596
cites work: The Complexity of the Finite Containment Problem for Petri Nets
cites work: Some independence results for Peano arithmetic
cites work: Q3931391
description: scientific article; zbMATH DE number 3909749