Authors
Balder ten Cate
Jesse Comer
Date (dd-mm-yyyy)
2025
Title
Craig Interpolation for Decidable First-Order Fragments
Journal
Logical Methods in Computer Science
Volume
21
Publication Year
2025
Issue number
3
Document type
Article
Abstract

We show that the guarded-negation fragment is, in a precise sense, the smallest extension of the guarded fragment with Craig interpolation. In contrast, we show that full first-order logic is the smallest extension of both the two-variable fragment and the forward fragment with Craig interpolation. Similarly, we also show that all extensions of the two-variable fragment and of the fluted fragment with Craig interpolation are undecidable.

URL
go to publisher's site
Permalink
https://hdl.handle.net/11245.1/5deeb340-f8f2-43b2-bc4f-28a7e032578c