First-Order Theory of Rewriting

Alexander Lochmann 📧 and Bertram Felgenhauer

February 2, 2022


The first-order theory of rewriting (FORT) is a decidable theory for linear variable-separated rewrite systems. The decision procedure is based on tree automata technique and an inference system presented in "Certifying Proofs in the First-Order Theory of Rewriting". This AFP entry provides a formalization of the underlying decision procedure. Moreover it allows to generate a function that can verify each inference step via the code generation facility of Isabelle/HOL. Additionally it contains the specification of a certificate language (that allows to state proofs in FORT) and a formalized function that allows to verify the validity of the proof. This gives software tool authors, that implement the decision procedure, the possibility to verify their output.
BSD License


Theories of FO_Theory_Rewriting