Conservative Extensions in Guarded and Two-Variable Fragments

Jung, Jean Christoph, Lutz, Carsten, Martel, Mauricio, Schneider, Thomas and Wolter, Frank ORCID: 0000-0002-4470-606X (2017) Conservative Extensions in Guarded and Two-Variable Fragments. Leibniz International Proceedings in Informatics Lipics, 80. ISSN 1868-8969

Text 1705.10115v1.pdf - Author Accepted Manuscript Download (442kB)

Abstract

We investigate the decidability and computational complexity of (deductive) conservative extensions in fragments of first-order logic (FO), with a focus on the two-variable fragment FO$^2$ and the guarded fragment GF. We prove that conservative extensions are undecidable in any FO fragment that contains FO$^2$ or GF (even the three-variable fragment thereof), and that they are decidable and 2\ExpTime-complete in the intersection GF$^2$ of FO$^2$ and GF.

Item Type:	Article
Additional Information:	Full version of paper accepted at ICALP 2017
Uncontrolled Keywords:	cs.LO, cs.LO
Depositing User:	Symplectic Admin
Date Deposited:	26 Sep 2017 09:54
Last Modified:	05 Jun 2025 19:50
DOI:	10.4230/LIPIcs.ICALP.2017.108
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3009643