Document Open Access Logo

Complexity Classifications via Algebraic Logic

Authors Reijo Jaakkola , Antti Kuusisto

PDF
Thumbnail PDF

File

LIPIcs.CSL.2023.27.pdf
  • Filesize: 0.8 MB
  • 18 pages

Document Identifiers

Author Details

Reijo Jaakkola
  • Tampere University, Finland
Antti Kuusisto
  • Tampere University, Finland
  • University of Helsinki, Finland

Funding

The authors were funded by the Academy of Finland project Theory of computational logics, grant numbers 324435, 328987 (to December 2021) and 352419, 352420, 353027 (2022 onwards).
  • Jaakkola, Reijo: Academy of Finland project Theory of Computational Logics, grant 328987
  • Kuusisto, Antti: Academy of Finland project Theory of Computational Logics, grants 324435, 328987, 352419, 352420, 353027

Cite AsGet BibTex

Reijo Jaakkola and Antti Kuusisto. Complexity Classifications via Algebraic Logic. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.CSL.2023.27

Abstract

Complexity and decidability of logics is an active research area involving a wide range of different logical systems. We introduce an algebraic approach to complexity classifications of computational logics. Our base system GRA, or general relation algebra, is equiexpressive with first-order logic FO. It resembles cylindric algebra but employs a finite signature with only seven different operators, thus also giving a very succinct characterization of the expressive capacities of first-order logic. We provide a comprehensive classification of the decidability and complexity of the systems obtained by limiting the allowed sets of operators of GRA. We also discuss variants and extensions of GRA, and we provide algebraic characterizations of a range of well-known decidable logics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic
Keywords
  • Decidability
  • complexity
  • algebraic logic
  • fragments of first-order logic

Metrics

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

Related Versions

References

  1. Hajnal Andréka, István Németi, and Johan van Benthem. Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27(3):217-274, 1998. Google Scholar
  2. Franz Baader, Ralf Küsters, and Frank Wolter. Extensions to description logics. In Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors, The Description Logic Handbook: Theory, Implementation, and Applications, pages 219-261. Cambridge University Press, 2003. Google Scholar
  3. John Bacon. The completeness of a predicate-functor logic. Journal of Symbolic Logic, 50:903-921, 1985. Google Scholar
  4. Vince Bárány, Balder ten Cate, and Luc Segoufin. Guarded negation. Journal of the ACM, 62(3):22:1-22:26, 2015. Google Scholar
  5. Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieronski, Rastislav Lenhardt, Filip Mazowiecki, and James Worrell. Complexity of two-variable logic on finite trees. ACM Transactions on Computational Logic, 17(4):32:1-32:38, 2016. Google Scholar
  6. Johan Van Benthem. Dynamic bits and pieces. ILLC research report, University of Amsterdam, 1997. Google Scholar
  7. Egon Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer, 1997. Google Scholar
  8. Witold Charatonik and Piotr Witkowski. Two-variable logic with counting and trees. ACM Transactions on Computational Logic, 17(4):31:1-31:27, 2016. Google Scholar
  9. Edgar F. Codd. Relational completeness of data base sublanguages. Research Report / RJ / IBM / San Jose, California, RJ987, 1972. Google Scholar
  10. Erich Grädel. Invited talk: Decision procedures for guarded logics. In Harald Ganzinger, editor, Automated Deduction - CADE-16, 16th International Conference on Automated Deduction, Proceedings, volume 1632 of Lecture Notes in Computer Science, pages 31-51. Springer, 1999. Google Scholar
  11. Erich Grädel. On the restraining power of guards. Journal of Symbolic Logic, 64(4):1719-1742, 1999. Google Scholar
  12. Erich Grädel, Phokion Kolaitis, and Moshe Vardi. On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic, 3(1):53-69, 1997. Google Scholar
  13. Erich Grädel, Martin Otto, and Eric Rosen. Two-variable logic with counting is decidable. In Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science LICS, pages 306-317. IEEE, 1997. Google Scholar
  14. Lauri Hella and Antti Kuusisto. One-dimensional fragment of first-order logic. In Rajeev Goré, Barteld P. Kooi, and Agi Kurucz, editors, Invited and contributed papers from the tenth conference on "Advances in Modal Logic" AiML, pages 274-293. College Publications, 2014. Google Scholar
  15. Jelle Hellings, Catherine L. Pilachowski, Dirk Van Gucht, Marc Gyssens, and Yuqing Wu. From relation algebra to semi-join algebra: An approach to graph query optimization. The Computer Journal, 64(5):789-811, 2021. Google Scholar
  16. Robin Hirsch and Ian Hodkinson. Relation algebras by games. North Holland, 2002. Google Scholar
  17. Reijo Jaakkola. Ordered Fragments of First-Order Logic. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 62:1-62:14, 2021. Google Scholar
  18. Reijo Jaakkola and Antti Kuusisto. Algebraic classifications for fragments of first-order logic and beyond. CoRR, abs/2005.01184v1, 2020. Google Scholar
  19. Reijo Jaakkola and Antti Kuusisto. Algebraic classifications for fragments of first-order logic and beyond. arXiv Preprint, arXiv:2005.01184v2, 2021. Google Scholar
  20. Emanuel Kieronski and Antti Kuusisto. Complexity and expressivity of uniform one-dimensional fragment with equality. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS, Proceedings, Part I, volume 8634 of LNCS, pages 365-376. Springer, 2014. Google Scholar
  21. Emanuel Kieronski, Jakub Michaliszyn, Ian Pratt-Hartmann, and Lidia Tendera. Two-variable first-order logic with equivalence closure. SIAM Journal on Computing, 43(3):1012-1063, 2014. Google Scholar
  22. Emanuel Kieronski, Ian Pratt-Hartmann, and Lidia Tendera. Equivalence closure in the two-variable guarded fragment. J. Log. Comput., 27(4):999-1021, 2017. Google Scholar
  23. Steven T. Kuhn. An axiomatization of predicate functor logic. Notre Dame Journal of Formal Logic, 24:233-241, 1983. Google Scholar
  24. Antti Kuusisto. On games and computation. CoRR, abs/1910.14603, 2019. Google Scholar
  25. Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz, and Jan Van den Bussche. The semijoin algebra and the guarded fragment. Journal of Logic, Language and Information, 14(3):331-343, 2005. Google Scholar
  26. Per Lindström. First order predicate logic with generalized quantifiers. Theoria, 32(3):186-195, 1966. Google Scholar
  27. Leopold Löwenheim. Über möglichkeiten im relativkalkül. Matematische Annalen, 76(4):447-470, 1915. Google Scholar
  28. Carsten Lutz, Ulrike Sattler, and Frank Wolter. Modal logic and the two-variable fragment. In Laurent Fribourg, editor, Computer Science Logic, 15th International Workshop, CSL, 2001. Google Scholar
  29. Amaldev Manuel and Thomas Zeume. Two-variable logic on 2-dimensional structures. In Simona Ronchi Della Rocca, editor, Computer Science Logic 2013 (CSL 2013), volume 23 of LIPIcs, pages 484-499. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. Google Scholar
  30. Maarten Marx. Tolerance logic. Journal of Logic, Language and Information, 10(3):353-374, 2001. Google Scholar
  31. S. Ju. Maslov. The inverse method for establishing deducibility for logical calculi. In V. P. Orevkov, editor, Logical and logical-mathematical calculus. Part I, Trudy Mat. Inst. Steklov, volume 98, pages 26-87. Public, 1968. Google Scholar
  32. Fabio Mogavero and Giuseppe Perelli. Binding forms in first-order logic. In Stephan Kreutzer, editor, 24th EACSL Annual Conference on Computer Science Logic, CSL, volume 41 of LIPIcs, pages 648-665, 2015. Google Scholar
  33. Michael Mortimer. Reasoning about strategies: On the model-checking problem. Mathematical Logic Quarterly, 21(1), 1975. Google Scholar
  34. Andrdzej Mostowski. On a generalization of quantifiers. Fundamenta Mathematicae, 44(1):12-36, 1957. Google Scholar
  35. Leszek Pacholski, Wieszlaw Szwast, and Lidia Tendera. Complexity of two-variable logic with counting. In Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science LICS, pages 318-327. IEEE, 1997. Google Scholar
  36. Ian Pratt-Hartmann. Complexity of the two-variable fragment with counting quantifiers. Journal of Logic, Language and Information, 14(3):369-395, 2005. Google Scholar
  37. Ian Pratt-Hartmann, Wieslaw Szwast, and Lidia Tendera. The fluted fragment revisited. Journal of Symbolic Logic, 84(3):1020-1048, 2019. Google Scholar
  38. Willard Van Quine. Toward a calculus of concepts. The Journal of Symbolic Logic, I:2-25, 1936. Google Scholar
  39. Willard Van Quine. Variables explained away. In Proceedings of the American Philosophical Society, 1960. Google Scholar
  40. Willard Van Quine. On the limits of decision. In Proceedings of the 14th International Congress of Philosophy, volume III, pages 57-62. University of Vienna, 1969. Google Scholar
  41. Willard Van Quine. Algebraic logic and predicate functors. In Logic and Art, pages 214-238. Bobbs-Merrill, Indianapolis, Indiana, 1972. Google Scholar
  42. Luc Segoufin and Balder ten Cate. Unary negation. Logical Methods in Computer Science, 9(3), 2013. Google Scholar
  43. Szymon Torunczyk and Thomas Zeume. Register automata with extrema constraints, and an application to two-variable logic. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 873-885. ACM, 2020. Google Scholar
  44. Marco Voigt. A fine-grained hierarchy of hard problems in the separated fragment. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pages 1-12. IEEE, 2017. 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