On Determining the AND-OR Hierarchy in Workflow Nets

DOI10.3233/FI-2017-1599zbMATH Open1386.68109arXiv1701.02199OpenAlexW2765615144MaRDI QIDQ4606265FDOQ4606265

Jacek Sroka, Jan Hidders

Publication date: 2 March 2018

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: This paper presents the notion of AND-OR reduction, which reduces a WF net to a smaller net by iteratively contracting certain well-formed subnets into single nodes until no more such contractions are possible. This reduction can reveal the hierarchical structure of a WF net, and since it preserves certain semantical properties such as soundness, it can help with analysing and understanding why a WF net is sound or not. The reduction can also be used to verify if a WF net is an AND-OR net. This class of WF nets was introduced in earlier work, and arguably describes nets that follow good hierarchical design principles. It is shown that the AND-OR reduction is confluent up to isomorphism, which means that despite the inherent non-determinism that comes from the choice of subnets that are contracted, the final result of the reduction is always the same up to the choice of the identity of the nodes. Based on this result, a polynomial-time algorithm is presented that computes this unique result of the AND-OR reduction. Finally, it is shown how this algorithm can be used to verify if a WF net is an AND-OR net.

Full work available at URL: https://arxiv.org/abs/1701.02199

Recommendations

• On generating hierarchical workflow nets and their extensions and verifying hierarchicality
• Applications and Theory of Petri Nets 2005
• Soundness of workflow nets: classification, decidability, and analysis
• Structural soundness of workflow nets is decidable
• On the \(\alpha \)-reconstructibility of workflow nets
• Complexity of the soundness problem of workflow nets
• Soundness and separability of workflow nets in the stepwise refinement approach
• Confusion analysis and detection for workflow nets
• Sufficient and necessary condition to decide compatibility for a class of interorganizational workflow nets
• Discovering workflow nets using integer linear programming

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (1)

• Confusion analysis and detection for workflow nets

This page was built for publication: On Determining the AND-OR Hierarchy in Workflow Nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606265)