Conservative extensions in guarded and two-variable fragments

DOI10.4230/LIPICS.ICALP.2017.108MaRDI QIDQ5111440zbMATH OpenOpenAlexFDO

Authors

Publication date 27 May 2020

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)

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.

Recommendations

• The triguarded fragment of first-order logic
• The guarded fragment with transitive guards
• STACS 2005
• Decidability of the Guarded Fragment with the Transitive Closure
• Conservative Extensions in Horn Description Logics with Inverse Roles

Cited in

(5)

• Query inseparability for \(\mathcal{ALC}\) ontologies
• Conservative extensions in modal logic
• Equivalence closure in the two-variable guarded fragment
• The triguarded fragment of first-order logic
• 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)