Towards formal analysis of artifact-centric business process models

Business process (BP) modeling is a building block for design and management of business processes. Two fundamental aspects of BP modeling are: a formal framework that well integrates both control flow and data, and a set of tools to assist all aspects of a BP life cycle. A typical BP life cycle includes at least a design phase where the key concerns are around “correct” realization of business logic in a resource constrained environment, and an operational phase where a main objective is to optimize and improve the realization during the execution (operation). This paper is an initial attempt to address both aspects of BP modeling. We view our investigation as a precursor to the development of a framework and tools that enable automated construction of processes, along the lines of techniques developed around OWL-S and Semantic Web Services.

Over the last decade, the idea of coupling control and data in an “artifact-centric” approach emerged in the practice of business process design. The key focus is on the “moving” data as they are manipulated throughout a process. The idea works well with many applications, typical examples include customer order processing, insurance claim handling, etc. Based on this idea, we formulate a theoretical model for artifact-centric business processes and develop complexity results concerning static analysis of three problems of immediate practical concerns. The problems focus on the ability to complete an execution, existence of an execution “deadend”, and redundancy. It is shown that the problems are undecidable in the general case; and under various restrictions they are decidable but complete in PSPACE, co-NP, and NP; and in some cases decidable in linear time.

By: Kamal Bhattacharya, Cagdas Gerede, Richard Hull, Rong Liu, Jianwen Su

Published in: RC24282 in 2007


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .