On the finite containment problem for Petri nets (Q1819937): Difference between revisions
From MaRDI portal
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