Verification

H.M.W. Verbeek, M.T. Wynn

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

2 Citations (Scopus)

Abstract

Introduction. Chapter 2 introduced the soundness property on a special class of Petri nets called WF-nets (WorkFlow nets). To reiterate, a WF-net is sound if and only if the following requirements are met: Any executing instance of the WF-net must eventually terminate At the moment of termination, there must be precisely one token in the end place and all other places are empty No dead tasks Van der Aalst has shown that soundness of a WF-net corresponds to boundedness and liveness of an extension of that WF-net. As boundedness and liveness of Petri nets are both decidable, soundness ofWF-nets is also decidable. Based on this observation, theWoflan tool was built, which uses standard Petri-net techniques to decide soundness. However, as Chap. 1 has already mentioned, the class of WF-nets is not sufficient to reason about YAWL nets. For this, we need to extend the WF-nets with the concept of reset arcs, yielding RWF-nets (Reset WorkFlow nets). Using reset arcs, the cancelation features of YAWL can be captured in a natural way: if some task or condition is canceled by some task, then the corresponding place is reset by the corresponding transition. Unfortunately, soundness of an RWF-net does not correspond to boundedness and liveness of an extension of this net, as the example RWF-net in Fig. 20.1 shows. Although this RWF-net is sound, it is unbounded as the place p may contain an arbitrary number of tokens. Furthermore, the reachability problem is undecidable for reset nets. As the liveness property corresponds to a reachability problem, the liveness property cannot be decided for arbitrary reset nets. On top of this, YAWL also includes the OR-join construct, which has been neglected so far in this chapter.
Original languageEnglish
Title of host publicationModern business process automation : YAWL and its support environment
EditorsA.H.M. Hofstede, ter, W.M.P. Aalst, van der, M. Adams, N. Russell
Place of PublicationBerlin
PublisherSpringer
Pages513-539
ISBN (Print)978-3-642-03120-5
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Verification'. Together they form a unique fingerprint.

Cite this