On Complexity of Verifying Nested Workflows with Extra Constraints
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10129790" target="_blank" >RIV/00216208:11320/12:10129790 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.5220/0003748003460354" target="_blank" >http://dx.doi.org/10.5220/0003748003460354</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5220/0003748003460354" target="_blank" >10.5220/0003748003460354</a>
Alternative languages
Result language
angličtina
Original language name
On Complexity of Verifying Nested Workflows with Extra Constraints
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F10%2F1188" target="_blank" >GAP202/10/1188: KnowSched: Knowledge Techniques in Scheduling</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 4th International Conference on Agents and Artificial Intelligence (ICAART 2012), Volume 1
ISBN
978-989-8425-95-9
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
346-354
Publisher name
SciTePress
Place of publication
Rome
Event location
Vilamoura, Portugal
Event date
Feb 6, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—