The power of linear functions

• Tipo: Artigo em Revista Científica Internacional
• Data: 2006

Autores

Sandra Alves (Autor) FCUP; Maribel Fernandez (Autor) Outra; Mirio Florido (Autor) FCUP; Ian Mackie (Autor) Outra

Indexação

ISI Web of Knowledge - 9 Citações

Scopus - 15 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 16