Complexity of Place / Transition Nets

This is a survey of results about the 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 first and then problems are presented by decreasing complexity. As a consequence of the results presented it will follow that one has to concentrate on very restricted classes of systems in order to get practically relevant algorithms that work well for all cases, since even seemingly simple classes of Petri nets have simple problems with a provable high lower bound for the complexity of their sol’ution.