### Abstract

We formalize basic results on first-order terms, including matching and a first-order unification algorithm, as well as well-foundedness of the subsumption order. This entry is part of the Isabelle Formalization of Rewriting IsaFoR, where first-order terms are omni-present: the unification algorithm is used to certify several confluence and termination techniques, like critical-pair computation and dependency graph approximations; and the subsumption order is a crucial ingredient for completion.

### License

GNU Lesser General Public License (LGPL)

### Topics

- Logic/Rewriting
- Computer science/Algorithms

### Session First_Order_Terms

- Transitive_Closure_More
- Renaming2
- Lists_are_Infinite
- Renaming2_String
- Seq_More
- Fun_More
- Option_Monad
- Term
- Term_Pair_Multiset
- Abstract_Matching
- Unifiers
- Abstract_Unification
- Unification
- Matching
- Unification_String
- Subsumption
- Subterm_and_Context

### Depends on

- Abstract Rewriting
- Fresh identifiers

### Used by

- Undecidability Results on Orienting Single Rewrite Rules
- A Formalization of the SCL(FOL) Calculus: Simple Clause Learning for First-Order Logic
- Extensions to the Comprehensive Framework for Saturation Theorem Proving
- A Formalization of Knuth–Bendix Orders
- Stateful Protocol Composition and Typing
- A Verified Functional Implementation of Bachmair and Ganzinger’s Ordered Resolution Prover
- The Resolution Calculus for First-Order Logic

## Cite

×

First_Order_Terms-AFP

    @article{First_Order_Terms-AFP,
      author  = {Christian Sternagel and René Thiemann},
      title   = {First-Order Terms},
      journal = {Archive of Formal Proofs},
      month   = {February},
      year    = {2018},
      note    = {\url{https://isa-afp.org/entries/First_Order_Terms.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 18, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Feb 7, 2018 : Isabelle2017
- Feb 6, 2018 : Isabelle2017