Effective interpolation and preservation in guarded logics

Journal article

Desirable properties of a logic include decidability, and a model theory that inherits properties of first-order logic, such as interpolation and preservation theorems. It is known that the Guarded Fragment (GF) of firstorder logic is decidable and satisfies some preservation properties from first-order model theory; however, it fails to have Craig interpolation. The Guarded Negation Fragment (GNF), a recently defined extension, is known to be decidable and to have Craig interpolation. Here we give the first results on effective interpolation for extensions of GF. We provide an interpolation procedure for GNF whose complexity matches the doubly exponential upper bound for satisfiability of GNF. We show that the same construction gives not only Craig interpolation, but Lyndon interpolation and relativized interpolation, which can be used to provide effective proofs of some preservation theorems. We provide upper bounds on the size of GNF interpolants for both GNF and GF input, and complement this with matching lower bounds.

Authors: Benedikt, M; Ten Cate, B; Vanden Boom, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Computational Logic
• Volume: 17
• Issue: 2
• Article number: 8
• Publication date: 2015-12-06
• DOI: 10.1145/2814570
• EISSN: 1557-945X
• ISSN: 1529-3785
• Keywords: guarded fragment; mosaic method; guarded negation fragment