The Power of Closed Reduction Strategies

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

Authors

Alves, S (Author) FCUP; Fernandez, M (Author) Other; Florido, M (Author) FCUP; Mackie, I (Author) Other

Journal

Title: Electronic Notes in Theoretical Computer Science

Vol. 174

Pages: 57-74

ISSN: 1571-0661

Publisher: Elsevier

Indexing

ISI Web of Knowledge

Scopus - 4 Citations

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18