Document Open Access Logo

The Power of the Filtration Technique for Modal Logics with Team Semantics

Author Martin Lück

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.31.pdf
  • Filesize: 0.62 MB
  • 20 pages

Document Identifiers

Author Details

Martin Lück

Cite AsGet BibTex

Martin Lück. The Power of the Filtration Technique for Modal Logics with Team Semantics. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CSL.2017.31

Abstract

Modal Team Logic (MTL) extends Väänänen's Modal Dependence Logic (MDL) by Boolean negation. Its satisfiability problem is decidable, but the exact complexity is not yet understood very well. We investigate a model-theoretical approach and generalize the successful filtration technique to work in team semantics. We identify an "existential" fragment of MTL that enjoys the exponential model property and is therefore, like Propositional Team Logic (PTL), complete for the class AEXP(poly). Moreover, superexponential filtration lower bounds for different fragments of MTL are proven, up to the full logic having no filtration for any elementary size bound. As a corollary, superexponential gaps of succinctness between MTL fragments of equal expressive power are shown.
Keywords
  • dependence logic,team logic,modal logic,finite model theory

Metrics

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

References

  1. Samson Abramsky and Jouko Väänänen. From IF to BI. Synthese, 167(2):207-230, 2009. URL: http://dx.doi.org/10.1007/s11229-008-9415-6.
  2. Ernest Allen Emerson. Temporal and modal logic. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science (Vol. B), pages 995-1072. MIT Press, Cambridge, MA, USA, 1990. URL: http://dl.acm.org/citation.cfm?id=114891.114907.
  3. Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal logic. Cambridge University Press, New York, NY, USA, 2001. Google Scholar
  4. Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114-133, January 1981. URL: http://dx.doi.org/10.1145/322234.322243.
  5. Brian A. Davey and Hilary A. Priestley. Introduction to Lattices and Order. Cambridge university press, 2002. Google Scholar
  6. 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, January 2012. URL: http://dx.doi.org/10.1016/j.apal.2011.08.005.
  7. Erich Grädel and Jouko Väänänen. Dependence and independence. Studia Logica, 101(2):399-410, 2013. Google Scholar
  8. Erich Grädel, Phokion G. Kolaitis, and Moshe Y. Vardi. On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic, 3(01):53-69, March 1997. URL: http://dx.doi.org/10.2307/421196.
  9. 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. URL: http://dx.doi.org/10.4204/EPTCS.226.14.
  10. Miika Hannula, Juha Kontinen, Jonni Virtema, and Heribert Vollmer. Complexity of Propositional Independence and Inclusion Logic. In Giuseppe F Italiano, Giovanni Pighizzini, and Donald T. Sannella, editors, Mathematical Foundations of Computer Science 2015, volume 9234, pages 269-280. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48057-1_21.
  11. Jaakko Hintikka and Gabriel Sandu. Informational Independence as a Semantical Phenomenon. In Studies in Logic and the Foundations of Mathematics, volume 126, pages 571-589. Elsevier, 1989. Google Scholar
  12. Wilfrid Hodges. Compositional semantics for a language of imperfect information. Logic Journal of IGPL, 5(4):539-563, July 1997. URL: http://dx.doi.org/10.1093/jigpal/5.4.539.
  13. Juha Kontinen, Julian-Steffen Müller, Henning Schnoor, and Heribert Vollmer. A Van Benthem Theorem for Modal Team Semantics. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany, pages 277-291, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2015.277.
  14. Martin Lück. Axiomatizations for Propositional and Modal Team Logic. In Jean-Marc Talbot and Laurent Regnier, editors, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), volume 62 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:18, Dagstuhl, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2016.33.
  15. Julian-Steffen Müller. Satisfiability and Model Checking in team based logics. PhD thesis, University of Hanover, 2014. URL: http://d-nb.info/1054741921.
  16. Jouko Väänänen. Modal dependence logic. New perspectives on games and interaction, 4:237-254, 2008. Google Scholar
  17. Jouko Väänänen. Dependence logic: a new approach to independence friendly logic. Number 70 in London Mathematical Society student texts. Cambridge University Press, Cambridge ; New York, 2007. Google Scholar
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 Imprint Privacy Contact