Solving divergence in Knuth--Bendix completion by enriching signatures (Q685379)

The Knuth-Bendix completion algorithm is a procedure which generates confluent and terminating sets of rewrite rules. The algorithm has many applications: the resulting rules can be used as a decision procedure for equality or, in the case of program synthesis, as a program. We present an effective algorithm to solve some cases of divergence in the Knuth- Bendix completion algorithm, starting from a grammar characterising the infinite rule set. We replace an infinite set of rewrite rules by a finite complete set by enriching the original (order-sorted) signature with new sorts and new operator arities, while remaining within a conservative extension of the original system and within the original term set. The complexity of the new rewriting system is no worse than that of the original system. We characterise the class of examples for which this approach is applicable and give some sufficient conditions for the algorithm to succeed.