Godel's system T revisited

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

Autores

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

Revista

Título: Theoretical Computer Science

Vol. 411 Nº 11-13

Páginas: 1484-1500

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 11 Citações

Scopus - 16 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-003-8BA

DOI: 10.1016/j.tcs.2009.11.014

Abstract (EN): The linear lambda calculus, where variables are restricted to occur in terms exactly once, has a very weak expressive power: in particular, all functions terminate in linear time. In this paper we consider a simple extension with natural numbers and a restricted iterator: only closed linear functions can be iterated. We show properties of this linear version of Godel's T using a closed reduction strategy, and study the class of functions that can be represented. Surprisingly, this linear calculus offers a huge increase in expressive power over previous linear versions of T, which are 'closed at construction' rather than 'closed at reduction'. We show that a linear T with closed reduction is as powerful as T.

Idioma: Inglês

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

Nº de páginas: 17