Institut de Mathématiques de Luminy

Abstract 2006-08

Lafont Yves.
Algebra and geometry of rewriting

We present various results of the last twenty years converging towards a homotopical theory of computation. This new theory is based on two crucial notions : polygraphs (introduced by Albert Burroni) and polygraphic resolutions (introduced by François Métayer). There are two motivations for such a theory:

• providing invariants of computational systems to study those systems and prove properties about them;

• finding new methods to make computations in algebraic structures coming from geometry or topology.

This means that this theory should be relevant for mathematicians as well as for theoretical computer scientists, since both may find useful tools or concepts for their own domain coming from the other one.

Keywords. homotopical theory of computation, polygraphs, polygraphic resolutions


Last update : may 4, 2006, EL.