Towards a notion of unsatisfiable and unrealizable cores for LTL

Unsatisfiable cores, i.e., parts of an unsatisfiable formula that are themselves unsatisfiable, have important uses in debugging specifications, speeding up search in model checking or SMT, and generating certificates of unsatisfiability. While unsatisfiable cores have been well investigated for Boolean SAT and constraint programming, the notion of unsatisfiable cores for temporal logics such as LTL has not received much attention. In this paper we investigate notions of unsatisfiable cores for LTL that arise from the syntax tree of an LTL formula, from converting it into a conjunctive normal form, and from proofs of its unsatisfiability. The resulting notions are more fine-grained than existing ones. We illustrate the benefits of the more fine-grained notions on examples from the literature. We extend some of the notions to realizability and we discuss the relationship of unsatisfiable and unrealizable cores with the notion of vacuity.

Research highlights
► We propose and compare notions of unsatisfiable cores for LTL.
► Notions are based on syntax trees, conjunctive normal forms, and tableaux.
► Examples from the literature clearly show benefits compared to previous notions.
► Some notions are extended to unrealizable cores.
► We relate the notion of cores to that of vacuity.