LIPIcs.MFCS.2021.62.pdf
- Filesize: 0.7 MB
- 14 pages
Document
Ordered Fragments of First-Order Logic
Author
-
Part of:
Volume:
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-18
File
Document Identifiers
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 AsGet 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
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)
0PDF Downloads
References
-
Bartosz Bednarczyk. Exploiting forwardness: Satisfiability and query-entailment in forward guarded fragment. In JELIA, pages 179-193. Springer, 2021.
-
Erich Grädel. On the restraining power of guards. The Journal of Symbolic Logic, 64(4):1719-1742, 1999.
-
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.
-
Andreas Herzig. A new decidable fragment of first order logic. In 3rd Logical Biennial Summer School and Conference in Honour of SC Kleene, 1990.
-
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.
- 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.
- 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.
- Emanuel Kieronski. One-dimensional guarded fragments. arXiv Preprint, 2019. URL: http://arxiv.org/abs/1904.04572.
-
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.
- Antti Kuusisto. On games and computation. arXiv Preprint, 2019. URL: http://arxiv.org/abs/1910.14603.
-
Martin Otto. Two variable first-order logic over ordered domains. The Journal of Symbolic Logic, 66(2):685-702, 2001.
-
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.
-
Ian Pratt-Hartmann, Wiesław Szwast, and Lidia Tendera. The fluted fragment revisited. The Journal of Symbolic Logic, 84(3):1020-1048, 2019.
- Ian Pratt-Hartmann and Lidia Tendera. The fluted fragment with transitive relations. arXiv Preprint, 2020. URL: http://arxiv.org/abs/2006.11169.
-
Willard V Quine. Variables explained away. Proceedings of the american philosophical society, 104(3):343-347, 1960.
-
WV Quine. Predicate functors revisited. The Journal of Symbolic Logic, 46(3):649-652, 1981.
-
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.