Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 16 Avril 2013

Finding an optimal generating sequence for a presented structure

par Ali Akhavi (GREYC, Caen)

This talk presents a new framework for canonically associating an algorithm to a set of rewrite systems. Our approach identifies the algorithm with the set of all its execution traces. The rewrite systems associated to the algorithm are defined on the sequences of elementary transforms of the algorithm and are such that their normal forms are exactly the execution traces of the algorithm. The considered algorithms here are those solving the problem of finding an optimal generating sequence for a presented structure. Under some reasonable hypotheses, the execution traces are a spanning diagram on the Cayley diagram of the automorphism group of the presented structure and thus normal terms of rewrite systems. The approach provides a view of all algorithms that solve the problem with a set of fixed elementary transforms and brings better understanding of the problem: For instance, when there is a unique output and the automorphism group of the presented structure is finite, the radius of its Cayley graph is a lower bound for the complexity of the problem.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr