Reducing Higher-order Recursion Scheme Equivalence to Coinductive Higher-order Constrained Horn Clauses
arXiv:2109.04632 · doi:10.4204/EPTCS.344.4
Abstract
Higher-order constrained Horn clauses (HoCHC) are a semantically-invariant system of higher-order logic modulo theories. With semi-decidable unsolvability over a semi-decidable background theory, HoCHC is suitable for safety verification. Less is known about its relation to larger classes of higher-order verification problems. Motivated by program equivalence, we introduce a coinductive version of HoCHC that enjoys a greatest model property. We define an encoding of higher-order recursion schemes (HoRS) into HoCHC logic programs. Correctness of this encoding reduces decidability of the open HoRS equivalence problem -- and, thus, the LambdaY-calculus Böhm tree equivalence problem -- to semi-decidability of coinductive HoCHC over a complete and decidable theory of trees.
arXiv commentIn Proceedings HCVS 2021, arXiv:2109.03988
References in corpus (4)
- HoCHC: A Refutationally Complete and Semantically Invariant System of Higher-order Logic Modulo Theories
- Coinduction in Uniform: Foundations for Corecursive Proof Search with Horn Clauses
- Towards Coinductive Theory Exploration in Horn Clause Logic: Position Paper
- The Extended Theory of Trees and Algebraic (Co)datatypes