Document Open Access Logo

Two-variable Logic with Counting and a Linear Order

Authors Witold Charatonik, Piotr Witkowski

PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.631.pdf
  • Filesize: 0.66 MB
  • 17 pages

Document Identifiers

Author Details

Witold Charatonik
Piotr Witkowski

Cite As Get BibTex

Witold Charatonik and Piotr Witkowski. Two-variable Logic with Counting and a Linear Order. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 631-647, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CSL.2015.631

Abstract

We study the finite satisfiability problem for the two-variable fragment of the first-order logic extended with counting quantifiers (C2) and interpreted over linearly ordered structures. We show that the problem is undecidable in the case of two linear orders (in presence of two other binary symbols). In the case of one linear order it is NEXPTIME-complete, even in presence of the successor relation. Surprisingly, the complexity of the problem explodes when we add one binary symbol more: C2 with one linear order and its successor, in presence of other binary predicate symbols, is decidable, but it is as expressive (and as complex) as Vector Addition Systems.

Subject Classification

Keywords
  • Two-variable logic
  • counting quantifiers
  • linear order
  • satisfiability
  • complexity

Metrics

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

References

  1. Mikolaj Bojanczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin, and Claire David. Two-variable logic on words with data. In LICS, pages 7-16. IEEE Computer Society, 2006. Google Scholar
  2. Witold Charatonik, Emanuel Kieronski, and Filip Mazowiecki. Satisfiability of the two-variable fragment of first-order logic over trees. CoRR, abs/1304.7204, 2013. Google Scholar
  3. Witold Charatonik, Emanuel Kieroński, and Filip Mazowiecki. Decidability of weak logics with deterministic transitive closure. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS'14, Vienna, Austria, July 14-18, 2014, page 29, 2014. Google Scholar
  4. Witold Charatonik and Piotr Witkowski. Two-variable logic with counting and trees. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, pages 73-82, 2013. Google Scholar
  5. Kousha Etessami, Moshe Y. Vardi, and Thomas Wilke. First-order logic with two variables and unary temporal logic. Inf. Comput., 179(2):279-295, 2002. Google Scholar
  6. Diego Figueira. Satisfiability for two-variable logic with two successor relations on finite linear orders. Computing Research Repository, abs/1204.2495, 2012. Google Scholar
  7. E. Grädel, M. Otto, and E. Rosen. Undecidability results on two-variable logics. Archive for Mathematical Logic, 38:213-354, 1999. Google Scholar
  8. 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
  9. Erich Grädel and Martin Otto. On logics with two variables. Theor. Comput. Sci., 224(1-2):73-113, 1999. Google Scholar
  10. Erich Grädel, Martin Otto, and Eric Rosen. Two-variable logic with counting is decidable. In LICS, pages 306-317. IEEE Computer Society, 1997. Google Scholar
  11. N. Immerman, A. Rabinovich, T. Reps, M.Sagiv, and G. Yorsh. The boundary between decidability and undecidability for transitive-closure logics. In Proceedings of the 18th Annual Conference of the European Association for Computer Science Logic (CSL'04), pages 160-174, 2004. Google Scholar
  12. Emanuel Kieroński. Decidability issues for two-variable logics with several linear orders. In Marc Bezem, editor, CSL, volume 12 of LIPIcs, pages 337-351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011. Google Scholar
  13. Emanuel Kieroński and Jakub Michaliszyn. Two-variable universal logic with transitive closure. In Patrick Cégielski and Arnaud Durand, editors, CSL, volume 16 of LIPIcs, pages 396-410. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. Google Scholar
  14. Emanuel Kieroński, Jakub Michaliszyn, Ian Pratt-Hartmann, and Lidia Tendera. Two-variable first-order logic with equivalence closure. In LICS, pages 431-440. IEEE, 2012. Google Scholar
  15. Emanuel Kieroński and Martin Otto. Small substructures and decidability issues for first-order logic with two variables. In LICS, pages 448-457. IEEE Computer Society, 2005. Google Scholar
  16. Emanuel Kieroński and Lidia Tendera. On finite satisfiability of two-variable first-order logic with equivalence relations. In LICS, pages 123-132. IEEE Computer Society, 2009. Google Scholar
  17. S. Rao Kosaraju. Decidability of reachability in vector addition systems (preliminary version). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 267-281, 1982. Google Scholar
  18. Jérôme Leroux. The general vector addition system reachability problem by presburger inductive invariants. In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, pages 4-13, 2009. Google Scholar
  19. R. J. Lipton. The reachability problem requires exponential space. 62, New Haven, Connecticut: Yale University, Department of Computer Science, Research, Jan, 1976. Google Scholar
  20. Amaldev Manuel. Two variables and two successors. In Petr Hlinený and Antonín Kucera, editors, MFCS, volume 6281 of Lecture Notes in Computer Science, pages 513-524. Springer, 2010. Google Scholar
  21. Amaldev Manuel and Thomas Zeume. Two-variable logic on 2-dimensional structures. In Simona Ronchi Della Rocca, editor, Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2-5, 2013, Torino, Italy, volume 23 of LIPIcs, pages 484-499. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. Google Scholar
  22. Ernst W. Mayr. An algorithm for the general Petri net reachability problem. SIAM J. Comput., 13(3):441-460, 1984. Google Scholar
  23. Michael Mortimer. On languages with two variables. Mathematical Logic Quarterly, 21(1):135-140, 1975. Google Scholar
  24. B. O. Nash. Reachability problems in vector addition systems. The American Mathematical Monthly, 80(3):pp. 292-295, 1973. Google Scholar
  25. Martin Otto. Two variable first-order logic over ordered domains. J. Symb. Log., 66(2):685-702, 2001. Google Scholar
  26. Leszek Pacholski, Wieslaw Szwast, and Lidia Tendera. Complexity of two-variable logic with counting. In LICS, pages 318-327. IEEE, 1997. Google Scholar
  27. 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
  28. Ian Pratt-Hartmann. The two-variable fragment with counting revisited. In Anuj Dawar and Ruy J. G. B. de Queiroz, editors, WoLLIC, volume 6188 of Lecture Notes in Computer Science, pages 42-54. Springer, 2010. Google Scholar
  29. Ian Pratt-Hartmann. Logics with counting and equivalence. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS'14, Vienna, Austria, July 14-18, 2014, page 76, 2014. Google Scholar
  30. Thomas Schwentick and Thomas Zeume. Two-variable logic with two order relations - (extended abstract). In Anuj Dawar and Helmut Veith, editors, CSL, volume 6247 of Lecture Notes in Computer Science, pages 499-513. Springer, 2010. Google Scholar
  31. Dana Scott. A decision method for validity of sentences in two variables. Journal of Symbolic Logic, 27:477, 1962. Google Scholar
  32. Luc Segoufin. Automata and logics for words and trees over an infinite alphabet. In Proceedings of CSL 2006, volume 4207 of Lecture Notes in Computer Science, pages 41-57. Springer, 2006. Google Scholar
  33. Wieslaw Szwast and Lidia Tendera. FO² with one transitive relation is decidable. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 317-328, Dagstuhl, Germany, 2013. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. 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 About DROPS Imprint Privacy Contact