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.
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· Journal of Logic and Computa...· 0 citations
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
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...
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.· Proceedings of the ACM on Pr...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.