Studia Logica 101 (2):343-366 (2013)

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using ${\wedge, \square, \lozenge}$ (i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster
Keywords Dependence logic  Modal logic  Satisfiability problem  Computational complexity  Poor man’s logic
Categories (categorize this paper)
DOI 10.1007/s11225-013-9483-6
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 49,987
Through your library

References found in this work BETA

From If to Bi.Samson Abramsky & Jouko Väänänen - 2009 - Synthese 167 (2):207 - 230.

Add more references

Citations of this work BETA

Propositional Logics of Dependence.Fan Yang & Jouko Väänänen - 2016 - Annals of Pure and Applied Logic 167 (7):557-589.
The Expressive Power of Modal Dependence Logic.Lauri Hella, Kerkko Luosto, Katsuhiko Sano & Jonni Virtema - 2014 - In Rajeev Goré, Barteld Kooi & Agi Kurucz (eds.), Advances in Modal Logic, Volume 10. CSLI Publications. pp. 294-312.
Propositional Team Logics.Fan Yang & Jouko Väänänen - 2017 - Annals of Pure and Applied Logic 168 (7):1406-1441.

View all 8 citations / Add more citations

Similar books and articles

On Definability in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2009 - Journal of Logic, Language and Information 18 (3):317-332.
Generalized Quantifiers in Dependence Logic.Fredrik Engström - 2012 - Journal of Logic, Language and Information 21 (3):299-324.
Epistemic Operators in Dependence Logic.Pietro Galliani - 2013 - Studia Logica 101 (2):367-397.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Fragments of Language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.
Lewis Dichotomies in Many-Valued Logics.Simone Bova - 2012 - Studia Logica 100 (6):1271-1290.
A Remark on Negation in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2011 - Notre Dame Journal of Formal Logic 52 (1):55-65.
An Event-Based Fragment of First-Order Logic Over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.


Added to PP index

Total views
30 ( #320,974 of 2,324,058 )

Recent downloads (6 months)
4 ( #234,248 of 2,324,058 )

How can I increase my downloads?


My notes