Confluence via strong normalisation in an algebraic λ-calculus with rewriting

Pablo Buiras
Alejandro Díaz-Caro
Mauro Jaskelioff

The linear-algebraic lambda-calculus and the algebraic lambda-calculus are untyped lambda-calculi extended with arbitrary linear combinations of terms. The former presents the axioms of linear algebra in the form of a rewrite system, while the latter uses equalities. When given by rewrites, algebraic lambda-calculi are not confluent unless further restrictions are added. We provide a type system for the linear-algebraic lambda-calculus enforcing strong normalisation, which gives back confluence. The type system allows an abstract interpretation in System F.

In Simona Ronchi della Rocca and Elaine Pimentel: Proceedings 6th Workshop on Logical and Semantic Frameworks with Applications (LSFA 2011), Belo Horizonte, Brazil, 27 August 2011, Electronic Proceedings in Theoretical Computer Science 81, pp. 16–29.
Published: 24th March 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.81.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org