Combination of Uniform Interpolants via Beth Definability
Open Access
- 12 May 2022
- journal article
- research article
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 66 (3) , 409-435
Abstract
Uniform interpolants were largely studied in non-classical propositional logics since the nineties, and their connection to model completeness was pointed out in the literature. A successive parallel research line inside the automated reasoning community investigated uniform quantifier-free interpolants (sometimes referred to as “covers”) in first-order theories. In this paper, we investigate cover transfer to theory combinations in the disjoint signatures case. We prove that, for convex theories, cover algorithms can be transferred to theory combinations under the same hypothesis needed to transfer quantifier-free interpolation (i.e., the equality interpolating property, aka strong amalgamation property). The key feature of our algorithm relies on the extensive usage of the Beth definability property for primitive fragments to convert implicitly defined variables into their explicitly defining terms. In the non-convex case, we show by a counterexample that covers may not exist in the combined theories, even in case combined quantifier-free interpolants do exist. However, we exhibit a cover transfer algorithm operating also in the non-convex case for special kinds of theory combinations; these combinations (called ‘tame combinations’) concern multi-sorted theories arising in many model-checking applications (in particular, the ones oriented to verification of data-aware processes).Keywords
This publication has 33 references indexed in Scilit:
- Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant SynthesisLogical Methods in Computer Science, 2010
- Uniform Interpolation and Propositional Quantifiers in Modal LogicsStudia Logica, 2007
- Model-Theoretic Methods in Combined Constraint SatisfiabilityJournal of Automated Reasoning, 2004
- Logical questions concerning the μ-calculus: Interpolation, Lyndon and Łoś-TarskiThe Journal of Symbolic Logic, 2000
- Model completions and r-Heyting categoriesAnnals of Pure and Applied Logic, 1997
- A sheaf representation and duality for finitely presented Heyting algebrasThe Journal of Symbolic Logic, 1995
- An algebraic theory of normal formsAnnals of Pure and Applied Logic, 1995
- Undefinability of propositional quantifiers in the modal system S4Studia Logica, 1995
- On an interpretation of second order quantification in first order intuitionistic propositional logicThe Journal of Symbolic Logic, 1992
- Simplification by Cooperating Decision ProceduresACM Transactions on Programming Languages and Systems, 1979