From model completeness to verification of data aware processes. (English) Zbl 1443.68103

Lutz, Carsten (ed.) et al., Description logic, theory combination, and all that. Essays dedicated to Franz Baader on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 11560, 212-239 (2019).
Summary: Model completeness is a classical topic in model-theoretic algebra, and its inspiration sources are areas like algebraic geometry and field theory. Yet, recently, there have been remarkable applications in computer science: these applications range from combined decision procedures for satisfiability and interpolation, to connections between temporal logic and monadic second order logic and to model-checking. In this paper we mostly concentrate on the last one: we study verification over a general model of so-called artifact-centric systems, which are used to capture business processes by giving equal important to the control-flow and data-related aspects. In particular, we are interested in assessing (parameterized) safety properties irrespectively of the initial database instance. We view such artifact systems as array-based systems, establishing a correspondence with model checking based on Satisfiability Modulo Theories (SMT). Model completeness comes into the picture in this framework by supplying quantifier elimination algorithms for suitable existentially closed structures. Such algorithms, whose complexity is unexpectedly low in some cases of our interest, are exploited during search and to represent the sets of reachable states. Our first implementation, built up on top of the mcmt model-checker, makes all our foundational results fully operational and quite effective, as demonstrated by our first experiments.
For the entire collection see [Zbl 1428.68036].


68Q60 Specification and verification (program logics, model checking, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI