Reachability Analysis of Variants of Communication-Free Petri Nets

Chien-Liang CHEN  Suey WANG  Hsu-Chun YEN  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.3   pp.377-388
Publication Date: 2009/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.377
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm Theory
reachability,  communication-free Petri nets,  

Full Text: PDF>>
Buy this Article

Communication-free Petri nets provide a net semantics for Basic Parallel Processes, which form a subclass of Milner's Calculus of Communicating Systems (CCS) a process calculus for the description and algebraic manipulation of concurrent communicating systems. It is known that the reachability problem for communication-free Petri nets is NP-complete. Lacking the synchronization mechanism, the expressive power of communication-free Petri nets is somewhat limited. It is therefore importance to see whether the power of communication-free Petri nets can be enhanced without sacrificing their analytical capabilities. As a first step towards this line of research, in this paper our main concern is to investigate, from the decidability/complexity viewpoint, the reachability problem for a number of variants of communication-free Petri nets, including communication-free Petri nets augmented with 'static priorities,' 'dynamic priorities,' 'states,' 'inhibitor arcs,' and 'timing constraints.'