The Power of Closed Reduction Strategies

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

Autores

Alves, S (Autor) FCUP; Fernandez, M (Autor) Outra; Florido, M (Autor) FCUP; Mackie, I (Autor) Outra

Revista

Título: Electronic Notes in Theoretical Computer Science

Vol. 174

Páginas: 57-74

ISSN: 1571-0661

Editora: Elsevier

Indexação

ISI Web of Knowledge

Scopus - 4 Citações

Outras Informações

ID Authenticus: P-007-J13

DOI: 10.1016/j.entcs.2007.02.047

Abstract (EN): The computational efficiency of linear ¿-calculi with iterators is evaluated using closed reduction strategies. The interaction between linearity and closed reduction and the computational power of linear systems with and without closed reduction is analyzed. A linear version of Gödel's System T with closed reductions is defined to analyze the computational power of linear systems. Closed reduction strategies in the ¿-calculus restrict the reduction rules since closed reduction strategies can take place when certain terms are closed and do not contain free variables. Closed reduction strategies impose strong constraints on the application of reduction rules. Closed reduction strategies can simulate call-by-name and call-by-value evaluations in the ¿-calculus. Linear ¿-calculus with iterators can be efficiently analyzed by relaxing the constraints on the construction of iterator terms.

Idioma: Inglês

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

Nº de páginas: 18