In: PNPM89. Proceedings of the Third International Workshop On Petri Nets and Performance Models, 1989, Kyoto, Japan, pages 258-265. Los Alamitos, CA, USA: IEEE Computer Society Press, 1990.
Abstract: The computational complexity of reachability problems for Petri nets is analyzed. A new class of Petri nets is introduced. A net of the class is composed of subnets of state machines. Sufficient conditons on initial and target markings are obtained under which the reachability problem for the class is solvable in deterministic polynomial time. Also presented is an algorithm that examines in deterministic polynomial time whether a Petri net is in the class.
Keywords: reachability problem complexity.