Journal
ACTA INFORMATICA
Volume 55, Issue 6, Pages 489-520Publisher
SPRINGER
DOI: 10.1007/s00236-017-0303-8
Keywords
-
Categories
Funding
- Velux foundation [33295]
- Danish Council for Independent Research [DFF-6111-00337]
- Innovation Fund Denmark
Ask authors/readers for more resources
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 at-regular language. Moreover, we prove that event-reachability 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/actal6.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available