Weak linearization of the lambda calculus

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

Authors

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

Journal

Title: Theoretical Computer Science

Vol. 342

Pages: 79-103

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 4 Citations

Scopus - 7 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 25