Vous pouvez vous abonner à nos annonces de séminaires
		    http://gallium.inria.fr/seminaires/

			     S E M I N A I R E
			   __                                  
			  / _`  _   /  /  o           
			 /   ) __) /  /  / /  / /\/| 
			(___/ (_/ (_ (_ / (__/ /   |  
                                                
			  I N R I A - Rocquencourt
                         Amphi Turing du bâtiment 1

                              Lundi 16 juin, 15h

                                 ------------
                                 Guy Blelloch
                                 ------------

                          Carnegie Mellon University

                   ========================================
                   Cost Models based on the Lambda Calculus
                   ========================================

                    [PLEASE NOTE THE UNUSUAL TIME: 15:00]

Traditionally complexity classes have been defined, and algorithms
analyzed using machine models such as the Turing Machine or Random
Access Machine (RAM).  However, the lambda calculus with appropriate
cost semantics can also serve as a simple model for defining (most of)
the same set of complexity classes, and for effectively analyzing the
cost of algorithms. Using the lambda calculus has some important
advantages, and in particular it is naturally parallel, capturing the
complexity class NC and being well suited for analyzing the efficiency
of parallel algorithms.  Indeed we currently teach our undergraduate
introduction to algorithms using the call-by-value (CBV) lambda
calculus (with a couple extensions) as our cost model.

In this talk I will describe some of our work on cost models and
simulation bounds starting with early work on equivalence of the CBV
lambda calculus and the RAM within a logarithmic factor, simple
extensions of the cost model for parallelism and its relation to the
Parallel RAM, accounting for space, and recent work on cost semantics
for cache efficient algorithms.