A formalised first-order confluence proof for the λ-calculus using one-sorted variable names |
| |
Authors: | Ren Vestergaard James Brotherston |
| |
Affiliation: | a Japan Advanced Institute of Science and Technology, Tatsunokuchi, Ishikawa 923-1292, Japan;b Mathematical Reasoning Group, Division of Informatics, University of Edinburgh, 80 South Bridge, Edinburgh EH1 1HN, Scotland, UK |
| |
Abstract: | We present the titular proof development that has been verified in Isabelle/HOL. As a first, the proof is conducted exclusively by the primitive proof principles of the standard syntax and of the considered reduction relations: the naive way, so to speak. Curiously, the Barendregt Variable Convention takes on a central technical role in the proof. We also show: (i) that our presentation of the λ-calculus coincides with Curry’s and Hindley’s when terms are considered equal up to α-equivalence and (ii) that the confluence properties of all considered systems are equivalent. |
| |
Keywords: | λ -Calculus Structural induction and recursion Confluence Theorem proving Barendregt’ s Variable Convention |
本文献已被 ScienceDirect 等数据库收录! |
|