Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Polymorphic rewriting conserves algebraic strong normalization
Breazu-Tannen V., Gallier J. Theoretical Computer Science83 (1):3-28,1991.Type:Article
Date Reviewed: Aug 1 1992

A combination of many-sorted algebraic term rewriting systems and polymorphic lambda term rewriting is studied in this paper. The results show that some important properties of algebraic systems are preserved when algebraic rewriting and polymorphic lambda-term rewriting are combined.

Given a set R of rewriting rules between algebraic &Sgr;-terms, if R is strong normalizing on algebraic &Sgr;-terms, then R+&bgr;+&eegr;+(type-&bgr;)+(type-&eegr;) rewriting of mixed terms is also strong normalizing. This result is obtained using a technique that nicely extends Girard’s reducibility candidates, which were introduced in the original proof of strong normalization for the polymorphic lambda calculus. The authors conclude by considering some directions for future research.

Reviewer:  Adrian Atanasiu Review #: CR115749
Bookmark and Share
 
Lambda Calculus And Related Systems (F.4.1 ... )
 
 
Grammars And Other Rewriting Systems (F.4.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Lambda Calculus And Related Systems": Date
Metacircularity in the polymorphic &lgr;-calculus
Pfenning F. (ed), Lee P. (ed) Theoretical Computer Science 89(1): 137-159, 1991. Type: Article
Nov 1 1992
Quantitative domains and infinitary algebras
Lamarche F. Theoretical Computer Science 94(1): 37-62, 1992. Type: Article
Dec 1 1992
A characterization of F-complete assignments
Dezani-Ciancaglini M. (ed), Margaria I. Theoretical Computer Science 45(2): 121-157, 1986. Type: Article
Jan 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy