The paper addresses the difficulty of generating abductive explanations for boolean classifiers, a key challenge in explainable AI. It demonstrates that even with efficient representations like Ordered Binary Decision Diagrams, many classes of abductive explanations remain computationally hard. The authors propose using a dual‑rail encoding of the classifier to enable efficient computation of these hard explanation classes.
By Arthur Ledaguenel, Florent Capelli, Jean-Marie Lagniez
arXiv:2609. 19077v1 Announce Type: cross Abstract: Formal explainability provides mathematically grounded justifications for individual predictions.
By Frederic Koriche, Jean-Marie Lagniez, Chi Tran
arXiv:2601. 18747v2 Announce Type: replace-cross Abstract: Modern AI agents increasingly rely on search infrastructure to execute complex, neuro-symbolic reasoning workflows.
By Amir Aavani
arXiv:2509. 24808v2 Announce Type: replace Abstract: Explaining why a language model produces a particular output requires local, input-level explanations.
By Tung-Yu Wu, Fazl Barez
arXiv:2607. 16715v1 Announce Type: new Abstract: We study Controlled Query Evaluation (CQE), a declarative approach to confidentiality-preserving data access, in the context of Description Logic (DL) ontologies, and for confidentiality policies expressed through Epistemic Dependencies (EDs).
By Lorenzo Marconi, Daniela Rieti, Riccardo ROsati
arXiv:2606. 24279v1 Announce Type: new Abstract: In Description Logics (DLs), reasoning under Rational Closure (RC) is a well-known and widely accepted non-monotonic formalism to handle defeasible knowledge.
By Giovanni Casini (CNR - ISTI, University of Cape Town), Umberto Straccia (CNR - ISTI)
arXiv:2604. 26976v2 Announce Type: replace-cross Abstract: We study the problem of fitting a description logic (DL) ontology to a given set of positive and negative examples that take the form of an ABox and a Boolean query.
By Marvin Grosser, Carsten Lutz
In Description Logics (DLs), reasoning under Rational Closure (RC) is a well-known and widely accepted non-monotonic formalism to handle defeasible knowledge. In this paper, we study the application of RC to the core and horn variants of the DL-Lite family of lightweight description logics.
arXiv:2608. 14004v1 Announce Type: new Abstract: In-context learning is commonly formalized as inference from examples of a function.
By Faizanuddin Ansari, Debanjan Dutta, Swagatam Das
The paper investigates whether large language models (LLMs) follow Occam's Razor when performing inductive and abductive reasoning. It introduces a synthetic framework for generating questions that require both types of reasoning and a new automated metric to evaluate the simplicity and correctness of generated hypotheses. Experiments show that while LLMs can handle simple scenarios, they struggle with complex world models and producing high‑quality, simplest hypotheses, even when using advanced reasoning techniques.
By Yunxin Sun, Abulhair Saparov
arXiv:2607. 21183v1 Announce Type: cross Abstract: The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation.
By Johannes Schmidt (J\"onk\"oping University), Mohamed Maizia (J\"onk\"oping University, Link\"oping University), Victor Lagerkvist (Link\"oping University), Johannes K. Fichte (Link\"oping University)
The paper presents an interactive probabilistically checkable proof (PCP) protocol that allows a polynomial‑time verifier to check the approximate consistency of a probabilistic predictor defined by two circuits, P and Q. By evaluating these circuits at a few points and querying a proof oracle that encodes a witnessing probability distribution, the verifier can confirm that the predictor’s many conditional‑probability claims are self‑consistent. The authors also establish that the problem of verifying l₂‑approximate consistency for explicit probabilistic claims lies in NP, with certificates of size O(mn + log B), and show how to eliminate dependence on the input bit‑precision B through a small additive gap.
By Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser