Paper Info
Title
Extracting Unsatisfiable Cores for LTL via Temporal Resolution
Abstract
Unsatisfiable cores (UCs) are a well established means for debugging in a declarative setting. Still, there are few tools that perform automated extraction of UCs for LTL. Existing tools compute a UC as an unsatisfiable subset of the set of top-level conjuncts of an LTL formula. Using resolution graphs to extract UCs is common in other domains such as SAT. In this article we construct and optimize resolution graphs for temporal resolution as implemented in the temporal resolution-based solver 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.
Year
DOI
Venue
2013
10.1109/TIME.2013.15
TIME '13 Proceedings of the 2013 20th International Symposium on Temporal Representation and Reasoning
Keywords
DocType
Volume
unsatisfiable core,temporal resolution-based solver,temporal resolution,extracting unsatisfiable cores,source code,declarative setting,automated extraction,propositional ltl,optimize resolution graph,resolution graph,temporal logic
Conference
abs/1212.3884
Issue
ISSN
Citations 
3
1432-0525
2
PageRank 
References 
Authors
0.35
63
1
Name
Order
Citations
PageRank
Viktor Schuppan140917.49