IEICE TRANSACTIONS on Information
State Number Calculation Problem of Workflow Nets
Summary :
The number of states is a very important matter for model checking approach in Petri net's analysis. We first gave a formal definition of state number calculation problem: For a Petri net with an initial state (marking), how many states does it have? Next we showed the problem cannot be solved in polynomial time for a popular subclass of Petri nets, known as free choice workflow nets, if P≠NP. Then we proposed a polynomial time algorithm to solve the problem by utilizing a representational bias called as process tree. We also showed effectiveness of the algorithm through an application example.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.6 pp.1128-1136
- Publication Date
- 2015/06/01
- Publicized
- 2015/02/13
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2014FOP0009
- Type of Manuscript
- Special Section PAPER (Special Section on Formal Approach)
- Category
- Petri net
Authors
Mohd Anuaruddin BIN AHMADON
Yamaguchi University
Shingo YAMAGUCHI
Yamaguchi University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Mohd Anuaruddin BIN AHMADON, Shingo YAMAGUCHI, "State Number Calculation Problem of Workflow Nets" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 6, pp. 1128-1136, June 2015, doi: 10.1587/transinf.2014FOP0009.
Abstract: The number of states is a very important matter for model checking approach in Petri net's analysis. We first gave a formal definition of state number calculation problem: For a Petri net with an initial state (marking), how many states does it have? Next we showed the problem cannot be solved in polynomial time for a popular subclass of Petri nets, known as free choice workflow nets, if P≠NP. Then we proposed a polynomial time algorithm to solve the problem by utilizing a representational bias called as process tree. We also showed effectiveness of the algorithm through an application example.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014FOP0009/_p
Copy
@ARTICLE{e98-d_6_1128,
author={Mohd Anuaruddin BIN AHMADON, Shingo YAMAGUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={State Number Calculation Problem of Workflow Nets},
year={2015},
volume={E98-D},
number={6},
pages={1128-1136},
abstract={The number of states is a very important matter for model checking approach in Petri net's analysis. We first gave a formal definition of state number calculation problem: For a Petri net with an initial state (marking), how many states does it have? Next we showed the problem cannot be solved in polynomial time for a popular subclass of Petri nets, known as free choice workflow nets, if P≠NP. Then we proposed a polynomial time algorithm to solve the problem by utilizing a representational bias called as process tree. We also showed effectiveness of the algorithm through an application example.},
keywords={},
doi={10.1587/transinf.2014FOP0009},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - State Number Calculation Problem of Workflow Nets
T2 - IEICE TRANSACTIONS on Information
SP - 1128
EP - 1136
AU - Mohd Anuaruddin BIN AHMADON
AU - Shingo YAMAGUCHI
PY - 2015
DO - 10.1587/transinf.2014FOP0009
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2015
AB - The number of states is a very important matter for model checking approach in Petri net's analysis. We first gave a formal definition of state number calculation problem: For a Petri net with an initial state (marking), how many states does it have? Next we showed the problem cannot be solved in polynomial time for a popular subclass of Petri nets, known as free choice workflow nets, if P≠NP. Then we proposed a polynomial time algorithm to solve the problem by utilizing a representational bias called as process tree. We also showed effectiveness of the algorithm through an application example.
ER -
English
