On the finite containment problem for Petri nets (Q1819937)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3995065
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the finite containment problem for Petri nets |
scientific article; zbMATH DE number 3995065 |
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
0.8429815769195557
0 references
0.824021577835083
0 references
0.8098891973495483
0 references
0.7831778526306152
0 references
