A framework for efficiently deciding language inclusion for sound unlabelled WF-Nets

D. M M Schunselaar, W.H.M. Verbeek, Wil M P Van Der Aalst, H. A. Reijers

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We present a framework to efficiently check language inclusion between two sound unlabelled WF-nets. That is, to efficiently check whether every successfully terminating transition sequence of one sound unlabelled WF-net also is a successfully terminating transition sequence of a second sound unlabelled WF-net. Existing approaches for checking language inclusion are typically based on the underlying transition systems of both nets, and hence are subject to the well-known stateexplosion problem. As a result, these approaches cannot check language inclusion on sound unlabelled WF-nets in polynomial time. Our framework allows for efficient language inclusion checks even if parallelism is present, by comparing specific net abstractions that can be computed and compared in polynomial time. For sound unlabelled WF-nets that are free-choice and do not contain loops, we prove that our approach is complete.

Original languageEnglish
Pages (from-to)135-154
Number of pages20
JournalCEUR Workshop Proceedings
Volume989
Publication statusPublished - 2013
Externally publishedYes

Fingerprint Dive into the research topics of 'A framework for efficiently deciding language inclusion for sound unlabelled WF-Nets'. Together they form a unique fingerprint.

Cite this