Complexity of the Soundness Problem of Workflow Nets
Fundamenta Informaticae · 2014-04 · 131 (1) · 81-101
DOI: 10.3233/fi-2014-1005 ↗Kurz gefasst
Fachartikel in der Zeitschrift Fundamenta Informaticae, online erschienen am 01.04.2014. Verfasst von GuanJun Liu und 3 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref).
Abstract (Originalsprache)
Classical workflow nets (WF-nets for short) are an important subclass of Petri nets that are widely used to model and analyze workflow systems. Soundness is a crucial property of workflow systems and guarantees that these systems are deadlock-free and bounded. Aalst et al. proved that the soundness problem is decidable for WF-nets and can be polynomially solvable for free-choice WF-nets. This paper proves that the soundness problem is PSPACE-hard for WF-nets. Furthermore, it is proven that the soundness problem is PSPACE-complete for bounded WF-nets. Based on the above conclusion, it is derived that the soundness problem is also PSPACE-complete for bounded WF-nets with reset or inhibitor arcs (ReWF-nets and InWF-nets for short, resp.). ReWF- and InWF-nets are two extensions to WF-nets and their soundness problems were proven by Aalst et al. to be undecidable. Additionally, we prove that the soundness problem is co-NP-hard for asymmetric-choice WF-nets that are a larger class and can model more cases of interaction and resource allocation than free-choice ones.
Zitieren
APA
Liu, G., Sun, J., Liu, Y., & Dong, J. (2014). Complexity of the Soundness Problem of Workflow Nets. Fundamenta Informaticae, 131(1), 81-101. https://doi.org/10.3233/fi-2014-1005
Vancouver
Liu G, Sun J, Liu Y, Dong J. Complexity of the Soundness Problem of Workflow Nets. Fundamenta Informaticae. 2014;131(1):81-101. doi:10.3233/fi-2014-1005
BibTeX
@article{Liu2014,
author = {Liu, GuanJun and Sun, Jun and Liu, Yang and Dong, JinSong},
title = {Complexity of the Soundness Problem of Workflow Nets},
journal = {Fundamenta Informaticae},
year = {2014},
volume = {131},
number = {1},
pages = {81--101},
doi = {10.3233/fi-2014-1005}
}
EUVIMED