A Knuth-Bendix-Like Ordering for Orienting Combinator Equations
- 24 June 2020
- book chapter
- Published by Springer Nature
- Vol. 12166, 259-277
Abstract
We extend the graceful higher-order basic Knuth-Bendix order (KBO) of Becker et al. to an ordering that orients combinator equations left-to-right. The resultant ordering is highly suited to parameterising the first-order superposition calculus when dealing with the theory of higher-order logic, as it prevents inferences between the combinator axioms. We prove a number of desirable properties about the ordering including it having the subterm property for ground terms, being transitive and being well-founded. The ordering fails to be a reduction ordering as it lacks compatibility with certain contexts. We provide an intuition of why this need not be an obstacle when using it to parameterise superposition.Keywords
This publication has 19 references indexed in Scilit:
- A Knuth-Bendix-Like Ordering for Orienting Combinator Equations2020
- A Combinator-Based Superposition Calculus for Higher-Order Logic2020
- Superposition with Lambdas2019
- Hammer for Coq: Automation for Dependent Type TheoryJournal of Automated Reasoning, 2018
- A Transfinite Knuth–Bendix Order for Lambda-Free Higher-Order TermsLecture Notes in Computer Science, 2017
- A Lambda-Free Higher-Order Recursive Path Order2017
- The Higher-Order Prover Leo-IIJournal of Automated Reasoning, 2015
- Satallax: An Automatic Higher-Order Prover2012
- The Computability Path Ordering: The End of a Quest2008
- Substitution tree indexing1995