Conservative extensions in guarded and two-variable fragments

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

Authors:

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

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

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 (5)

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