Marcel-Paul Schützenberger

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Schutzenberger.

Marcel-Paul Schützenberger (né le 24 octobre 1920 à Paris, mort le 29 juillet 1996 à Paris) est un scientifique français. Ses recherches ont d'abord porté sur la médecine et la biologie, mais il est 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.

Marcel-Paul Schützenberger en 1972

Biographie[modifier | modifier le code]

Communiste dans ses jeunes années, Marcel-Paul Schützenberger oeuvre dans la résistance pendant la 2ème guerre mondiale. À la fin de la guerre, il est un proche collaborateur de Charles Tillon et membre de son cabinet ministériel[1].

Marcel-Paul Schützenberger fait alors des études accélérées et 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. Entre 1951 et 1954, il est biostatisticien consultant à l'Organisation mondiale de la santé.

Il enseigne la statistique mathématique, et les mathématiques appliquées à la biologie, à Poitiers, à Paris, à Nancy, entre 1950 et 1955.

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, débute 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-62, il est enseignant à la Faculté de médecine de Harvard. Il retourne au CNRS durant l'année 1963-64 comme directeur de recherches à l'Institut Blaise Pascal[2]. En 1964, il est nommé professeur à la Faculté des Sciences de Paris, puis, après la création des universités parisiennes, à l'université de 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[3]. Proche de Raymond Queneau, il a été invité d'honneur de l'Oulipo en 1974.

Œuvres scientifiques[modifier | modifier le code]

Il est, avec Noam Chomsky, un pionnier de la théorie des langages[4]. 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.

Théorie des demi-groupes[modifier | modifier le code]

Article détaillé : Groupe de Schützenberger

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[5]. La terminologie apparaît dans le livre d'Alfred H. Clifford et Gordon B. Preston[6].

Théorie des langages formels[modifier | modifier le code]

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 \varphi (c'est-à-dire tel que l'image d'une lettre est une lettre ou le mot vide) tels que

L=\varphi(D\cap K)

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[modifier | modifier le code]

Une série formelle sur un alphabet A à coefficients dans un 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

S= \sum_{w\in A^*}(S,w)\,w.

Dans une série d'articles parus dans les années 1960, Schützenberge développe un théorie des séries non-commutatives rationnelles et algébriques qui étend et approfondie la théorie des langages formels. L'introduction de l'algèbre linéaire permet d'une part de quantifier l'ambiguïté dans les langages algébriques, et d'autre part d'obtenir des preuves algébriques. La théorie des séries rationnelles en une variable s'étend de manière remarquable aux séries rationnelles en plusieurs variables. Une série S est rationnelle si elle est obtenue à partir des polynômes par un nombre fini d'opérations d'addition, de multiplication et d'étoiles de Kleene (pourvu que le terme constant de la série soit nul) :

S^*= \sum_{n\ge0}S^n.

Une représentation linéaire d'ordre N est un triplet \rho=(\lambda,\mu,\gamma), où \lambda\in K^{1\times N}, \mu:A^*\to K^{N\times N} est un morphisme et \gamma\in K^{N\times 1}. La représentation reconnaît une série S si (S,w)=\lambda\mu(w)\gamma pour tout mot w. Une représentation linéaire est une extension des automates finis usuels, parfois appelée automate pondéré. Un série S est reconnaissable s'il existe une représentation linéaire qui la reconnaît.

Une série est algébrique si elle est une composante d'une solution d'un système fini d'équations polynomiales. La théorie des séries algébriques est à la base de nombreux résultats de dénombrements d'objets combinatoire.

Parmi les résultats de Schützenberger les plus connus, il y a :

Théorème de Kleene-Schützenberger : Pour tout semi-anneau K et tout alphabet fini A, il y a égalité entre les séries rationnelles et les séries reconnaissables sur A à coefficients dans K.

Théorème de Jungen-Schützenberger : Pour tout semi-anneau K commutatif et tout alphabet fini A, le produit de Hadamard d'une série algébrique et d'une série rationnelle est encore une série algébrique.

Langages rationnels sans étoile[modifier | modifier le code]

Article détaillé : langage sans étoile.

Un langage rationnel est sans étoile (star-free language en anglais) s'il peut être obtenu à partir des lettres d'un alphabet et de l'ensemble vide, par un ensemble fini d'opérations booléennes et de concaténations, mais sans l'opération étoile. Par exemple, le langage des mots sur l'alphabet \{a,\,b\} qui ne contiennent pas deux lettres a consécutives st sans étoile. En effet, c'est ensemble est défini par (\emptyset^c aa \emptyset^c)^c, où X^c dénote le complément d'une partie X de \{a,\,b\}^*.

Schützenberger a caractérisé les langages sans étoile comme les langages dont le monoïde syntaxique est fini et apériodique[7]. Ce résultat est le point de départ de la théorie des variétés des langages formels.

Les langages sans étoile possèdent d'autres caractérisations. Ce sont les langages définissables dans la logique monadique du premier ordre avec l'opération d'ordre, notée FO[<] [8]

Ce sont également les langages acceptés par les automates sans compteurs[9] and comme langages définissables en logique temporelle linéaire[10].

Combinatoire du groupe symétrique[modifier | modifier le code]

La correspondance de Robinson-Schensted établit une bijection entre le groupe symétrique et les paires (P,Q) de tableaux de Young. On doit à Schützenberger la description de nombreuses propriétés de la construction de Schensted. Schützenberger a aussi introduit un algorithme en apparence très simple, le jeu de taquin, qui donne en particulier un moyen de construire le tableau P associé à une permutation.

Publications[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. P.-L. Curien, Une brève biographie scientifique de Maurice Nivat, Theoretical Computer Science 281 (2002), 3-23
  2. P. Mounier-Kuhn, L’Informatique en France, de la seconde guerre mondiale au Plan Calcul. L’émergence d’une science, Paris, PUPS, 2010, ch. 3 et 4.
  3. La « période Saint-Germain-des-Prés » de M.-P. Schützenberger est évoquée par P. Braffort, dans Le grand Docteur Marco.
  4. (en) Noam Chomsky et Marcel-Paul Schützenberger, « The Algebraic Theory of Context-Free Languages » dans P. Braffort et D. Hirschberg (éds), Computer Programming and Formal Systems, North Holland, 1963, p. 118-161.
  5. (en) Marcel-Paul Schützenberger, « D-représentation des demi-groupes », CRAS, vol. 244,‎ 1957, p. 1994–1996 (MR 19, 249)
  6. (en) Alfred H. Clifford et Gordon B. Preston, The algebraic theory of semigroups. Vol. I, Providence, R.I., AMS,‎ 1961 (ISBN 978-0-8218-0272-4), lien Math Reviews
  7. (en) Marcel-Paul Schützenberger, « On finite monoids having only trivial subgroups », Information and Computation, vol. 8, no 2,‎ 1965, p. 190–194 (lire en ligne)
  8. (en) Volker Diekert et Paul Gastin, Logic and automata: history and perspectives, Amsterdam University Press,‎ 2008 (ISBN 9789053565766, lire en ligne), « First-order definable languages »
  9. (en) Robert McNaughton et Seymour Papert, Counter-free Automata, Cambridge, MIT Press,‎ 1971 (ISBN 978-0-262-13076-9, LCCN 71153294)
  10. (en) Johan A. W. Kamp (en), Tense Logic and the Theory of Linear Order, University of California at Los Angeles (UCLA),‎ 1968

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Les séries formelles en variables non commutatives sont traités dans les livres suivants :

  • (en) J. Berstel et C. Reutenauer, Noncommutative Rational Series with Applications, Cambridge University Press, 2011.
  • (en) M. Droste, W. Kuich et H. Vogler (eds.), Handbook of Weighted Automata, Springer-Verlag, 2009.
  • (en) J. Sakarovitch, Elements of Automata Theory, Cambridge University Press, 2009.

Article connexe[modifier | modifier le code]

M. Lothaire, pseudonyme d'un groupe de mathématiciens de l'école de Schützenberger

Liens externes[modifier | modifier le code]