# First-Order Theory of Rewriting

 Title: First-Order Theory of Rewriting Authors: Alexander Lochmann (alexander /dot/ lochmann /at/ uibk /dot/ ac /dot/ at) and Bertram Felgenhauer Submission date: 2022-02-02 Abstract: 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. BibTeX: @article{FO_Theory_Rewriting-AFP, author = {Alexander Lochmann and Bertram Felgenhauer}, title = {First-Order Theory of Rewriting}, journal = {Archive of Formal Proofs}, month = feb, year = 2022, note = {\url{https://isa-afp.org/entries/FO_Theory_Rewriting.html}, Formal proof development}, ISSN = {2150-914x}, } License: BSD License Depends on: FOL-Fitting, Regular_Tree_Relations