Conservative Extensions in Guarded and Two-Variable Fragments.

DOI10.4230/LIPICS.ICALP.2017.108zbMATH Open1442.03006arXiv1705.10115OpenAlexW2962905563MaRDI QIDQ5111440FDOQ5111440

Author name not available (Why is that?)

Publication date: 27 May 2020

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 2ExpTime-complete in the intersection GF${}^2$ of FO${}^2$ and GF.

Full work available at URL: https://arxiv.org/abs/1705.10115

zbMATH Keywords

computational complexityconservative extensionsdecidable fragments of first-order logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (3)

• Query inseparability for \(\mathcal{ALC}\) ontologies
• Equivalence closure in the two-variable guarded fragment
• Logical separability of labeled data examples under ontologies

This page was built for publication: Conservative Extensions in Guarded and Two-Variable Fragments.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111440)