Weak linearization of the lambda calculus

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

Autores

Alves, S (Autor) FCUP; Florido, M (Autor) FCUP

Revista

Título: Theoretical Computer Science

Vol. 342

Páginas: 79-103

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 4 Citações

Scopus - 7 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-000-1D9

DOI: 10.1016/j.tcs.2005.06.005

Abstract (EN): We identify a restricted class of terms of the lambda calculus, here called weak linear, that includes the linear lambda-terms keeping their good properties of strong normalization, non-duplicating reductions and typability in polynomial time. The advantage of this class over the linear lambda-calculus is the possibility of transforming general terms into weak linear terms with the same normal form. We present such transformation and prove its correctness by showing that it preserves normal forms.

Idioma: Inglês

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

Nº de páginas: 25