Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Strong normalization of the second-order symmetric &lgr;μ-calculus
Yamagata Y. Information and Computation193 (1):1-20,2004.Type:Article
Date Reviewed: Dec 21 2004

This research paper in mathematical logic is devoted to the lambda-mu calculus of Parigot, completed by the so-called symmetric structural reduction rules, but without the extraction operator; the calculus is exposed in paragraph 2.

The main result is a very general theorem of strong normalization (theorem 25, at the end of paper). The efficiency of such a theorem is illustrated by the example of existential assertions (cf. theorem 5): if it is provable that there is an x such that A(x), the normal deduction must contain a first order term t that satisfies A. But there is a cost: the calculus is highly nondeterministic, and if theorem 25 proves that a strong normalization exists for each term, its proof uses very noneffective tools, such as König’s Lemma (cf. proposition 9), or transfinite induction up to the first uncountable ordinal.

Reviewer:  F. Aribaud Review #: CR130555 (0506-0697)
Bookmark and Share
 
Lambda Calculus And Related Systems (F.4.1 ... )
 
 
Miscellaneous (F.4.m )
 
Would you recommend this review?
yes
no
Other reviews under "Lambda Calculus And Related Systems": Date
Polymorphic rewriting conserves algebraic strong normalization
Breazu-Tannen V., Gallier J. Theoretical Computer Science 83(1): 3-28, 1991. Type: Article
Aug 1 1992
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
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