On Complexity of Verifying Nested Workflows with Extra Constraints

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On Complexity of Verifying Nested Workflows with Extra Constraints

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On Complexity of Verifying Nested Workflows with Extra Constraints

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F10%2F1188" target="_blank" >GAP202/10/1188: KnowSched: Znalostní techniky v rozvrhování</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of 4th International Conference on Agents and Artificial Intelligence (ICAART 2012), Volume 1

ISBN

978-989-8425-95-9

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

346-354

Název nakladatele

SciTePress

Místo vydání

Rome

Místo konání akce

Vilamoura, Portugal

Datum konání akce

6. 2. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—