A Formalization of the Knuth-Bendix(-Huet) Critical Pair Theorem

作者：Galdino Andre L; Ayala Rincon Mauricio^*

来源：Journal of Automated Reasoning, 2010, 45(3): 301-325.

DOI：10.1007/s10817-010-9165-2

• Abstract reduction systems
• Term rewriting systems
• Formalization of theorems
• PVS
• Critical pair theorem

A mechanical proof of the Knuth-Bendix Critical Pair Theorem in the higher-order language of the theorem prover PVS is described. This well-known theorem states that a Term Rewriting System is locally confluent if and only if all its critical pairs are joinable. The formalization of this theorem follows Huet's well-known structure of proof in which the restriction on strong normalization or Noetherian was dropped and the result presented as a lemma. In order to formalize the Knuth-Bendix Critical Pair Theorem we rely on previously developed PVS theories for abstract reduction systems, named ars, and term rewriting systems, named trs, which were built upon the PVS libraries for finite sequences and sets. On the one hand, the theory trs is composed of subtheories for dealing with the structure of terms, for replacements of subterms and substitutions and jointly with the theory ars it allows for adequate specifications of elaborate notions of term rewriting systems such as the one of critical pairs. On the other hand, ars specifies basic definitions and notions of abstract reduction systems such as reduction, termination, normal forms, and confluence as well as non basic concepts such as strong normalization.

• 出版日期2010-10