Reference:

J. Esparza. Petri nets, commutative context-free grammars, and basic parallel processes. Fundamenta Informaticae, 31:13–26, 1997.

Abstract:

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 -complete. Further consequences are: the uniform word problem for commutative context-free grammars is -complete; weak-bisimilarity is semidecidable for Basic Parallel Processes.

Suggested BibTeX entry:

@article{Esp97a,
    author = {J. Esparza},
    journal = {Fundamenta Informaticae},
    pages = {13--26},
    title = {Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes},
    volume = {31},
    year = {1997}
}