Papers for

knowledge representation 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.

Modal style dependence logics extended and shown undecidable by reductions

Connecting Extended Modal Dependence Logics

Abstract: We consider three natural extensions of the basic decidable dependence logic LFD, adding, respectively, conditional dependence atoms, independence atoms, and identity atoms between variables. We show that these systems are all connected to first-order logic with identity by SAT reductions and in several cases also faithful translations. In particular, this implies that all these extended modal-style dependence logics are undecidable. This solves a number of problems left open in the original publication [1] introducing the LFD framework. The definitions and proofs presented here were found by ChatGPT and checked and streamlined as needed by the authors. At the end, we provide some discussion of what new things we learnt about dependence logics and about the methodology of using AI in logical research.

Mon 16 NovLogic in Computer Science
The gist
This paper studies logical systems that describe how variables depend on each other, which are important for reasoning in computer science. The authors look at three versions that add new types of dependence, like conditional dependence, independence, and identity between variables. They find connections between these logic systems and a well-known type of logic that includes equality, and show that these extended systems are undecidable—meaning there is no general algorithm to always decide their truth. They also discuss how AI tools helped discover and check their proofs.
Open → 2611.21287v1

Several logic systems between S4.2 and S4.3 explained by independence

On Some Logics Intermediate Between S4.2 and S4.3 Defined by the Notion of Independence

Abstract: Hamkins and Loewe described modal logic S4.2 through the notion of sets of independent buttons - statements that are possibly necessary - and switches - necessarily contingent statements. In this article we investigate logics intermediate between S4.2 and S4.3 that are defined through a different notion of independence. We provide an axiomatic description of such logics, state some basic facts and prove various completeness and decidability results.

Thu 29 OctLogic in Computer Science
The gist
The paper looks at a group of logical systems that sit between two known modal logics called S4.2 and S4.3. It builds on previous ideas that link these logics to concepts of 'independent buttons' and 'switches', which are special kinds of statements about what could be necessarily true or possibly changeable. The authors introduce a new notion of independence to define these intermediate logics, provide formal rules for them, and prove key facts about how complete and decidable these logics are. This work helps better understand the landscape of modal logics related to necessity and possibility.
Open → 2610.40800v1