Reachability Analysis of Variants of Communication-Free Petri Nets

Chien-Liang CHEN  Suey WANG  Hsu-Chun YEN 

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

Full Text: PDF(449.6KB)

Summary: 
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.'