Automating the Derivation of Unification Algorithms
Richard Waldinger · 2025
Read Automating the Derivation of Unification Algorithms by Richard Waldinger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11136.txt.
Description
Richard Waldinger pursues a fully automatic derivation of the unification algorithm, the pattern-matching heart of logic programming, in a 2025 paper. In this approach, a program is extracted from a theorem proof, so correctness comes with an explanation attached. The goal: given two symbolic expressions and a starting set of replacements, called a substitution, produce the most general one that makes the expressions match, or report failure.
The work builds on a manual 1981 proof by Manna and Waldinger and automates it. The new method carries the growing substitution through its nested calls, recording each replacement as it is found. Waldinger suspects this form is both faster and easier for a prover to derive than the classic two-input form. The case study shows how far machine proving has come toward writing its own programs.
Catalog record
| CREATOR | Richard Waldinger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 224 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-11136