Document Open Access Logo

Validity and Entailment in Modal and Propositional Dependence Logics

Author Miika Hannula

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.28.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Author Details

Miika Hannula

Cite As Get BibTex

Miika Hannula. Validity and Entailment in Modal and Propositional Dependence Logics. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.28

Abstract

The computational properties of modal and propositional dependence logics have been extensively studied over the past few years, starting from a result by Sevenster showing NEXPTIME-completeness of the satisfiability problem for modal dependence logic. Thus far, however, the validity and entailment properties of these logics have remained uncharacterised to a great extent. This paper establishes a complete classification of the complexity of validity and entailment in modal and propositional dependence logics. In particular, we address the question of the complexity of validity in modal dependence logic. By showing that it is NEXPTIME-complete we refute an earlier conjecture proposing a higher complexity for the problem.

Subject Classification

Keywords
  • modal logic
  • propositional logic
  • dependence logic
  • entailment
  • validity
  • complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981. URL: http://dx.doi.org/10.1145/322234.322243.
  2. Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC'71, pages 151-158, New York, NY, USA, 1971. ACM. Google Scholar
  3. Johannes Ebbing, Lauri Hella, Arne Meier, Julian-Steffen Müller, Jonni Virtema, and Heribert Vollmer. Extended modal dependence logic. In Logic, Language, Information, and Computation - 20th International Workshop, WoLLIC 2013, Darmstadt, Germany, August 20-23, 2013. Proceedings, pages 126-137, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39992-3_13.
  4. Johannes Ebbing and Peter Lohmann. Complexity of model checking for modal dependence logic. In Mária Bieliková, Gerhard Friedrich, Georg Gottlob, Stefan Katzenbeisser, and György Turán, editors, SOFSEM 2012: Theory and Practice of Computer Science, volume 7147 of Lecture Notes in Computer Science, pages 226-237. Springer, 2012. Google Scholar
  5. Pietro Galliani. Inclusion and exclusion dependencies in team semantics: On some logics of imperfect information. Annals of Pure and Applied Logic, 163(1):68-84, 2012. Google Scholar
  6. Pietro Galliani, Miika Hannula, and Juha Kontinen. Hierarchies in independence logic. In Computer Science Logic 2013 (CSL 2013), volume 23, pages 263-280, 2013. Google Scholar
  7. Erich Grädel and Jouko Väänänen. Dependence and independence. Studia Logica, 101(2):399-410, 2013. URL: http://dx.doi.org/10.1007/s11225-013-9479-2.
  8. Miika Hannula, Juha Kontinen, Martin Lück, and Jonni Virtema. On quantified propositional logics and the exponential time hierarchy. In Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2016, Catania, Italy, 14-16 September 2016., pages 198-212, 2016. Google Scholar
  9. Miika Hannula, Juha Kontinen, Jonni Virtema, and Heribert Vollmer. Complexity of propositional independence and inclusion logic. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I, pages 269-280, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48057-1_21.
  10. Lauri Hella, Antti Kuusisto, Arne Meier, and Heribert Vollmer. Modal inclusion logic: Being lax is simpler than being strict. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I, pages 281-292, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48057-1_22.
  11. Lauri Hella, Kerkko Luosto, Katsuhiko Sano, and Jonni Virtema. The expressive power of modal dependence logic. In Advances in Modal Logic 10, invited and contributed papers from the 10th Conference on "Advances in Modal Logic," held in Groningen, The Netherlands, August 5-8, 2014, pages 294-312, 2014. Google Scholar
  12. Lauri Hella and Johanna Stumpf. The expressive power of modal logic with inclusion atoms. In Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2015, Genoa, Italy, 21-22nd September 2015., pages 129-143, 2015. URL: http://dx.doi.org/10.4204/EPTCS.193.10.
  13. Leon Henkin. Some Remarks on Infinitely Long Formulas. In Infinitistic Methods. Proc. Symposium on Foundations of Mathematics, pages 167-183. Pergamon Press, 1961. Google Scholar
  14. Jaakko Hintikka and Gabriel Sandu. Informational independence as a semantic phenomenon. In J. E. Fenstad, I. T. Frolov, and R. Hilpinen, editors, Logic, methodology and philosophy of science, pages 571-589. Elsevier, 1989. Google Scholar
  15. Wilfrid Hodges. Compositional Semantics for a Language of Imperfect Information. Journal of the Interest Group in Pure and Applied Logics, 5 (4):539-563, 1997. Google Scholar
  16. Juha Kontinen, Julian-Steffen Müller, Henning Schnoor, and Heribert Vollmer. Modal independence logic. In Advances in Modal Logic 10, invited and contributed papers from the 10th Conference on "Advances in Modal Logic," held in Groningen, The Netherlands, August 5-8, 2014, pages 353-372, 2014. Google Scholar
  17. Andreas Krebs, Arne Meier, and Jonni Virtema. A team based variant of CTL. In 22nd International Symposium on Temporal Representation and Reasoning, TIME 2015, Kassel, Germany, September 23-25, 2015, pages 140-149, 2015. Google Scholar
  18. Richard E. Ladner. The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput., 6(3):467-480, 1977. URL: http://dx.doi.org/10.1137/0206033.
  19. Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115-116, 1973. Google Scholar
  20. Peter Lohmann and Heribert Vollmer. Complexity results for modal dependence logic. Studia Logica, 101(2):343-366, 2013. Google Scholar
  21. Martin Lück. Complete problems of propositional logic for the exponential hierarchy. CoRR, abs/1602.03050, 2016. URL: http://arxiv.org/abs/1602.03050.
  22. Julian-Steffen Müller and Heribert Vollmer. Model checking for modal dependence logic: An approach through post’s lattice. In Logic, Language, Information, and Computation - 20th International Workshop, WoLLIC 2013, Darmstadt, Germany, August 20-23, 2013. Proceedings, pages 238-250, 2013. Google Scholar
  23. Gary L. Peterson, John H. Reif, and Salman Azhar. Lower bounds for multiplayer noncooperative games of incomplete information. Computers &Mathematics with Applications, 41(7-8):957-992, April 2001. Google Scholar
  24. Katsuhiko Sano and Jonni Virtema. Axiomatizing propositional dependence logics. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany, pages 292-307, 2015. Google Scholar
  25. Merlijn Sevenster. Model-theoretic and computational properties of modal dependence logic. Journal of Logic and Computation, 19(6):1157-1173, 2009. Google Scholar
  26. Jouko Väänänen. Dependence Logic. Cambridge University Press, 2007. Google Scholar
  27. Jouko Väänänen. Modal Dependence Logic. In Krzysztof R. Apt and Robert van Rooij, editors, New Perspectives on Games and Interaction. Amsterdam University Press, Amsterdam, 2008. Google Scholar
  28. Jonni Virtema. Complexity of validity for propositional dependence logics. In Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2014, Verona, Italy, September 10-12, 2014., pages 18-31, 2014. Google Scholar
  29. Jonni Virtema. Complexity of validity for propositional dependence logics. Inf. Comput., 253:224-236, 2017. URL: http://dx.doi.org/10.1016/j.ic.2016.07.008.
  30. F. Yang. Modal Dependence Logics: Axiomatizations and Model-theoretic Properties. ArXiv e-prints, October 2016. URL: http://arxiv.org/abs/1610.02710.
  31. Fan Yang. On extensions and variants of dependence logic. PhD thesis, University of Helsinki, 2014. Google Scholar
  32. Fan Yang and Jouko Väänänen. Propositional logics of dependence. Annals of Pure and Applied Logic, 167(7):557-589, 2016. URL: http://dx.doi.org/10.1016/j.apal.2016.03.003.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact