Polynomial Time Verification of Behavioral Inheritance for Interworkflows Based on WfMC Protocol

Shingo YAMAGUCHI; Tomohiro HIRAKAWA

doi:10.1587/transfun.E94.A.2821

Polynomial Time Verification of Behavioral Inheritance for Interworkflows Based on WfMC Protocol

Shingo YAMAGUCHI, Tomohiro HIRAKAWA

Full Text Views

0

Cite this

Summary :

The Workflow Management Coalition, WfMC for short, has given a protocol for interorganizational workflows, interworkflows for short. In the protocol, an interworkflow is constructed by connecting two or more existing workflows; and there are three models to connect those workflows: chained, nested, and parallelsynchronized. Business continuity requires the interworkflow to preserve the behavior of the existing workflows. This requirement is called behavioral inheritance, which has three variations: protocol inheritance, projection inheritance, and life-cycle inheritance. Van der Aalst et al. have proposed workflow nets, WF-nets for short, and have shown that the behavioral inheritance problem is decidable but intractable. In this paper, we first show that all WF-nets of the chained model satisfy life-cycle inheritance, and all WF-nets of the nested model satisfy projection inheritance. Next we show that soundness is a necessary condition of projection inheritance for an acyclic extended free choice WF-net of the parallelsynchronized model. Then we prove that the necessary condition can be verified in polynomial time. Finally we show that the necessary condition is a sufficient condition if the WF-net is obtained by connecting state machine WF-nets.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.12 pp.2821-2829

Publication Date: 2011/12/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E94.A.2821

Type of Manuscript: Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)

Category

Cite this

Copy

Shingo YAMAGUCHI, Tomohiro HIRAKAWA, "Polynomial Time Verification of Behavioral Inheritance for Interworkflows Based on WfMC Protocol" in IEICE TRANSACTIONS on Fundamentals, vol. E94-A, no. 12, pp. 2821-2829, December 2011, doi: 10.1587/transfun.E94.A.2821.
Abstract: The Workflow Management Coalition, WfMC for short, has given a protocol for interorganizational workflows, interworkflows for short. In the protocol, an interworkflow is constructed by connecting two or more existing workflows; and there are three models to connect those workflows: chained, nested, and parallelsynchronized. Business continuity requires the interworkflow to preserve the behavior of the existing workflows. This requirement is called behavioral inheritance, which has three variations: protocol inheritance, projection inheritance, and life-cycle inheritance. Van der Aalst et al. have proposed workflow nets, WF-nets for short, and have shown that the behavioral inheritance problem is decidable but intractable. In this paper, we first show that all WF-nets of the chained model satisfy life-cycle inheritance, and all WF-nets of the nested model satisfy projection inheritance. Next we show that soundness is a necessary condition of projection inheritance for an acyclic extended free choice WF-net of the parallelsynchronized model. Then we prove that the necessary condition can be verified in polynomial time. Finally we show that the necessary condition is a sufficient condition if the WF-net is obtained by connecting state machine WF-nets.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.2821/_p

Copy

@ARTICLE{e94-a_12_2821,
author={Shingo YAMAGUCHI, Tomohiro HIRAKAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Polynomial Time Verification of Behavioral Inheritance for Interworkflows Based on WfMC Protocol},
year={2011},
volume={E94-A},
number={12},
pages={2821-2829},
abstract={The Workflow Management Coalition, WfMC for short, has given a protocol for interorganizational workflows, interworkflows for short. In the protocol, an interworkflow is constructed by connecting two or more existing workflows; and there are three models to connect those workflows: chained, nested, and parallelsynchronized. Business continuity requires the interworkflow to preserve the behavior of the existing workflows. This requirement is called behavioral inheritance, which has three variations: protocol inheritance, projection inheritance, and life-cycle inheritance. Van der Aalst et al. have proposed workflow nets, WF-nets for short, and have shown that the behavioral inheritance problem is decidable but intractable. In this paper, we first show that all WF-nets of the chained model satisfy life-cycle inheritance, and all WF-nets of the nested model satisfy projection inheritance. Next we show that soundness is a necessary condition of projection inheritance for an acyclic extended free choice WF-net of the parallelsynchronized model. Then we prove that the necessary condition can be verified in polynomial time. Finally we show that the necessary condition is a sufficient condition if the WF-net is obtained by connecting state machine WF-nets.},
keywords={},
doi={10.1587/transfun.E94.A.2821},
ISSN={1745-1337},
month={December},}

Copy

TY - JOUR
TI - Polynomial Time Verification of Behavioral Inheritance for Interworkflows Based on WfMC Protocol
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2821
EP - 2829
AU - Shingo YAMAGUCHI
AU - Tomohiro HIRAKAWA
PY - 2011
DO - 10.1587/transfun.E94.A.2821
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2011
AB - The Workflow Management Coalition, WfMC for short, has given a protocol for interorganizational workflows, interworkflows for short. In the protocol, an interworkflow is constructed by connecting two or more existing workflows; and there are three models to connect those workflows: chained, nested, and parallelsynchronized. Business continuity requires the interworkflow to preserve the behavior of the existing workflows. This requirement is called behavioral inheritance, which has three variations: protocol inheritance, projection inheritance, and life-cycle inheritance. Van der Aalst et al. have proposed workflow nets, WF-nets for short, and have shown that the behavioral inheritance problem is decidable but intractable. In this paper, we first show that all WF-nets of the chained model satisfy life-cycle inheritance, and all WF-nets of the nested model satisfy projection inheritance. Next we show that soundness is a necessary condition of projection inheritance for an acyclic extended free choice WF-net of the parallelsynchronized model. Then we prove that the necessary condition can be verified in polynomial time. Finally we show that the necessary condition is a sufficient condition if the WF-net is obtained by connecting state machine WF-nets.
ER -