pith. sign in

arxiv: 1705.10115 · v1 · pith:VDZ7TC2Wnew · submitted 2017-05-29 · 💻 cs.LO

Conservative Extensions in Guarded and Two-Variable Fragments

classification 💻 cs.LO
keywords fragmentconservativeextensionsfragmentsguardedtwo-variablecomplexitycomputational
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.