The apparition of combinatorial structures like partitions, trees, graphs in algebraic computation is not new. Two famous earlier examples can be found in the formula of Cayley for integrating vector fields and the theory of Young tableaux in the representation theory of the symmetric group. The fact that combinatorial objects carry naturally some Hopf-algebraic structures has been then widely advertised by Rota. Recently, a large class of examples of very rich algebraic structures (Hopf algebra, Lambda-rings...) appeared naturally in several seemingly unrelated fields of science. One can cite, for example, renormalization of quantum electrodynamics in physics (Connes-Kreimer), category of algebra and operads in algebra (Loday), generalized symmetric functions (Gessel), and generalized generating series in combinatorics. Several of these algebras are closely related to well known algorithms of computer sciences (Schensted algorithm for computing the length of a longest increasing subsequence, Bubble-sort, search-tree insertion). The knowledge of this connection allows one for very simple proofs and very efficient algorithm for computing in these structures. The goal of this course is to present to the audience what kind of algebraic structures, namely the Hopf algebra appears naturally in these fields. In a second time, we will show on two similar examples how two of these Hopf algebras can be naturally constructed in a very efficient way starting from simple computer science algorithms.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 email@example.com
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 firstname.lastname@example.org