For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Reachability Analysis of Variants of Communication-Free Petri Nets
Chien-Liang CHEN Suey WANG Hsu-Chun YEN
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/03/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm Theory
reachability, communication-free Petri nets,
Full Text: PDF>>
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.'