Replication, refinement & reachability: complexity in dynamic condition-response graphs

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Replication, refinement & reachability : complexity in dynamic condition-response graphs. / Debois, Søren; Hildebrandt, Thomas T.; Slaats, Tijs.

In: Acta Informatica, Vol. 55, 2018, p. 489–520.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Debois, S, Hildebrandt, TT & Slaats, T 2018, 'Replication, refinement & reachability: complexity in dynamic condition-response graphs', Acta Informatica, vol. 55, pp. 489–520. https://doi.org/10.1007/s00236-017-0303-8

APA

Debois, S., Hildebrandt, T. T., & Slaats, T. (2018). Replication, refinement & reachability: complexity in dynamic condition-response graphs. Acta Informatica, 55, 489–520. https://doi.org/10.1007/s00236-017-0303-8

Vancouver

Debois S, Hildebrandt TT, Slaats T. Replication, refinement & reachability: complexity in dynamic condition-response graphs. Acta Informatica. 2018;55:489–520. https://doi.org/10.1007/s00236-017-0303-8

Author

Debois, Søren ; Hildebrandt, Thomas T. ; Slaats, Tijs. / Replication, refinement & reachability : complexity in dynamic condition-response graphs. In: Acta Informatica. 2018 ; Vol. 55. pp. 489–520.

Bibtex

@article{1de1ddf4e71c46ddb65b94ee35dd61f1,
title = "Replication, refinement & reachability: complexity in dynamic condition-response graphs",
abstract = "We explore the complexity of reachability and run-time refinement under safety and liveness constraints in event-based process models. Our study is framed in the DCR? process language, which supports modular specification through a compositional operational semantics. DCR?encompasses the “Dynamic Condition Response (DCR) graphs” declarative process model for analysis, execution and safe run-time refinement of process-aware information systems;including replication of sub-processes. We prove that event-reachability and refinement are np-hard for DCR? processes without replication, and that these finite state processes recognise exactly the languages that are the union of a regular and an ω-regular language. Moreover, we prove that eventreachability and refinement are undecidable in general for DCR? processes with replication and local events, and we provide a tractable approximation for refinement. A prototype implementation of the DCR ⋆ language is available at http://dcr.tools/acta16",
author = "S{\o}ren Debois and Hildebrandt, {Thomas T.} and Tijs Slaats",
year = "2018",
doi = "10.1007/s00236-017-0303-8",
language = "English",
volume = "55",
pages = "489–520",
journal = "Acta Informatica",
issn = "0001-5903",
publisher = "Springer",

}

RIS

TY - JOUR

T1 - Replication, refinement & reachability

T2 - complexity in dynamic condition-response graphs

AU - Debois, Søren

AU - Hildebrandt, Thomas T.

AU - Slaats, Tijs

PY - 2018

Y1 - 2018

N2 - We explore the complexity of reachability and run-time refinement under safety and liveness constraints in event-based process models. Our study is framed in the DCR? process language, which supports modular specification through a compositional operational semantics. DCR?encompasses the “Dynamic Condition Response (DCR) graphs” declarative process model for analysis, execution and safe run-time refinement of process-aware information systems;including replication of sub-processes. We prove that event-reachability and refinement are np-hard for DCR? processes without replication, and that these finite state processes recognise exactly the languages that are the union of a regular and an ω-regular language. Moreover, we prove that eventreachability and refinement are undecidable in general for DCR? processes with replication and local events, and we provide a tractable approximation for refinement. A prototype implementation of the DCR ⋆ language is available at http://dcr.tools/acta16

AB - We explore the complexity of reachability and run-time refinement under safety and liveness constraints in event-based process models. Our study is framed in the DCR? process language, which supports modular specification through a compositional operational semantics. DCR?encompasses the “Dynamic Condition Response (DCR) graphs” declarative process model for analysis, execution and safe run-time refinement of process-aware information systems;including replication of sub-processes. We prove that event-reachability and refinement are np-hard for DCR? processes without replication, and that these finite state processes recognise exactly the languages that are the union of a regular and an ω-regular language. Moreover, we prove that eventreachability and refinement are undecidable in general for DCR? processes with replication and local events, and we provide a tractable approximation for refinement. A prototype implementation of the DCR ⋆ language is available at http://dcr.tools/acta16

U2 - 10.1007/s00236-017-0303-8

DO - 10.1007/s00236-017-0303-8

M3 - Journal article

VL - 55

SP - 489

EP - 520

JO - Acta Informatica

JF - Acta Informatica

SN - 0001-5903

ER -

ID: 192391691