%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%         Marcel-Paul Sch\"utzenberger
%     Prepare pour le Bulletin of EATCS et l'EJC
%         version anglaise du 15 octobre 96
%         avec corrections Herbert Wilf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[12pt]{article}
\begin{document}
\begin{center}
{\large\bf Marcel-Paul Sch\"utzenberger (1920-1996)}
\end{center}

Marcel-Paul Sch\"utzenberger died on Monday, July 29, 1996.
He was a great figure of science, leaving to mankind a bunch of
fundamental discoveries and new ideas.
 He has worked during his life in an
incredible number of areas and many of the people, including some
of his former students, don't know the full extent of the 
diversity and  depth of the results of all sorts that he had
obtained. I am not sure
that I am aware myself of all of them, such as his contribution
to the discovery of the gene of trisomy in the early 50.

 I will
concentrate here on his work in Theoretical Computer Science.
You may find in the electronic Journal of Combinatorics 
(http://www.) contributions
by Herbert Wilf and by Dominique Foata more focused on his work
in combinatorics. Another source of additional information is
the volume {\it Mots} (by Lothaire, Hermes, 1990). It is a
collection of papers dedicated to Marco Sch\"utzenberger
by his friends and former students. You will find there
a bibliography (compiled by Imre Simon) of 155 scientific
papers by Marco.


It is also very early that Marco Sch{\"u}tzenberger began to work on
context-free grammars. The famous Chomsky-Sch\"utzenberger
theorem asserting that any context-free language is a coding of a
simple Dyck language appeared in 1963. His fundamental idea was that context-free
languages were a non-commutative version of algebraic series,
in the same way as finite-state languages are the non-commutative
counterpart of rational series. His work on context-free grammars
is thus closely related to the ones on algebraic and rational series.
He would in this vein publish in 1962 a paper in which he proves
a version for series of the property of the family of context-free
languages to be closed under intersection with a rational language,
thus appearing as a non-commutative version of a theorem on the
Hadamard product of an algabraic series with a rational one
(On a theorem of R. Jungen, {\it Proc. Amer. Math. Soc.}, {\it 13}, 885-890).

The beautiful theorem on aperiodic and star-free sets was published in
1965 ( On finite monoids having only trivial subgroups, {\it Inf. and
Control}, {\bf 8}, 190-194). It is the first result of the theory
of varieties that he would develop with S. Eilenberg and appears in the
second volume of {\it Automata, Languages and Machines} (Academic Press,
1976).

A good part of the rest of his mathematical work is either in algebra
or in combinatorics.

In algebra, he has deeply influenced the theory of semigoups.
The name of Sch\"utzenberger group of a ${\cal D}$-class was coined
by A. H. Clifford in the first book on semigroup theory
(A. H. Clifford and G. B. Preston,
{\it The algebraic Theory of Semigroups}, Amer. Math. Soc., 1961).
The techniques that he had developped in semigroups were in many
cases his `arme secr\`ete' for his work on automata. For example,
the theorem on star-free sets mentionned above can be easily stated
without reference to semigroups but I don't know of a proof that
does not use finite semigroups (a fact which might explain that
this result is not as well-known as one could expect).
Another part of Marco's work in algebra is on Lie algebras.
This is again related with codes and automata. Actually, one
of his most beautiful results relates Lie algebras decompositions
with factorizations of the free monoid (On a factorization of
free monoids, {\it Proc. Amer. Math. Soc.}, {\bf 16}, 1965, 21-24).


 His contributions in combinatorics are probably as important as those
in computer science, making Marco, to quote Herbert Wilf,
 `one of the most creative and influential
combinatorialists of this century'. It is probably his work on Young
tableaux which is most famous. Some of his early work
is reported in  Knuth's volume 3 ({\it Sorting and Searching}, Addison
Wesley, 1975). He was not so far from his grass roots since
 he introduced there, in his further work with Alain
Lascoux, a semigroup (the {\it plactic monoid}) which reveals many properties
of the tableaux.

 Marco Sch\"utzenberger was without doubt the founder
of combinatorics on words. One of the references for his pioneering
work there is the collective book by Lothaire published in 1983
and in which he himself wrote  a chapter, together with the
group of his former students in this field ({\it Combinatorics on Words},
Cambridge University Press). He used to say that I was the
``protonotaire'' of  Lothaire. Having accepted for many years this
mysterious title, I had today the curiosity to look in a dictionnary.
Here is what the Robert says:
\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}

I give up any attempt to translate the definition into english.


 Much of his work in mathematics, as we have seen, is
connected with automata, words and coding. It would certainely be difficult to
tell whether Marco Sch\"utzenberger has applied mathematics to computer
science or  conversely. He once told me long ago
that his work consisted in applying
his intuitions from data processing to bring new contributions to mathematics.
Was he really joking? He had actually especially strong beliefs and
a passion for discussion if not for controversy. Among the favourite
victims of his irony were all sorts of fools including the tenants
of artificial intelligence as they were trying to deny, he would say
the difference between men and women.

So much for mathematics. His contributions
 will live for a long time. A lot of the
rest will not survive  his numerous friends and students. All of them
remember long passionate discussions on all possible subjects. The influence
that he had on each of us goes well beyond our mathematical education.
We all have   lost a close and very affectionate friend who
hided behind bitter irony and an immederate love for paradoxes, an
incredibly generous nature.
\begin{flushright}
Dominique {\sc Perrin}\\
Paris, october 1996
\end{flushright}

 
\end{document}
\begin{center}
{\large\bf Dictionnary}
\end{center}
\noindent Former PhD student: {\it someone who makes me the honor to consider
himself as one of my students.}\\
\noindent A very useful work: {\it a thesis with pages printed one side only.}