%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%         Marcel-Paul Sch\"utzenberger
%     Prepare pour le Seminaire Lotharingien
%         versionfrancaise du 15 octobre 96
%        
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}
\begin{document}
\begin{center}
{\large\bf Marcel-Paul Sch\"utzenberger (1920-1996)}
\end{center}
Marcel-Paul Sch\"utzenberger est mort le lundi 29 juillet 1996.
C'\'etait, pour reprendre l'expression d'Andr\'e Lichnerowicz
\footnote{Hommage \`a M. P. Sch\"utzenberger, La Recherche, {\bf 280}, octobre 1996},
un gentilhomme de la  science, qui laisse en h\'eritage
une quantit\'e de d\'ecouvertes fondamentales et d'id\'ees nouvelles.
Il a travaill\'e durant sa vie dans un nombre incroyable de
domaines diff\'erents et beaucoup, y compris parmi ses
anciens \'el\`eves, ne connaissent qu'une partie de la fabuleuse
diversit\'e et de la profondeur des r\'esultats de toutes
sortes qu'il a pu obtenir. Je ne suis moi-m\^eme pas s\^ur
de bien les conna\^{\i}tre tous, comme par exemple sa participation
\`a la d\'ecouverte du g\`ene de la trisomie au d\'ebut des
ann\'ees 50.

Je vais essayer de retracer ici quelques \'el\'ements de son
travail en informatique th\'eorique. Une source d'autres informations
est le volume {\em Mots} (Hermes, 1980). Il s'agit d'un recueil de
textes en hommage \`a Marco Sch\"utzenber\-ger pr\'epar\'e par ses
amis et ses anciens \'el\`eves. On y trouve en particulier une
liste de ses publications scientifiques (compil\'ee par Imre Simon)
compl\`ete jusqu'\`a la date de publication de l'ouvrage. 

Le point de d\'epart de son travail en informatique th\'eorique
est la th\'eorie des codes \`a longueur variable. Il a pr\'esent\'e en
1955 au s\'eminaire d'alg\`ebre de Paul Dubreil un expos\'e
intitul\'e `Une th\'eorie alg\'ebrique du codage' ({\em S\'eminaire
Dubreil-Pisot}, ann\'ee 1955-56, expos\'e n$^o$ 15). Le texte contient
d\'eja un grand nombre des id\'ees de son travail futur sur les automates.
On y trouve en particulier la d\'efinition du semigroupe syntaxique d'une
partie reconnaissable (le {\em `semigroupe fondamental'}). La preuve
de l'\'egalit\'e des ensembles rationnels et reconnaissables
(ou, au moins, la partie essentielle qui est la cloture des
ensembles reconnaissables par \'etoile) apparait l\`a de fa\c{c}on
presque simultan\'ee avec la publication de l'article de Kleene
(sur cette p\'eriode h\'ero{\"\i}que, on peut consulter mon article
`Les d\'ebuts de la th\'eorie des automates', {\em TSI},{\bf 14},
1995,
409-433). Il a certainement \'et\'e le premier \`a
voir que la propri\'et\'e de d\'ecodage unique est de nature alg\'ebrique
(en fait une propri\'et\'e de base d'un mono\"{\i}de libre, analogue \`a
celle qui fait l'objet de la th\'erie de Nielsen-Schreier dans le groupe
libre). Il a \'et\'e fascin\'e d\`es le d\'ebut par l'id\'ee qu'il y avait
quelque chose de plus \`a comprendre dans cette propri\'et\'e et qu'on
avait tort de se satisfaire du fait que l'algorithme de Sardinas et
Paterson (sardinapoil pour les intimes, publi\'e en 1953) permet de v\'erifier
qu'un ensemble la poss\`ede. Il a aussi d\'ecouvert dans ce  domaine un jeu
tr\`es riche de propri\'et\'es et de points de vue qui s'articulent
de fa\c{c}on \'etonnante. J'ai d\'ecouvert moi-m\^eme, lorseque j'ai commen\c{c}\'e
\`a travailler sur les codes au d\'ebut des ann\'ees 70, les diff\'erents aspects
alg\'ebriques (avec l'utilisation de semigroupes finis), combinatoires
(avec la combinatoire des mots) ou probabilistes (li\'es \`a la th\'eorie de
l'information de Shannon).  Les tr\`es nombreux r\'esultats que Sch\"utzenberger
a obtenus sur les codes ont fait l'objet de publications ind\'ependantes
 et certains d'entre eux n'apparaissaient que dans des notes,
comme celles du s\'eminaire de Royan de 1965. L'ensemble constituait un
corps assez difficile d'acc\`es comportant, au dire d'Aldo De Luca et Antonio Restivo `una
tradizione orale'. La publication en 1984 de notre livre avec Jean
Berstel (`Theory of Codes', Academic Press) a permis de donner une pr\'esentation
plus accessible de l'ensemble de la th\'eorie. L'ouvrage a, en fait, \'et\'e
pr\'epar\'e \`a l'initiative et avec la constante sollicitude de Marco qui,
suivant son go\^ut en la mati\`ere, a pr\'ef\'er\'e que son nom ne figure
pas parmi ceux des auteurs. Pour citer l'un des tr\`es beaux r\'esultats
de Sch\"utzenberger sur les codes, je choisirai celui-ci~: {\em Un code maximal
fini a un d\'elai de d\'echiffrage qui est nul ou bien infini}
({\it J. Comb. Th.}, {\bf 1}, 1966, 437-442). Ce magnifique
th\'eor\`eme avait \'et\'e conjectur\'e par E. N. Gilbert et E. F. Moore dans
leur article de 1959 (variable length binary encodings, {\em Bell System 
Tech. J.} {\bf 38}, 933-967). Il est, comme beaucoup de r\'esultats combinatoires
de nature extr\^emale, susceptible de plusieurs preuves
tr\`es diff\'erentes. L'une d'elles a d'ailleurs \'et\'e d\'ecouverte tr\`es r\'ecemment
par V\'eronique Bruy\`ere. Il peut aussi \^etre interpr\'et\'e de diverses
fa\c{c}ons, en particulier comme un r\'esultat sur l'optimalit\'e des codes
pr\'efixes, qui sont ceux dont le d\'elai de d\'echiffrage est nul.
La th\'eorie des codes \`a longueur variable reste aussi marqu\'ee par la
conjecture de Sch\"utzenberger selon laquelle un code maximal fini
est commutativement pr\'efixe. Cette conjecture aparait d\'eja dans
le texte de Royan cit\'e plus haut et a r\'esist\'e jusqu'\`a pr\'esent
\`a tous les efforts faits pour la d\'emontrer, y compris ceux 
qui ont permis d'\'etablir des th\'eor\`emes voisins,
 comme celui de Christophe Reutenauer.
Les id\'ees de Sch\"utzenberger sur les codes l'ont aussi conduit plus tard
\`a d\'evelopper une th\'eorie des fonctions rationnelles sur les mots.
Il s'agit de fonctions calculables par un automate fini, dont le
d\'ecodage d'un code rationnel fournit un exemple typique.
Ainsi, un des beaux outils qu'il a introduits sont les transducteurs non-ambigus,
qui sont la g\'en\'eralisation naturelle des tranducteurs de d\'ecodage.

Marco Sch\"utzenberger a aussi commen\c{c}\'e tr\`es t\^ot son c\'el\`ebre
travail sur les grammaires context-free. Le fameux th\'eor\`eme
de Chomsky-Sch\"utzenberger, affirmant que tout langage context-free
est un codage d'un langage de Dyck date de 1963. Son id\'ee fondamentale
est que les langages context-free sont une version non-commutative des
s\'eries alg\'ebriques, de la m\^eme fa\c{c}on que les langages rationnels
sont la version non-commutative des s\'eries rationnelles. Ainsi, pour donner
un exemple, on \'ecrira la grammaire des mots bien parenth\'es\'es
\[P\rightarrow (P)P+\epsilon\]
sous la forme de l'\'equation alg\'ebrique
\[\pi=a\pi b+1\]
dont la solution, en variables commutatives, est la fonction alg\'ebrique
\[\pi=a\frac{1}{\displaystyle 1-a\frac{1}{\displaystyle 1-a\frac{1}{\ddots}b}b}b\]
Son travail sur les grammaires context-free est donc \'etroitement
reli\'e \`a celui sur les s\'eries alg\'ebriques et rationnelles.
C'est dans cet esprit qu'il a publi\'e en 1962 un article dans
lequel il montre que le produit de Hadamard d'une s\'erie alg\'ebrique et d'une s\'erie
rationnelle non-commutatives est encore une s\'erie alg\'ebrique
(On a theorem of R. Jungen, {\it Proc. Amer. Math. Soc.}, {\it 13}, 885-890).
Il s'agit en fait d'une version pour les s\'eries de la propri\'et\'e
suivant laquelle l'intersection d'un langage context-free et d'un langage
rationnel est encore context-free, qui aparait de la sorte comme une
g\'en\'eralisation d'un r\'esultat d\'eja connu, et d\^u \`a R. Jungen,
 pour les s\'eries en une variable.

Le magnifique th\'eor\`eme sur les ensembles ap\'eriodiques et sans-\'etoile
est publi\'e en 1965 (On finite monoids having only trivial subgroups, {\it Inf. and
Control}, {\bf 8}, 190-194). Il caract\'erise les propri\'et\'es
d\'efinissables par des op\'erations bool\'eennes et le produit
( et donc sans \'etoile) comme celles qui ne donnent pas lieu \`a
une p\'eriodicit\'e. Il s'agit en fait du premier r\'esultat de la
th\'eorie des vari\'et\'es qu'il allait d\'evelopper avec Samuel
Eilenberg et qui parut pour la premi\`ere fois dans le second volume
du livre d'Eilenberg ({\it Automata, Languages and Machines}, Academic Press,
1976).

La plupart du reste de l'oeuvre math\'ematique de M. P. Sch\"utzenberger
est soit en alg\`ebre, soit en combinatoire.


En alg\`ebre, il a profond\'ement influenc\'e la th\'eorie des
semigroupes. Le nom de groupe de Sch\"utzenberger d'une ${\cal D}$-classe,
ainsi que celui de repr\'esen\-tation de Sch\"utzenberger,
ont \'et\'e choisis par A. H. Clifford et aparaissent dans le
premier livre sur la th\'eorie alg\'ebique des semigroupes
(A. H. Clifford and G. B. Preston,
{\it The algebraic Theory of Semigroups}, Amer. Math. Soc., 1961).
Les techniques qu'il avait d\'evelopp\'e sur les semigroupes furent
souvent son `arme secr\`ete' pour son travail sur les automates.
Par exemple, la preuve du th\'eor\`eme mentionn\'e plus
haut sur les ensembles sans \'etoile utilise la th\'eorie des
semigroupes finis. Je ne connais d'ailleurs pas de preuve de ce r\'esultat
qui n'utilise pas les semigroupes (ce qui explique peut-\^etre que le th\'eor\`eme
ne soit pas aussi bien connu qu'on pourrait s'y attendre).
Une autre partie du travail de Marco porte sur les alg\`ebres de Lie.
Il y a en fait, de nouveau, un lien avec les codes et les automates.
De fait, l'un de ses plus beaux r\'esultats relie les d\'ecompositions des
alg\`ebres de Lie et les factorisations des mono\"{\i}des libres 
(On a factorization of
free monoids, {\it Proc. Amer. Math. Soc.}, {\bf 16}, 1965, 21-24).

Ses contributions en combinatoire sont probablement aussi importantes que celles
d'informatique th\'eorique, et Marco fut, aux dires de Herbert Wilf,
`l'un des combinatorialistes les plus cr\'eatifs et les plus importants
de ce si\`ecle'
\footnote{in {\em Electronic Journal of Combinatorics},
 http://ejc.math.gatech.edu:8080/Journal
}. C'est probablement son travail sur les tableaux de Young qui est le plus
c\'el\`ebre. Une partie de ses premiers r\'esultats est reproduite
dans le volume 3 du livre de Donald Knuth ({\it Sorting and Searching}, Addison
Wesley, 1975). Il n'\'etait en fait pas si loin de son port d'attache,
puisqu'il devait introduire dans ce domaine, dans son travail avec Alain Lascoux,
un semigroupe (le {\em mono\"{\i}de plaxique}) qui rend compte de nombre des
propri\'et\'es des tableaux. On lui doit aussi l'id\'ee des {\em preuves
bijectives} consistant \`a rechercher une interpr\'etation combinatoire
naturelle des identit\'es combinatoires en exhibant une bijection entre
deux ensembles correspondant aux deux membres de l'identit\'e.
Les ensembles sont souvent des langages formels, comme dans le cas des
\'enum\'erations de familles de graphes donn\'ees par des langages
context-free d\'evelopp\'ees \`a sa suite par Robert Cori.
.

Marco Sch\"utzenberger fut sans aucun doute le fondateur de la combinatoire des
mots. Il a travaill\'e dans ce domaines \`a de tr\`es nombreuses reprises,
en particulier avec Andr\'e Lentin ou avec
Roger Lyndon 
sur les \'equations en mots. Nombre des r\'esultats sont pr\'esent\'es dans
le volume collectif publi\'e sous le pseudonyme de Lothaire en 1983
({\it Combinatorics on Words},
Cambridge University Press). Marco avait l'habitude de me gratifier de titre
de ``protonotaire'' de Lothaire. J'ai accept\'e longtemps ce titre myst\'erieux sans
y penser mais j'ai eu r\'ecemment la curiosit\'e de consulter le Robert.
Voici le r\'esultat:

 

\begin{quotation}
\noindent{\large\bf PROTONOTAIRE} {\small
n. m. $-$ 1390; lat. eccl\'es. {\it protonotarius},
de {proto}-, et lat. {\it notarius}. $\rightarrow$ Notaire}

\noindent$\diamondsuit$ {\bf 1.} Pr\'elat de la cour romaine, du rang le plus \'elev\'e parmi
ceux qui n'ont pas le caract\`ere \'episcopal. {\it Les protonotaires
apostoliques participants} (de numero participiendum), {\it officiers de la cour
pontificale, sont constitu\'es en coll\`ege et sont charg\'es d'enregis\-trer les
actes pontificaux dans les circonstances solennelles, \`a la congr\'e\-gation
des rites, de signer les bulles...}--{\it Protonotaires \`a l'instar}
(ad instar participantium). {\it Protonotaires titulaires, honoraires} ou {\it
protonotaires noirs} (dont l'habit ne comporte pas les ornements amarante
des autres protonotaires).

\noindent$\diamondsuit$ {\bf 2.} (1680). Hist. Premier notaire d'un empereur
romain.\\
(1869). Dignitaire la\"{\i}c du moyen-\^age (chef de la chancellerie, etc.)

\noindent$\diamondsuit$ {\bf 3.} (Canada, 1795). Fonctionnaire charg\'e de l'enregistrement
des actes dans un bureau r\'egional.

\noindent{\footnotesize\bf D\'ER. Protonotariat}
\end{quotation}

Une grande partie du travail de Marco en math\'ematiques est, comme nous
l'avons vu, reli\'e avec les automates, les mots ou les codes. Il serait 
certainement tr\`es difficile de dire si Marco Sch\"utzenberger a appliqu\'e les
math\'ematiques \`a l'informatique, ou si c'est plut\^ot l'inverse.
 Il m'a dit il y a longtemps
qu'il consid\'erait que son r\^ole \'etait d'utiliser ses intuitions sur
le traitement des donn\'ees pour contribuer \`a enrichir les math\'ematiques
 d'objets et de propri\'et\'es nouvelles. Plaisantait-il?
En fait, il avait dans toutes les mati\`eres des id\'ees extr\^emement
originales et affirm\'ees qui alimentaient une v\'eritable passion pour la
conversation, voire m\^eme les joutes oratoires. L'une des victimes fr\'equentes
de ses sarcasmes \'etait l'intelligence artificielle et tout ce qui
s'en rapproche dans la croyance dans un mod\`ele simpliste de la pens\'ee
et de la nature humaine,
 au point, disait-il, d'en arriver \`a oublier l'existence de diff\'erences
entre les sexes.

Voil\`a pour les math\'ematiques. Ses contributions resteront vivantes tr\`es
longtemps, m\^eme si le souvenir de son \'etonnante personnalit\'e
 ne pourra survivre \`a ses nombreux
amis et \'el\`eves. L'influence qu'il a eu sur chacun de nous d\'epasse de
beaucoup notre \'education math\'ematique. Nous avons perdu un ami tr\`es
attentionn\'e, dont l'amour pour la discussion et les paradoxes nourrissait
une nature merveilleusement g\'en\'ereuse.



\begin{flushright}
Dominique {\sc Perrin}\\
Paris, october 1996
\end{flushright}
\end{document}
