Papers for

knowledge representation engineers

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

Non-expansive fuzzy modal logic supports modular reasoning with uniform interpolation

Non-Expansive Fuzzy Modal Logic Has Uniform Interpolation

Abstract: Fuzzy logics with truth values in the unit interval vary in their choice of propositional connectives and their semantics, ranging from just minimum and maximum as in Zadeh logics to truncated addition and subtraction as in Łukasiewicz logics or their extensions with truth constants, known as Pavelka logics. In the more specific world of fuzzy modal logics, non-expansive fuzzy modal logic has recently been proposed as a sweet spot between Łukasiewicz (more precisely, Pavelka) and Zadeh fuzzy modal logic; it restricts Łukasiewicz propositional connectives to have one argument constant, equivalently extends the Zadeh propositional base with constant shift operators. It retains reasonable expressiveness both in practical terms and abstractly; in particular, it characterizes the standard notion of behavioural distance on fuzzy Kripke frames. At the same time, it allows for satisfiability checking in the same complexity as for its two-valued correspondent (the modal logic K, or the description logic ALC), in contrast to the notorious computational hardness of Łukasiewicz modal logic. In the present work, we show that non-expansive fuzzy modal logic admits uniform interpolation, a key property in modularization, information hiding, summarization, and other applications that fails for both Łukasiewicz (or Pavelka) and Zadeh modal logic.

Fri 23 OctLogic in Computer Science
The gist
Fuzzy modal logics let computers handle uncertain or in-between truth values, but some versions are either too complicated to use efficiently or lack useful properties. The authors focus on a middle-ground version called non-expansive fuzzy modal logic, which balances expressiveness and computational ease. They show this version has a useful feature called uniform interpolation, allowing parts of logical statements to be isolated or simplified without losing important information. This property helps with building and maintaining complex logical systems by supporting modular design and information hiding.
Open → 2610.32335v1

Modal logic extensions unify reasoning in generalized Nelson logics

Modal Extensions of Generalised Nelson Logics

Abstract: Motivated by relevant epistemic logic, we extend Dunn's simple Kripke-style binary relational semantics for the semi-relevant logic RM to fit a modal extension of RM. It is shown that the modal axioms and rules that need to be added to RM to obtain a sound and complete axiomatisation of its modal extension give an axiomatisation of modal extensions of all logics in the family of generalised Nelson logics, also studied by Dunn.

Wed 7 OctLogic in Computer Science
The gist
The authors study how to add modal reasoning—thinking about necessity and possibility—to a type of logic called RM, which models certain relevant relationships. They build on earlier work to create a system that accurately captures these modal ideas within RM and related Nelson logics. This work shows that the same rules used for the modal version of RM also work for other logics in this family, making it easier to handle modal concepts across different logical frameworks.
Open → 2610.10008v1