The Power of Linear Functions

Alves, Sandra, Fernández, Maribel, Florido, Mario and Mackie, Ian (2006) The Power of Linear Functions. In: Lecture Notes in Computer Science.

Full text not available from this repository.


The linear lambda calculus is very weak in terms of expressive power: in particular, all functions terminate in linear time. In this paper we consider a simple extension with Booleans, natural numbers and a linear iterator. We show properties of this linear version of Gödel’s System T and study the class of functions that can be represented. Surprisingly, this linear calculus is extremely expressive: it is as powerful as System T.

Item Type: Conference or Workshop Item (Paper)
Schools and Departments: School of Engineering and Informatics > Informatics
Depositing User: Ian Mackie
Date Deposited: 06 Feb 2012 20:45
Last Modified: 13 Apr 2012 09:19
📧 Request an update