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.
  author  = {Alexander Lochmann and Bertram Felgenhauer},
  title   = {First-Order Theory of Rewriting},
  journal = {Archive of Formal Proofs},
  month   = feb,
  year    = 2022,
  note    = {\url{},
            Formal proof development},
  ISSN    = {2150-914x},
License: BSD License
Depends on: FOL-Fitting, Regular_Tree_Relations