Marcel-Paul Schützenberger, né le 24 octobre 1920 à Paris et mort le 29 juillet 1996 dans la même ville, est un scientifique français, dont les recherches ont d'abord porté sur la médecine et la biologie, mais surtout connu pour ses travaux en mathématiques, en informatique théorique et en combinatoire. Il est le fondateur de la combinatoire des mots et un pionnier de la théorie des codes en longueur variable. Il a joué un rôle déterminant dans la création de l'informatique théorique en France, comme en témoigne le nombre de ses disciples.
Pendant la deuxième Guerre mondiale, Marcel-Paul Schützenberger œuvre dans la résistance. À la fin de la guerre, il est un proche collaborateur de Charles Tillon et membre de son cabinet ministériel. En 1948, il épouse Anne Ancelin Schützenberger ; ils divorcent quelques années plus tard.
Marcel-Paul Schützenberger obtient un doctorat en médecine en 1949. De 1948 à 1953, il est attaché de recherches, puis chargé de recherches à l'Institut national d'hygiène, et il est assistant de consultation au Centre de génétique de l'Hôpital Saint-Louis de 1948 à 1954. Durant cette période, il développe et applique des méthodes statistiques à l'analyse de divers problèmes médicaux. Il collabore à la rédaction de deux des livres de la collection Monographie de l'Institut national d'hygiène ; sous la direction de Pierre Florent Denoix. Entre 1951 et 1954, il est biostatisticien consultant à l'Organisation mondiale de la santé (OMS). Il enseigne la statistique mathématique, et les mathématiques appliquées à la biologie, à Poitiers, à Paris, à Nancy, entre 1950 et 1955. En 1953, l'OMS l'envoie en Indonésie dans le cadre d’une mission pour lutter contre le pian, une maladie infectieuse chronique des pays tropicaux. Il y rencontre sa seconde épouse Hariati Soerosoegondo.
Il soutient en 1953 une thèse en mathématiques intitulée Contributions aux applications statistiques de la théorie de l'information. À partir de 1953, Schützenberger est chercheur au CNRS pendant trois ans. Il travaille en théorie des demi-groupes, commence ses travaux en théorie des codes, publie en théorie des automates.
En 1956, il est invité au Research Laboratory of Electronics du Massachusetts Institute of Technology, où Shannon séjourne comme professeur invité. Il effectue de nombreux autres séjours aux États-Unis, au MIT durant les étés 1959, 1961, 1970, à l'université de Caroline du Nord en 1960-1961, à l'université Harvard en 1961-1962. Il est à l'université de Pennsylvanie au printemps 1963, à l'université de Californie à Berkeley au printemps 1967. Il est consultant à l'IBM Research Center durant l'été 1962, et à la RAND Corporation en été 1966.
En 1957, Schützenberger est nommé professeur à l'université de Poitiers, où il enseigne notamment la statistique, de 1957 à 1963. C'est la période où il développe la théorie des codes et la théorie algébrique des langages formels, basée sur les séries formelles en variables non commutatives. Durant l'année 1961-1962, il est enseignant à la faculté de médecine de Harvard. Il retourne au CNRS durant l'année 1963-1964 comme directeur de recherches à l'Institut Blaise Pascal. En 1964, il est nommé professeur à la Faculté des sciences de Paris, puis, après la création des universités parisiennes, à l'université Paris-VII en 1970. Schützenberger est consultant à la direction scientifique de l'OMS de 1969 à 1980. Il est directeur scientifique à l'IRIA (ancien nom de l'INRIA) de 1968 à 1972.
En 1979, Schützenberger est élu correspondant de l'Académie des sciences. Il en est élu membre en 1988.
Ami de Boris Vian, il a inspiré le personnage du docteur Schutz, héros du roman Et on tuera tous les affreux. Proche de Raymond Queneau, il a été invité d'honneur de l'Oulipo en 1963.
Dans les années 80 à 90, Schützenberger devient anti-darwiniste, remettant en cause un certain nombre de principes fondamentaux de l'évolutionnisme. Le magazine La Recherche publie un entretien avec Schützenberger qui déclenche une polémique virulente : nombreuses lettres envoyées par les lecteurs, articles dans Charlie Hebdo et Le Monde, réponses des biologistes.
Il est, avec Noam Chomsky, un pionnier de la théorie des langages. Ses travaux ont porté sur la théorie des demi-groupes, sur la théorie algébrique des codes en longueur variable, la théorie des automates finis, les séries formelles en variables non commutatives, les transductions rationnelles. Il est l'un des fondateurs de la combinatoire des mots.
Il est un des créateurs de la combinatoire du monoïde plaxique, de son emploi dans les tableaux de Young, et de ses applications dans l'étude du groupe symétrique.
En algèbre, en théorie des demi-groupes, un groupe de Schützenberger est un groupe associé à une classe de la relation de Green H. Les groupes de Schützenberger associés à des H-classes différentes sont différentes, mais les groupes des H-classes d'une même D-classe sont isomorphes. De plus, si une H-classe est un groupe, le groupe de Schützenberger de cette H-classe est isomorphe à la H-classe elle-même. En fait, il y a deux groupes de Schützenberger associés à une H-classe, et ils sont anti-isomorphes (en).
Les groupes de Schützenberger ont été découverts par Schützenberger en 1957.
La terminologie apparaît dans le livre d'Alfred H. Clifford et Gordon B. Preston.
Le théorème de Chomsky-Schützenberger affirme que pour tout langage algébrique L, il existe un langage de Dyck D, un langage rationnel K et un morphisme alphabétique φ (c'est-à-dire tel que l'image d'une lettre est une lettre ou le mot vide) tels que
Ce théorème signifie que les langages de Dyck sont les langages algébriques les plus « typiques ». Schützenberger introduit également, dans un autre article, les automates à pile.
Séries formelles en variables non commutatives
Une série formelle sur un alphabet A à coefficients dans un demi-anneau (ou semi-anneau) K est une application S du monoïde libre A∗ dans K. La valeur de S pour un mot w est notée (S,w) et la série elle-même est écrite