Abstract
In this paper we prove that the uniform one-dimensional guarded fragment, which is a natural polyadic generalization of guarded two-variable logic, has the Craig interpolation property. We will also prove that the satisfiability problem of uniform guarded fragment is NExpTime-complete.
Chapter PDF
Similar content being viewed by others
References
Andréka, H., Németi, I., van Benthem, J.: Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic 27, 217–274 (1998)
Bárány, V., Benedikt, M., Cate, B.T.: Some model theory of guarded negation. The Journal of Symbolic Logic 83, 1307 – 1344 (2018)
Bell, J., Slomson, A.: Models and Ultraproducts: An Introduction. Dover Books on Mathematics Series, Dover Publications (2006)
van Benthem, J.: The many faces of interpolation. Synthese 164(3), 451–460 (2008)
Blackburn, P., Rijke, M.d., Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2001)
Gabbay, D.M.: Craig’s interpolation theorem for modal logics. In: Hodges, W. (ed.) Conference in Mathematical Logic — London ’70. pp. 111–127. Springer Berlin Heidelberg, Berlin, Heidelberg (1972)
Grädel, E.: On the restraining power of guards. Journal of Symbolic Logic 64(4), 1719–1742 (1999)
Grädel, E., Kolaitis, P., Vardi, M.: On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic 3(1), 53–69 (1997)
Hella, L., Kuusisto, A.: One-dimensional fragment of first-order logic. In: Advances in Modal Logic. vol. 10, pp. 274–293 (08 2014)
Herzig, A.: A new decidable fragment of first order logic. In: 3rd Logical Biennial Summer School and Conference in Honour of SC Kleene (1990)
Hoogland, E., Marx, M.: Interpolation and definability in guarded fragments. Studia Logica: An International Journal for Symbolic Logic 70(3), 373–409 (2002)
Jaakkola, R.: Ordered Fragments of First-Order Logic. In: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 202, pp. 62:1–62:14 (2021)
Jung, J.C., Wolter, F.: Living without beth and craig: Definitions and interpolants in the guarded and two-variable fragments. 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) pp. 1–14 (2021)
Kieronski, E.: One-Dimensional Logic over Words. In: 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 62, pp. 38:1–38:15 (2016)
Kieronski, E.: One-Dimensional Guarded Fragments. In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 138, pp. 16:1–16:14 (2019)
Kieronski, E., Kuusisto, A.: Complexity and expressivity of uniform one-dimensional fragment with equality. In: 39nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2014). Lecture Notes in Computer Science, vol. 8634, pp. 365–376 (2014)
Kierónski, E., Kuusisto, A.: Uniform One-Dimensional Fragments with One Equivalence Relation. In: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 41, pp. 597–615 (2015)
Kieronski, E., Kuusisto, A.: One-Dimensional Logic over Trees. In: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 83, pp. 64:1–64:13 (2017)
Marx, M.: Interpolation in modal logic. In: Proceedings of the 7th International Conference on Algebraic Methodology and Software Technology. p. 154–163. AMAST ’98, Springer-Verlag, Berlin, Heidelberg (1999)
Mogavero, F., Perelli, G.: Binding Forms in First-Order Logic. In: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 41, pp. 648–665 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2022 The Author(s)
About this paper
Cite this paper
Jaakkola, R. (2022). Uniform Guarded Fragments. In: Bouyer, P., Schröder, L. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2022. Lecture Notes in Computer Science, vol 13242. Springer, Cham. https://doi.org/10.1007/978-3-030-99253-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-99253-8_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-99252-1
Online ISBN: 978-3-030-99253-8
eBook Packages: Computer ScienceComputer Science (R0)