Conservative Extensions in Guarded and Two-Variable Fragments


Jung, Jean Christoph, Lutz, Carsten, Martel, Mauricio, Schneider, Thomas and Wolter, Frank (2017) Conservative Extensions in Guarded and Two-Variable Fragments. Leibniz International Proceedings in Informatics, LIPIcs, 80.

[img] 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: 19 Jan 2023 06:53
DOI: 10.4230/LIPIcs.ICALP.2017.108
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3009643
Dimensions
Altmetric
CORE (COnnecting REpositories)