General Bindings and Alpha-Equivalence in Nominal Isabelle
arXiv:1206.0136 · doi:10.2168/LMCS-8(2:14)2012
Abstract
Nominal Isabelle is a definitional extension of the Isabelle/HOL theorem prover. It provides a proving infrastructure for reasoning about programming language calculi involving named bound variables (as opposed to de-Bruijn indices). In this paper we present an extension of Nominal Isabelle for dealing with general bindings, that means term constructors where multiple variables are bound at once. Such general bindings are ubiquitous in programming language research and only very poorly supported with single binders, such as lambda-abstractions. Our extension includes new definitions of alpha-equivalence and establishes automatically the reasoning infrastructure for alpha-equated terms. We also prove strong induction principles that have the usual variable convention already built in.
arXiv comment35 pages
Cited by in corpus (7)
- A Mechanised Proof of Gödel's Incompleteness Theorems using Nominal Isabelle
- A Machine-Assisted Proof of Gödel's Incompleteness Theorems for the Theory of Hereditarily Finite Sets
- Nominal Unification of Higher Order Expressions with Recursive Let
- Check: A mechanized metatheory model-checker
- Nominal Unification and Matching of Higher Order Expressions with Recursive Let
- Adventures in Formalisation: Financial Contracts, Modules, and Two-Level Type Theory
- A Short Mechanized Proof of the Church-Rosser Theorem by the Z-property for the -calculus in Nominal Isabelle