Séminaire PPS: Georg Moser le 15/09 à 11H en 1D23

Bonjour à tous,

La séance de réntrée du séminaire PPS aura lieu ce jeudi 15 septembre en salle 1D23.
Nous accueillerons Georg Moser qui est en visite au laboratoire jusqu'à la fin du mois de septembre
(pour les membres du labo, Georg est en 5A16).

Automated Complexity Analysis of Rewriting
Georg Moser
Computational Logic Group, Institute of Computer Science University of Innsbruck

Jeudi 15 septembre à 11H en 1D23

Abstract: For a terminating term rewrite system (TRS for short), we can consider
the following abstract problem:

"How many rewrite steps can we perform till a normal-form is reached?"

Termination assert that this problem is  well-defined. This question
entails investigations into the "complexity" of term rewrite systems.
A TRS  is considered of higher complexity, if the number of possible
rewrite steps is larger. In recent years this sub-field of rewriting
has been thoroughly revived and a shift towards automation has been
performed.

In the talk I will review recent results and discuss the strong links
to implicit computational complexity theory as well as to the field of
automated complexity analysis of programs.

=======

À NOTER: il y aura café, thé, etc... un quart d'heure avant le début du séminaire: venez un peu en avance!

=======

Plus de détails sur le séminaire à http://www.pps.jussieu.fr/seminaire.

Amicalement,

Alexis