Control-Flow Modeling with Declare: Behavioral Properties, Computational Complexity, and Tools
Valeria Fionda, Antonella Guzzo · IEEE Transactions on Knowledge and Data Engineering · 2019
Declarative approaches to control-flow modeling use logic-based languages to formalize a number of constraints that valid traces must satisfy. The most noticeable example is the DECLARE framework based on linear temporal logic. Despite the interest that DECLARE has been attracting, the current knowledge about its formal properties was rather limited. The goal of this paper is to fill this gap by: (i) analyzing the behavioral properties of DECLARE by comparing it with the modeling capabilities of traditional procedural design approaches, in particular, block-structured processes; (ii) analyzing DECLARE from the computational point of view. As for the former point, we identify both the block-structured processes constructs that can be simulated in DECLARE and the features of DECLARE that can be encoded in block-structured processes. As for the latter point, we show that checking whether a given set of DECLARE patterns admits a satisfying trace is an NP-hard problem. In particular, we identify some DECLARE specifications whose satisfying traces are all of exponential length and some useful DECLARE fragments where a satisfying trace whose length is polynomially bounded is guaranteed to exist. The paper also discusses the declare2sat prototype system and the results of a thorough experimental validation.