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.
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 |