Towards Formal Analysis of Artifact-Centric Process Models

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 concering static analysis of three problems of immediate pratical 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.