We consider the problem of the verification of an LTL specification \(\varphi \) on a system S given some prior knowledge K, an LTL formula that S is known to satisfy. The automata-theoretic approach to LTL model checking is implemented as an emptiness check of the product \(S\otimes A_{\lnot \varphi }\) where \(A_{\lnot \varphi }\) is an automaton for the negation of the property. We propose new operations that simplify an automaton \(A_{\lnot \varphi }\) given some knowledge automaton \(A_K\) , to produce an automaton B that can be used instead of \(A_{\lnot \varphi }\) for more efficient model checking. Our evaluation of these operations on a large benchmark derived from the MCC’22 competition shows that even with simple knowledge, half of the problems can be definitely answered without running an LTL model checker, and the remaining problems can be simplified significantly.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Simplifying LTL Model Checking Given Prior Knowledge

  • Alexandre Duret-Lutz,
  • Denis Poitrenaud,
  • Yann Thierry-Mieg

摘要

We consider the problem of the verification of an LTL specification \(\varphi \) on a system S given some prior knowledge K, an LTL formula that S is known to satisfy. The automata-theoretic approach to LTL model checking is implemented as an emptiness check of the product \(S\otimes A_{\lnot \varphi }\) where \(A_{\lnot \varphi }\) is an automaton for the negation of the property. We propose new operations that simplify an automaton \(A_{\lnot \varphi }\) given some knowledge automaton \(A_K\) , to produce an automaton B that can be used instead of \(A_{\lnot \varphi }\) for more efficient model checking. Our evaluation of these operations on a large benchmark derived from the MCC’22 competition shows that even with simple knowledge, half of the problems can be definitely answered without running an LTL model checker, and the remaining problems can be simplified significantly.