zbMATH — the first resource for mathematics

LTL with arithmetic and its applications in reasoning about hierarchical systems. (English) Zbl 1415.68144
Barthe, Gilles (ed.) et al., LPAR-22. 22nd international conference on logic for programming, artificial intelligence and reasoning, Awassa, Ethiopia, November 17–21, 2018. Selected papers. Manchester: EasyChair. EPiC Ser. Comput. 57, 343-362 (2018).
Summary: The computational bottleneck in model-checking applications is the blow-up involved in the translation of systems to their mathematical model. This blow up is especially painful in systems with variables over an infinite domain, and in composite systems described by means of their underlying components. We introduce and study linear temporal logic with arithmetic (LTLA), where formulas include variables that take values in \(\mathbb{Z}\), and in which linear arithmetic over these values is supported. We develop an automata-theoretic approach for reasoning about LTLA formulas and use it in order to solve, in PSPACE, the satisfiability problem for the existential fragment of LTLA and the model-checking problem for its universal fragment. We show that these results are tight, as a single universally-quantified variable makes the satisfiability problem for LTLA undecidable.
In addition to reasoning about systems with variables over \(\mathbb{Z}\), we suggest applications of LTLA in reasoning about hierarchical systems, which consist of subsystems that can call each other in a hierarchical manner. We use the values in \(\mathbb{Z}\) in order to describe the nesting depth of components in the system. A naive model-checking algorithm for hierarchical systems flattens them, which involves an exponential blow up. We suggest a model-checking algorithm that avoids the flattening and avoids a blow up in the number of components.
For the entire collection see [Zbl 1407.68021].

68Q60 Specification and verification (program logics, model checking, etc.)
03B44 Temporal logic
68Q45 Formal languages and automata
Full Text: DOI