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.