Séminaire Linguistique Informatique

6 Décembre 2010

Simone Martini

TITRE: Implicit computational complexity: cost models for rule based languages

Implicit computational complexity is a young research area, whose main aim is the description of complexity phenomena based on language restrictions, and not on external measure conditions or on explicit machine models. One of its goals is the study from a computational complexity viewpoint of those machine models that do not come with a natural cost model.
The main example is the lambda-calculus: The most natural intrinsic parameter of a computation is its number of beta-reductions, but this very parameter bears no relation, in general, with the actual cost of performing that computation (on a Turing machine, say), since a beta-reduction may involve the duplication of arbitrarily large subterms. In this introductory talk we will present some results for machine models where such natural cost measures do not exist, or are not obvious. We will deal with lambda-calculus, term rewrite systems, and term graph rewrite systems.
The talk will assume no (or very limited) prerequisites on computational complexity or rule based machine models.