首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号