ON COMPLEXITY OF VERIFYING NESTED WORKFLOWS WITH EXTRA CONSTRAINTS

Roman Barták

2012

Abstract

Workflow is a formal description of a process or processes. There exist tools for interactive and visual editing of workflows such as the FlowOpt Workflow Editor. During manual editing of workflows, it is common to introduce flaws such as cycles of activities. Hence one of the required features of workflow management tools is verification of workflows, which is a problem of deciding whether the workflow describes processes that can be realized in practice. In this paper we deal with the theoretical complexity of verifying workflows with a nested structure and with extra constraints. The nested structure forces users to create valid workflows but as we shall show, introduction of extra causal, precedence, and temporal synchronization constraints makes the problem of deciding whether the workflow represents a realizable process hard. In particular, we will show that this problem is NP-complete.

Paper Citation

in Harvard Style

Barták R. (2012). ON COMPLEXITY OF VERIFYING NESTED WORKFLOWS WITH EXTRA CONSTRAINTS . In Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8425-95-9, pages 346-354. DOI: 10.5220/0003748003460354

in Bibtex Style

@conference{icaart12,
author={Roman Barták},
title={ON COMPLEXITY OF VERIFYING NESTED WORKFLOWS WITH EXTRA CONSTRAINTS},
booktitle={Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2012},
pages={346-354},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003748003460354},
isbn={978-989-8425-95-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - ON COMPLEXITY OF VERIFYING NESTED WORKFLOWS WITH EXTRA CONSTRAINTS
SN - 978-989-8425-95-9
AU - Barták R.
PY - 2012
SP - 346
EP - 354
DO - 10.5220/0003748003460354