Publication details
Autosubst: Reasoning with de Bruijn Terms and Parallel Substitutions
Steven Schäfer, Tobias Tebbi, Gert Smolka
Interactive Theorem Proving - 6th International Conference, ITP 2015, Nanjing, China, August 24-27, 2015, Springer-Verlag, August 2015
Reasoning about syntax with binders plays an essential role in the formalization of the metatheory of programming languages.
While the intricacies of binders can be ignored in paper proofs, formalizations involving binders tend to be heavyweight.
We present a discipline for syntax with binders based on d Bruijn terms and parallel substitutions, with a decision procedure covering all assumption-free equational substitution lemmas.
The approach is implemented in the Coq library Autosubst, which additionally derives substitution operations and proofs of substitution lemmas for custom term types.
We demonstrate the effectiveness of the approach with several case studies, including part A of the POPLmark challenge.
project page
Download PDF
Show BibTeX
@INPROCEEDINGS{SchaeferEtAl:2015:Autosubst:-Reasoning,
title = {Autosubst: Reasoning with de Bruijn Terms and Parallel Substitutions},
author = {Steven Schäfer and Tobias Tebbi and Gert Smolka},
year = {2015},
month = {Aug},
editor = {Xingyuan Zhang and Christian Urban},
publisher = {Springer-Verlag},
booktitle = {Interactive Theorem Proving - 6th International Conference, {ITP} 2015, Nanjing, China, August 24-27, 2015},
series = {LNAI},
}
Login to edit
Legal notice, Privacy policy
