The Expressive Power of Modal Dependence Logic

Abstract

We study the expressive power of various modal logics with team semantics. We show that exactly the properties of teams that are downward closed and closed under team k-bisimulation, for some finite k, are definable in modal logic extended with intuitionistic disjunction. Furthermore, we show that the expressive power of modal logic with intuitionistic disjunction and extended modal dependence logic coincide. Finally we establish that any translation from extended modal dependence logic into modal logic with intuitionistic disjunction increases the size of some formulas exponentially.

arXiv comment19 pages

References in corpus (2)

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

Cited by in corpus (9)

• Propositional Logics of Dependence
• Propositional Team Logics
• Possibility Frames and Forcing for Modal Logic
• The expressive power of modal logic with inclusion atoms
• Structural completeness in propositional logics of dependence
• Modal Dependence Logics: Axiomatizations and Model-theoretic Properties
• Validity and Entailment in Modal and Propositional Dependence Logics
• On the Succinctness of Atoms of Dependency
• Diversity, Dependence and Independence