On the finite containment problem for Petri nets
type: Item
instance of: scholarly article
title: On the finite containment problem for Petri nets
zbMATH Open document ID: 0614.68047
DOI: 10.1016/0304-3975(86)90169-6
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 3995065
zbMATH Keywords: Ackermann function
zbMATH Keywords: finite containment problem
zbMATH Keywords: vector addition systems
zbMATH Keywords: finite Ramsey theorem
zbMATH Keywords: Karp-Miller-covering-tree
author: Peter Clote
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90169-6
OpenAlex ID: W1985986492
cites work: Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Subsystems of Peano Arithmetic
cites work: Q3903002
cites work: The equality problem for vector addition systems is undecidable
cites work: Parallel program schemata
cites work: Rapidly growing Ramsey functions
cites work: Petri nets and large finite sets
cites work: The Complexity of the Finite Containment Problem for Petri Nets
cites work: Q3893931
cites work: The covering and boundedness problems for vector addition systems
description: scientific article; zbMATH DE number 3995065