Papers for

diagnostic system developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Choosing observations to ensure explanations in Horn logic models

Choosing What to Observe: Higher-Order Obstructions in Horn Abduction

Abstract: An explanation may exist in every complete context yet be impossible to select from the information observed. We study this distinction in finite propositional Horn abduction with integrity constraints. Observations are sufficient when each report admits one hypothesis set that is consistent and entails the manifestation in every compatible context. We characterize sufficiency by minimal context families with no common explanation. Their variable spans form a canonical hypergraph whose transversals are exactly the sufficient observation sets. The characterization recovers classical discernibility for unique explanations and supports composition across independent components. Minimal obstructions have unbounded cardinality even for acyclic rules, while rectangular explanation families admit a tight bound given by their largest choice domain. With circuit-defined contexts, sufficiency is $Π_3^P$-complete and selecting at most $k$ observable variables is $Σ_4^P$-complete, already for unrestricted contexts and acyclic rules. The selection reduction makes observation choices enforce globally fixed existential commitments. Explicit contexts reduce both tasks to NP-complete problems; tabulated explanation families make sufficiency polynomial. These results connect explanatory choice, information requirements, and representation cost.

Fri 23 OctLogic in Computer Science
The gist
Sometimes, you can explain something in many ways, but it’s hard to pick the right explanation from what you observe. The authors study a type of logical reasoning called Horn abduction with rules and constraints, looking at which pieces of information you must observe so that an explanation can be found and uniquely selected. They identify conditions when observations are enough to guarantee a sensible explanation across all scenarios, and show that picking these observations can be very complex. Their results connect how to choose what to observe with how hard it is to explain something and how complex the information you store is.
Open → 2610.32805v1