No label defined (Q3766867)
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 4024806
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4024806 |
Statements
1987
0 references
complexity class
0 references
Petri net language
0 references
complete problems
0 references
weak Petri net computer
0 references
reachability
0 references
coverability
0 references
boundedness
0 references
liveness
0 references
complexity of decision problems
0 references
lower bounds
0 references
0.8194398283958435
0 references
0.8183088898658752
0 references
0.8157030344009399
0 references
0.8072909116744995
0 references
[For the entire collection see Zbl 0619.00023.] The paper is an improved version of the manuscript which appeared in the proceedings of the ``Advanced Course on Petri Nets'', Bad Honnef, FRG, 1986. It presents a survey of results about complexity of decision problems for various questions about Petri nets that arise in the analysis of systems. The border between undecidable and decidable problems is discussed and it is made visible that almost all problems are solvable only by ineffective algorithms even under strong restrictions. The work concentrates on identifying lower bounds for the problems and it is not intended to provide the `best' algorithms in the form of a computer program. The list of references is combined with that of the preceding paper (see Zbl 0629.68064).
0 references