An organization may have two or more similar workflows as a result of workflow evolutions or mergers and acquisitions. We should grasp the common behavior of those workflows to consolidate the management of them and/or to do business process reengineering. Workflows can be modeled as a particular class of Petri nets, called workflow nets. The common behavior of two or more workflow nets can be represented as a superclass under the behavioral inheritance of those workflow nets. In this paper, we tackled a problem of extracting a superclass from two workflow nets, named Superclass Extraction problem. We first gave a definition of the problem. Next we proposed a procedure to solve the problem on the basis of process mining technique. Then we gave an application of the proposed procedure.

A workflow may be extended to adapt to market growth, legal reform, and so on. The extended workflow must be logically correct, and inherit the behavior of the existing workflow. Even if the extended workflow inherits the behavior, it may be not logically correct. Can we modify it so that it satisfies not only behavioral inheritance but also logical correctness? This is named behavioral inheritance preserving soundizability problem. There are two kinds of behavioral inheritance: protocol inheritance and projection inheritance. In this paper, we tackled protocol inheritance preserving soundizability problem using a subclass of Petri nets called workflow nets. Limiting our analysis to acyclic free choice workflow nets, we formalized the problem. And we gave a necessary and sufficient condition on the problem, which is the existence of a key structure of free choice workflow nets called TP-handle. Based on this condition, we also constructed a polynomial time procedure to solve the problem.

A workflow net N may be extended as another workflow net N' by adding nodes and arcs. N' is intuitively called a subclass of N under protocol inheritance if we cannot distinguish those behaviors when removing the added transitions. Protocol inheritance problem is to decide whether N' is a subclass of N under protocol inheritance. It is known that the problem is decidable but is intractable. Even if N is a subnet of N', N' is not always a subclass of N under protocol inheritance. In this paper, limiting our analysis to protocol inheritance between acyclic extended free-choice workflow nets and their subnets, we gave a necessary and sufficient condition on the problem. Based on the condition, we also constructed a polynomial time procedure for solving the problem.

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.