The search functionality is under construction.
The search functionality is under construction.

Reachability Analysis of Variants of Communication-Free Petri Nets

Chien-Liang CHEN, Suey WANG, Hsu-Chun YEN

  • Full Text Views

    0

  • Cite this

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

Publication
IEICE TRANSACTIONS on Information Vol.E92-D No.3 pp.377-388
Publication Date
2009/03/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E92.D.377
Type of Manuscript
PAPER
Category
Algorithm Theory

Authors

Keyword