Specifying and Reasoning about Workflows with Path Constraints

Wenfei Fan, Scott Weinstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution


One of the most common frameworks for specifying workflows is control flow graph [3,11,13,22]. Although a control flow graph can depict local execution dependencies of the tasks in a workflow, it is not capable of expressing global dependencies and is not helpful in reasoning about workflow properties. Recently, a path constraint theory has been developed for semistructured data [2,7,8,9,10]. It has proven useful for semantic specification and query optimization in the database context. To overcome the limitations of flow control graphs, this paper generalizes the path constraint theory to specify and analyze workflows. More specifically, it proposes a path constraint language and shows that both local and global dependencies, as well as sub-workflows, can be naturally expressed in the language. This allows one to reason about workflows in the traditional logic framework. The paper also establishes the decidability of several verification problems associated with workflows.
Original languageEnglish
Title of host publicationInternet Applications
Subtitle of host publication5th International Computer Science Conference, ICSC'99, Hong Kong, China, December 13-15, 1999, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages10
ISBN (Electronic)978-3-540-46652-9
ISBN (Print)978-3-540-66903-6
Publication statusPublished - 1999

Fingerprint Dive into the research topics of 'Specifying and Reasoning about Workflows with Path Constraints'. Together they form a unique fingerprint.

Cite this