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 phases of a BP life cycle. 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, an artifact-centric approach of coupling control and data emerged in the practice of BP design. It focuses on the “moving” data as they are manipulated
throughout a process. In this paper, we formulate a formal model for artifact-centric business processes and develop complexity
results concerning static analysis of three problems of immediate practical concerns, which focus on the ability to complete
an execution, existence of an execution “deadend”, and redundancy. We show that the problems are undecidable in general, but
under various restrictions they are decidable but complete in pspace, co-np, and np; and in some cases decidable in linear time.