Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes
Javier Esparza · Fundamenta Informaticae · 1997
The paper provides a structural characterisation of the reachable markings of Petri nets in which every transition has exactly one input place. As a corollary, the reachability problem for this class is proved to be NP-complete. Further consequences are: the uniform word problem for commutative context-free grammars is NP-complete; weak-bisimilarity is semidecidable for Basic Parallel Processes.