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 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.
| Original language | English |
|---|---|
| Pages (from-to) | 13-25 |
| Number of pages | 13 |
| Journal | Fundamenta Informaticae |
| Volume | 31 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jul 1997 |
Keywords
- Basic Parallel Processes
- Commutative Context-free Grammars
- Petri nets
- Weak bisimilarity