Finding an optimal generating sequence for a presented structure

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.