Reachability Problem of Marked Graphs with Batch Processing Arcs

Petri net is a mathematical model for discrete event systems. Batch processing arcs are suggested which moves all tokens in its input places by single firing of transition. This extension makes Petri net Turing machine equivalent, which means most of important analysis problems including reachability problem are undecidable. In this report, we study reachability problem of marked graphs with batch processing arcs. It is assumed that transitions are classified in two categories: for each transition, either all incident arcs are normal arcs or all incident arcs are batch processing arcs. Under this assumption, necessary and sufficient condition for reachability of marked graphs without batch processing arcs is shown to be extended to that with batch processing arcs.