Document Open Access Logo

Decidability of Predicate Logics with Team Semantics

Authors Juha Kontinen, Antti Kuusisto, Jonni Virtema

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2016.60.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • team semantics
  • dependence logic
  • complexity
  • two-variable logic

Metrics

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

Abstract

We study the complexity of predicate logics based on team semantics.
We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIME-complete. Furthermore, we show that the validity problem of two-variable dependence logic is undecidable, thereby solving an open problem from the team semantics literature. We also briefly analyse the complexity of the Bernays-Schoenfinkel-Ramsey prefix classes of dependence logic.

Cite As Get BibTex

Juha Kontinen, Antti Kuusisto, and Jonni Virtema. Decidability of Predicate Logics with Team Semantics. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.60

Author Details

Juha Kontinen
Antti Kuusisto
Jonni Virtema

References

  1. Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieroński, Rastislav Lenhardt, Filip Mazowiecki, and James Worrell. Complexity of two-variable logic on finite trees. In ICALP (2), pages 74-88, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39212-2_10.
  2. R. Berger. The undecidability of the domino problem. Memoirs of the American Mathematical Society, 66:369-395, 1966. Google Scholar
  3. Egon Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer, 1997. Google Scholar
  4. Witold Charatonik and Piotr Witkowski. Two-variable logic with counting and trees. In LICS, pages 73-82. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/LICS.2013.12.
  5. A. Durand, J. Kontinen, and H. Vollmer. Expressivity and Complexity of Dependence Logic, in Dependence Logic: Theory and Applications. Springer, In Press, 2016. Google Scholar
  6. Pietro Galliani. Inclusion and exclusion dependencies in team semantics - on some logics of imperfect information. Ann. Pure Appl. Logic, 163(1):68-84, 2012. URL: http://dx.doi.org/10.1016/j.apal.2011.08.005.
  7. Pietro Galliani and Lauri Hella. Inclusion logic and fixed point logic. In proceedings of CSL 2013, pages 281-295, 2013. Google Scholar
  8. Erich Grädel. Model-checking games for logics of imperfect information. Theor. Comput. Sci., 493:2-14, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.10.033.
  9. Erich Grädel, Phokion G. Kolaitis, and Moshe Y. Vardi. On the decision problem for two-variable first-order logic. The Bulletin of Symbolic Logic, 3(1):53-69, 1997. URL: http://www.jstor.org/stable/421196.
  10. Erich Grädel, Martin Otto, and Eric Rosen. Undecidability results on two-variable logics. In Proceedings of STACS'97, pages 249-260, London, UK, 1997. Springer-Verlag. Google Scholar
  11. 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.
  12. Miika Hannula. Hierarchies in inclusion logic with lax semantics. In Mohua Banerjee and Shankara Narayanan Krishna, editors, Logic and Its Applications: 6th Indian Conference, ICLA 2015, Mumbai, India, January 8-10, 2015. Proceedings, pages 100-118, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-662-45824-2_7.
  13. Lauri Hella and Antti Kuusisto. One-dimensional fragment of first-order logic. In Advances in Modal Logic 10, invited and contributed papers from the tenth conference on "Advances in Modal Logic," held in Groningen, The Netherlands, August 5-8, 2014, pages 274-293, 2014. URL: http://www.aiml.net/volumes/volume10/Hella-Kuusisto.pdf.
  14. Jaakko Hintikka and Gabriel Sandu. Informational independence as a semantical phenomenon. In J. E. Fenstad, I. T. Frolov, and R. Hilpinen, editors, Logic, Methodology and Philosophy of Science VIII, volume 126, pages 571-589. Elsevier, Amsterdam, 1989. Google Scholar
  15. Wilfrid Hodges. Compositional semantics for a language of imperfect information. Log. J. IGPL, 5(4):539-563 (electronic), 1997. Google Scholar
  16. Emanuel Kieroński, Jakub Michaliszyn, Ian Pratt-Hartmann, and Lidia Tendera. Two-variable first-order logic with equivalence closure. SIAM Journal of Computing, 43(3):1012-1063, 2014. Google Scholar
  17. Jarmo Kontinen. Coherence and computational complexity of quantifier-free dependence logic formulas. Studia Logica, 101(2):267-291, 2013. URL: http://dx.doi.org/10.1007/s11225-013-9481-8.
  18. Juha Kontinen, Antti Kuusisto, Peter Lohmann, and Jonni Virtema. Complexity of two-variable dependence logic and IF-logic. Inf. Comput., 239:237-253, 2014. URL: http://dx.doi.org/10.1016/j.ic.2014.08.004.
  19. Juha Kontinen, Antti Kuusisto, and Jonni Virtema. Decidability of predicate logics with team semantics. CoRR, abs/1410.5037, 2016. URL: http://arxiv.org/abs/1410.5037.
  20. Antti Kuusisto. A double team semantics for generalized quantifiers. Journal of Logic, Language and Information, 24(2):149-191, 2015. URL: http://dx.doi.org/10.1007/s10849-015-9217-4.
  21. Per Lindström. First order predicate logic with generalized quantifiers. Theoria, 32:186-195, 1966. Google Scholar
  22. Leszek Pacholski, Wieslaw Szwast, and Lidia Tendera. Complexity of two-variable logic with counting. In Proceedings of LICS'97, pages 318-327, 1997. URL: http://dx.doi.org/10.1109/LICS.1997.614958.
  23. Ian Pratt-Hartmann. Complexity of the two-variable fragment with counting quantifiers. Journal of Logic, Language and Information, 14(3):369-395, 2005. URL: http://dx.doi.org/10.1007/s10849-005-5791-1.
  24. Wieslaw Szwast and Lidia Tendera. FO² with one transitive relation is decidable. In STACS, pages 317-328, 2013. Google Scholar
  25. Jouko Väänänen. Dependence logic: A new approach to independence friendly logic. Number 70 in London Mathematical Society student texts. Cambridge University Press, 2007. Google Scholar
  26. Jonni Virtema. Approaches to Finite Variable Dependence: Expressiveness and Computational Complexity. PhD thesis, University of Tampere, 2014. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact