01-04-2016 | Original Article
Extracting unsatisfiable cores for LTL via temporal resolution
Published in: Acta Informatica | Issue 3/2016
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
TRP++
, and we use them to extract UCs for propositional LTL. The resulting UCs are more fine-grained than the UCs obtained from existing tools because UC extraction also simplifies top-level conjuncts instead of treating them as atomic entities. For example, given an unsatisfiable LTL formula of the form \( \phi \equiv {(\mathbf{G}{ \psi })}\wedge {\mathbf{F}{ \psi ' }}\) existing tools return \( \phi \) as a UC irrespective of the complexity of \( \psi \) and \( \psi ' \), whereas the approach presented in this article continues to remove parts not required for unsatisfiability inside \( \psi \) and \( \psi ' \). Our approach also identifies groups of occurrences of a proposition that do not interact in a proof of unsatisfiability. We implement our approach in TRP++
. Our experimental evaluation demonstrates that our approach (i) extracts UCs that are often significantly smaller than the input formula with an acceptable overhead and (ii) produces more fine-grained UCs than competing tools while remaining at least competitive in terms of run time and memory usage. The source code of our tool is publicly available.