Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice

Julian-Steffen Müller, Heribert Vollmer

Introduction

Model checking is a fundamental task in computer science, used to verify if a mathematical model of a system satisfies a given property. While standard propositional modal logic is computationally efficient, Modal Dependence Logic (MDL)—which introduces the dependence atom $dep(\cdot)$ to express functional relationships—significantly increases complexity. This paper provides a complete classification of the model checking problem for MDL fragments extended with arbitrary Boolean connectives, identifying the specific logical "building blocks" that determine computational difficulty.

Methodology: Team Semantics and Post's Lattice

To analyze MDL, the researchers utilize team semantics. Unlike classical semantics that evaluate formulas at single states, team semantics evaluate formulas over sets of states ("teams"). This is necessary because dependency is a property of a collection of data points rather than a single instance; one cannot observe a functional dependency within a single state.

The core of the classification relies on Post’s Lattice, a mathematical structure that categorizes all possible sets of Boolean functions (clones). Instead of testing infinite combinations of logic gates, the authors analyzed seven specific "base" cases (such as the set containing only AND, or the set containing only XOR). Because these clones form a lattice, proving a result for a base case allows it to be generalized to any logic fragment built from those connectives.

Post's Lattice of Boolean clones, showing the relationships between different sets of logical connectives.

Key Insights: The Tipping Points of Complexity

The study reveals that the complexity of model checking is highly sensitive to the choice of modalities and Boolean connectives:

  • The Universal Modality ($\Box$): If a fragment only uses the universal modality ("in all reachable states"), model checking remains in NL (Nondeterministic Logarithmic space), making it highly efficient regardless of the Boolean gates used.
  • The Existential Modality ($\Diamond$): The inclusion of the existential modality ("there exists a reachable state") serves as the primary engine of complexity, pushing the problem into higher complexity classes.
  • The XOR Threshold: A critical finding is that fragments capable of simulating the exclusive-or (XOR) operation reach PSPACE-completeness. This is because XOR allows the logic to encode the branching structure of Quantified Boolean Formulas (QBF), a classic PSPACE-hard problem.

Results and Complexity Landscape

The authors successfully mapped the complexity of MDL model checking across the entire lattice of Boolean clones. The classification identifies three primary "hard" zones when the $\Diamond$ modality is present, as visualized in the colored mapping of the lattice.

Extracted figure from page 7 of Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice

As shown in the figure, the complexity classes are distributed as follows:

  • NP-complete (Yellow): Fragments using monotone gates like AND ($\land$) and OR ($\lor$).
  • $P^{NP[1]}$-complete (Green): Fragments using negation ($\neg$) but lacking XOR.
  • PSPACE-complete (Red): Fragments containing linear gates like XOR ($\oplus$) or the full set of Boolean functions (BF).

Conclusion

This research provides a definitive map of the computational costs associated with different fragments of Modal Dependence Logic. While it covers all classical Boolean connectives, the authors note that a full classification including "non-classical" connectives—such as splitjunction or intuitionistic implication—remains an open challenge for future work in team semantics.

Summary updated

Abstract

In this paper we investigate an extended version of modal dependence logic by allowing arbitrary Boolean connectives. Modal dependence logic was recently introduced by Jouko V\"a\"an\"anen by extending modal logic by a the dependence atom dep(.). In this paper we study the computational complexity of the model checking problem. For a complete classification of arbitrary Boolean functions we are using a Lattice approach introduced by Emil Post. This classification is done for all fragments of the logical language allowing modalities $\Diamond$ and $\Box$, the dependence atom, and logical symbols for arbitrary Boolean functions.
BibTeX
@inproceedings{muller2013model,
  author = {Julian-Steffen Müller and Heribert Vollmer},
  title = {{Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice}},
  booktitle = {WoLLIC},
  year = {2013},
  doi = {10.1007/978-3-642-39992-3\_21},
}
Figure