2024/04/03 by Frank Wolter, Wolter, Frank, Michael Zakharyaschev +1 · 1 citation
Computer Science · Psychology · #03B45 (Primary) 03C40 (Secondary) #Advanced Algebra and Logic #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Philosophy and Theoretical Science
paper · pdf · doi:10.48550/arxiv.2404.02683
openalex publication_date 2024/04/03 · openalex created_date 2024/04/06 · openalex updated_date 2026/07/28
The interpolant existence problem (IEP) for a logic L is to decide, given formulas P and Q, whether there exists a formula I, built from the shared symbols of P and Q, such that P entails I and I entails Q in L. If L enjoys the Craig interpolation property (CIP), then the IEP reduces to validity in L. Recently, the IEP has been studied for logics without the CIP. The results obtained so far indicate that even though the IEP can be computationally harder than validity, it is decidable when L is decidable. Here, we give the first examples of decidable fragments of first-order logic for which the IEP is undecidable. Namely, we show that the IEP is undecidable for the two-variable fragment with two equivalence relations and for the two-variable guarded fragment with individual constants and two equivalence relations. We also determine the corresponding decidable Boolean description logics for which the IEP is undecidable.