Skip to content
Open access

Computing Coverage-Based Prime Implicant Explanations for Tree-Based Models

Sep 2026 · IJCAI/ECAI · pp. 4143-4151 · 0 citations · 31 references
Computer Science

TL;DR

This paper presents a greedy algorithm to derive coverage-based prime implicant explanations when dealing with a tree-based model and presents an empirical evaluation showing that this algorithm is efficient enough to be used in many practical cases.

Abstract

Coverage-based prime implicant explanations are formal explanations offering a number of valuable assets, especially in terms of faithfulness and generality. Unfortunately, deriving a coverage-based prime implicant explanation for an instance is computationally hard in the general case (the problem of identifying such an explanation being at the second level of the polynomial hierarchy). In this paper, we focus on the computation of a coverage-based prime implicant explanation for an instance given a tree-based model. We show that the specific nature of the domain theory linking the Boolean conditions in such models makes the problem computationally easier. We present a greedy algorithm to derive coverage-based prime implicant explanations when dealing with a tree-based model. We also present an empirical evaluation showing that this algorithm is efficient enough to be used in many practical cases.

Read PDF

Similar papers

Open access Nov 2026

Single-world counterfactual reasoning in ProbLog

This work makes complex counterfactual reasoning more computationally tractable and reliable, providing a crucial step towards developing more robust and explainable AI systems.

Saimun Habib, Vaishak Belle, Feng-Xiang He · 0 citations
Preprint Oct 2026

Symbolic Execution of Constrained Horn Clauses

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR...

Johannes Weiser, Zafer Esen, P. Rümmer · 0 citations
Preprint Oct 2026

Associativity of Multiplication Is Hard for Resolution

SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this phenomenon. CDCL SAT solvers implicitly search for resolution proofs, and no lower bound on proof size has ruled out the existence of short proofs that solvers...

Vincent Liew · 0 citations
Open access Oct 2026

LLM-Assisted Unsatisfiability Proofs for Satisfiability Modulo Theories, Oracles, and Natural Language

NLUnsat is presented, an SMT solver capable of producing proofs of unsatisfiability for first-order theories that include closed-box function calls, and an extension of the SMT-LIB language is introduced that operates over this extended syntax to find unsatisfiability proofs on SMT-LIB formulas with closed-box function...

Gourav Takhar, S. Lahiri, P. Kalita et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.