The power of linear functions

• Type: Article in International Scientific Journal
• Date: 2006

Authors

Sandra Alves (Author) FCUP; Maribel Fernandez (Author) Other; Mirio Florido (Author) FCUP; Ian Mackie (Author) Other

Indexing

ISI Web of Knowledge - 9 Citations

Scopus - 15 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-004-PDY

DOI: 10.1007/11874683_8

Abstract (EN): 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 Godels'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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 16