Modal style dependence logics extended and shown undecidable by reductions
Connecting Extended Modal Dependence Logics
Logic in Computer Science
Summary
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.
What this means in practice
- •For automated reasoning engineers: Understand limits of automated reasoning tools for modal dependence logics with new atom types due to their undecidability.
- •For knowledge representation developers: Avoid using these extended dependence logic variants in systems requiring guaranteed decision procedures, since they are undecidable.
A theory result. No direct application yet.
Authors
Johan van Benthem, Chenwei Shi, Wenfei Ouyang
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.