Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-31131-4_6
Title: Complexity of the soundness problem of bounded workflow nets
Authors: Liu, G.J.
Sun, J.
Liu, Y. 
Dong, J.S. 
Keywords: co-NP-hardness
Petri nets
PSPACE-hardness
soundness
workflow nets
workflow nets with reset arcs
Issue Date: 2012
Citation: Liu, G.J.,Sun, J.,Liu, Y.,Dong, J.S. (2012). Complexity of the soundness problem of bounded workflow nets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7347 LNCS : 92-107. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-31131-4_6
Abstract: Classical workflow nets (WF-nets) are an important class of Petri nets that are widely used to model and analyze workflow systems. Soundness is a crucial property that guarantees these systems are deadlock-free and bounded. Aalst et al. proved that the soundness problem is decidable, and proposed (but not proved) that the soundness problem is EXPSPACE-hard. In this paper, we show that the satisfiability problem of Boolean expression is polynomial time reducible to the liveness problem of bounded WF-nets, and soundness and liveness are equivalent for bounded WF-nets. As a result, the soundness problem of bounded WF-nets is co-NP-hard. Workflow nets with reset arcs (reWF-nets) are an extension to WF-nets, which enhance the expressiveness of WF-nets. Aalst et al. proved that the soundness problem of reWF-nets is undecidable. In this paper, we show that for bounded reWF-nets, the soundness problem is decidable and equivalent to the liveness problem. Furthermore, a bounded reWF-net can be constructed in polynomial time for every linear bounded automaton (LBA) with an input string, and we prove that the LBA accepts the input string if and only if the constructed reWF-net is live. As a result, the soundness problem of bounded reWF-nets is PSPACE-hard. © 2012 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/43164
ISBN: 9783642311307
ISSN: 03029743
DOI: 10.1007/978-3-642-31131-4_6
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.