Summary
International Technical Conference on Circuits/Systems, Computers and Communications
2008
Session Number:F1
Session:
Number:F1-5
Reachability Problem of State Machines with Batch Processing Arcs
Nami Mizuno, Atsushi Ohta, Kohkichi Tsuji,
pp.-
Publication Date:2008/7/7
Online ISSN:2188-5079
Summary:
Petri net is an effective model for concurrent systems. Batch Petri net is one of Turing machine equivalent extended classes. Number of tokens moved by a firing of transition through batch processing arcs equals to the minimum number of tokens among its input places connected with batch processing arcs. This paper studies reachability problem of batch state machines, a subclass of batch Petri net. Computational complexity is shown to be NP-hard. Sufficient conditions for reachability are derived.