01.04.2016 | Original Article
Extracting unsatisfiable cores for LTL via temporal resolution
Erschienen in: Acta Informatica | Ausgabe 3/2016
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.