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.'
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Chien-Liang CHEN, Suey WANG, Hsu-Chun YEN, "Reachability Analysis of Variants of Communication-Free Petri Nets" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 3, pp. 377-388, March 2009, doi: 10.1587/transinf.E92.D.377.
Abstract: 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.'
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.377/_p
Copy
@ARTICLE{e92-d_3_377,
author={Chien-Liang CHEN, Suey WANG, Hsu-Chun YEN, },
journal={IEICE TRANSACTIONS on Information},
title={Reachability Analysis of Variants of Communication-Free Petri Nets},
year={2009},
volume={E92-D},
number={3},
pages={377-388},
abstract={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.'},
keywords={},
doi={10.1587/transinf.E92.D.377},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Reachability Analysis of Variants of Communication-Free Petri Nets
T2 - IEICE TRANSACTIONS on Information
SP - 377
EP - 388
AU - Chien-Liang CHEN
AU - Suey WANG
AU - Hsu-Chun YEN
PY - 2009
DO - 10.1587/transinf.E92.D.377
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2009
AB - 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.'
ER -