Document Open Access Logo

Ordered Fragments of First-Order Logic

Author Reijo Jaakkola

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.62.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Author Details

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

Funding

The research leading to this work was supported by the Academy of Finland grants 324435 and 328987.

Acknowledgements

The author wishes to thank Antti Kuusisto for many helpful discussions on fragments of first-order logic. The author also wishes to thank the anonymous reviewers for their valuable suggestions concerning the exposition of the motivation and the context of the present work.

Cite As Get BibTex

Reijo Jaakkola. Ordered Fragments of First-Order Logic. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.62

Abstract

Using a recently introduced algebraic framework for classifying fragments of first-order logic, we study the complexity of the satisfiability problem for several ordered fragments of first-order logic, which are obtained from the ordered logic and the fluted logic by modifying some of their syntactical restrictions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic
Keywords
  • ordered logic
  • fluted logic
  • complexity
  • decidability

Metrics

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

Related Versions

References

  1. Bartosz Bednarczyk. Exploiting forwardness: Satisfiability and query-entailment in forward guarded fragment. In JELIA, pages 179-193. Springer, 2021. Google Scholar
  2. Erich Grädel. On the restraining power of guards. The Journal of Symbolic Logic, 64(4):1719-1742, 1999. Google Scholar
  3. 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(1):53-69, 1997. Google Scholar
  4. Andreas Herzig. A new decidable fragment of first order logic. In 3rd Logical Biennial Summer School and Conference in Honour of SC Kleene, 1990. Google Scholar
  5. Ullrich Hustadt, Renate A Schmidt, and Lilia Georgieva. A survey of decidable first-order fragments and description logics. Journal of Relational Methods in Computer Science, 1(251-276):3, 2004. Google Scholar
  6. Reijo Jaakkola and Antti Kuusisto. Algebraic classifications for fragments of first-order logic and beyond. arXiv Preprint, 2020. URL: http://arxiv.org/abs/2005.01184v1.
  7. Reijo Jaakkola and Antti Kuusisto. Algebraic classifications for fragments of first-order logic and beyond. arXiv Preprint, 2021. URL: http://arxiv.org/abs/2005.01184v2.
  8. Emanuel Kieronski. One-dimensional guarded fragments. arXiv Preprint, 2019. URL: http://arxiv.org/abs/1904.04572.
  9. Emanuel Kieroński and Antti Kuusisto. Complexity and expressivity of uniform one-dimensional fragment with equality. In International Symposium on Mathematical Foundations of Computer Science, pages 365-376. Springer, 2014. Google Scholar
  10. Antti Kuusisto. On games and computation. arXiv Preprint, 2019. URL: http://arxiv.org/abs/1910.14603.
  11. Martin Otto. Two variable first-order logic over ordered domains. The Journal of Symbolic Logic, 66(2):685-702, 2001. Google Scholar
  12. Ian Pratt-Hartmann. Fluted logic with counting. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  13. Ian Pratt-Hartmann, Wiesław Szwast, and Lidia Tendera. The fluted fragment revisited. The Journal of Symbolic Logic, 84(3):1020-1048, 2019. Google Scholar
  14. Ian Pratt-Hartmann and Lidia Tendera. The fluted fragment with transitive relations. arXiv Preprint, 2020. URL: http://arxiv.org/abs/2006.11169.
  15. Willard V Quine. Variables explained away. Proceedings of the american philosophical society, 104(3):343-347, 1960. Google Scholar
  16. WV Quine. Predicate functors revisited. The Journal of Symbolic Logic, 46(3):649-652, 1981. Google Scholar
  17. Wieslaw Szwast and Lidia Tendera. On the decision problem for the guarded fragment with transitivity. In Proceedings 16th Annual IEEE Symposium on Logic in Computer Science, pages 147-156. IEEE, 2001. 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