Marcel-Paul Schützenberger

Marcel-Paul Schützenberger Marcel-Paul Schützenberger w 1972 roku. Biografia

Narodziny	24 października 1920 r Paryż
Śmierć	29 lipca 1996 Paryż
Narodowość	Francuski
Trening	Uniwersytet Paryski Uniwersytet Poitiers
Zajęcia	Matematyk , informatyk , statystyk , profesor uniwersytetu , lekarz
Tata	Pierre Schützenberger
Rodzeństwo	Jean-Paul Schützenberger
Małżonka	Anne Ancelin-Schützenberger (od1948 w 1949)
Pokrewieństwo	Paul Schützenberger (pradziadek) Léon Schützenberger (dziadek)

Inne informacje

Pracował dla	Uniwersytet w Poitiers
Pole	Kombinatoryczny
Członkiem	Academy of Sciences Amerykańska Akademia Sztuki i Nauki
Kierownicy prac dyplomowych	Georges Darmois , Albert Châtelet
Nagrody	Członek Francuskiej Akademii Nauk

Marcel-Paul Schützenberger (ur24 października 1920 rw Paryżu , zmarł dnia29 lipca 1996w Paryżu) jest francuskim naukowcem . Jego badania początkowo koncentrowały się na medycynie i biologii , ale najbardziej znany jest ze swojej pracy w matematyce , informatyce teoretycznej i kombinatoryce . Jest twórcą kombinatoryki słów i pionierem teorii kodów o zmiennej długości. Odegrał decydującą rolę w tworzeniu informatyki teoretycznej we Francji, o czym świadczy liczba jego uczniów.

Biografia

W młodości komunista Marcel-Paul Schützenberger działał w ruchu oporu podczas II wojny światowej . Pod koniec wojny był bliskim współpracownikiem Charlesa Tillona i członkiem jego gabinetu ministerialnego.

W 1948 roku ożenił się z Anne Ancelin Schützenberger i rozwiedli się kilka lat później.

Marcel-Paul Schützenberger uzyskał stopień doktora medycyny w 1949 r. Od 1948 do 1953 r. Był pracownikiem naukowym, następnie pracownikiem naukowym w Państwowym Zakładzie Higieny , a od 1948 r. Do Centrum Genetyki Szpitala Saint-Louis pełnił funkcję asystenta konsultanta . 1954. W tym okresie opracował i zastosował metody statystyczne do analizy różnych problemów medycznych. W latach 1951-1954 konsultował biostatystykę w Światowej Organizacji Zdrowia (WHO). Uczył statystyki matematycznej i matematyki stosowanej w biologii w Poitiers, Paryż, Nancy w latach 1950–1955. W 1953 r. WHO wysłała go do Indonezji w ramach misji walki z ziewami , przewlekłą chorobą zakaźną krajów tropikalnych. Tam poznał swoją drugą żonę Hariati Soerosoegondo.

W 1953 r. Obronił pracę magisterską z matematyki pt. Przyczyny do statystycznych zastosowań teorii informacji . Od 1953 roku Schützenberger był przez trzy lata pracownikiem naukowym CNRS . Zajmuje się teorią półgrup , zajmuje się teorią kodów , publikuje w teorii automatów .

W 1956 roku został zaproszony do Laboratorium Badań Elektroniki na Massachusetts Institute of Technology , gdzie Shannon przebywał jako visiting professor. Odbył liczne inne pobyty w Stanach Zjednoczonych, na MIT latem 1959, 1961, 1970, na Uniwersytecie Karoliny Północnej w latach 1960-1961, na Uniwersytecie Harvarda w latach 1961-1962. Był na University of Pennsylvania , na wiosnę 1963 roku, na Uniwersytecie Kalifornijskim w Berkeley na wiosnę 1967. Był konsultantem IBM Research Center w lecie 1962 roku, a do RAND Corporation w lecie 1966.

W 1957 Schützenberger został mianowany profesorem na Uniwersytecie w Poitiers , gdzie wykładał statystykę od 1957 do 1963. Był to okres, w którym rozwinął teorię kodów i algebraiczną teorię języków formalnych, opartą na szeregach. . W latach 1961-62 uczył w Harvard Medical School. Wrócił do CNRS w latach 1963-64 jako dyrektor badawczy w Blaise Pascal Institute. W 1964 r. Został mianowany profesorem na Wydziale Nauk w Paryżu, a następnie, po utworzeniu uniwersytetów paryskich, w 1970 r. Na Uniwersytecie Paris-VII . Schützenberger był konsultantem dyrekcji naukowej WHO w latach 1969-1980. Był dyrektorem naukowym w IRIA (dawna nazwa INRIA ) od 1968 do 1972 roku.

W 1979 roku Schützenberger został wybrany na korespondenta Akademii Nauk . Został wybrany na członka w 1988 roku.

Przyjaciel Borysa Viana , zainspirował postać doktora Schutza, bohatera powieści I zabijemy wszystkich okropnych . Blisko Raymonda Queneau był gościem honorowym w Oulipo w 1974 roku.

Prace naukowe

Wraz z Noamem Chomskim jest pionierem teorii języków . Jego prace koncentrują się na teorii półgrup, algebraicznej teorii kodów o zmiennej długości, teorii automatów skończonych, szeregach formalnych w zmiennych nieprzemiennych, przemianach wymiernych. Jest jednym z twórców kombinatoryki słów . Jest jednym z twórców kombinatoryki monoidy plaxicznej , jej wykorzystania w tablicach Younga i jej zastosowań w badaniu grupy symetrycznej.

Teoria półgrupowa

W Algebra w teorii naczepy grup , grupa Schützenberger jest grupa związany z klasą związku zielonej H . Grupy Schützenbergera powiązane z różnymi klasami H są różne, ale grupy klas H tej samej klasy D są izomorficzne . Ponadto, jeśli klasa H jest grupą, grupa Schützenbergera tej klasy H jest izomorficzna z samą klasą H. W rzeczywistości istnieją dwie grupy Schützenbergera związane z klasą H i są one antyizomorficzne  (in) .

Grupy Schützenbergera zostały odkryte przez Schützenbergera w 1957 roku. Terminologia pojawia się w książce Alfreda H. Clifforda i Gordona B. Prestona.

Teoria języków formalnych

Chomsky-Schützenberger twierdzenie stwierdza, że dla każdego języka algebraicznych jest język Dyck , o racjonalny język i alfabetyczne morfizmem (to znaczy takie, że obraz listu jest literą lub słowo opróżnić), takie jak L{\ displaystyle L} re{\ displaystyle D} K.{\ displaystyle K}φ{\ displaystyle \ varphi}

L=φ(re∩K.){\ Displaystyle L = \ varphi (D \ nasadka K)}

To twierdzenie oznacza, że ​​języki Dycka są najbardziej „typowymi” językami algebraicznymi. Schützenberger przedstawia również automaty zasilane bateryjnie w innym artykule .

Szeregi formalne w zmiennych nieprzemiennych

Formalne serie na alfabet współczynnikach w pół-pierścienia (lub pół-ring) jest odwzorowaniem w wolnej monoid in . Wartość dla słowa zauważyć, a sama seria jest napisane W{\ displaystyle A} K.{\ displaystyle K}S{\ displaystyle S} W∗{\ displaystyle A ^ {*}}K.{\ displaystyle K}S{\ displaystyle S}w{\ displaystyle w}(S,w){\ displaystyle (S, w)}

S=∑w∈W∗(S,w)w{\ Displaystyle S = \ suma _ {w \ w A ^ {*}} (S, w) \, w}.

W serii artykułów opublikowanych w latach sześćdziesiątych Schützenberger opracował teorię wymiernych i algebraicznych serii nieprzemiennych, która rozszerzyła i pogłębiła teorię języków formalnych. Wprowadzenie algebry liniowej pozwala z jednej strony na kwantyfikację niejednoznaczności w językach algebraicznych, az drugiej na uzyskanie dowodów algebraicznych. Teoria wymiernych szeregów w jednej zmiennej rozciąga się szczególnie na wymierne szeregi w kilku zmiennych. Szereg jest racjonalny, jeśli jest otrzymywany z wielomianów przez skończoną liczbę operacji dodawania, mnożenia i gwiazd Kleene (pod warunkiem, że stały człon szeregu wynosi zero): S{\ displaystyle S}

S∗=∑nie≥0Snie{\ Displaystyle S ^ {*} = \ suma _ {n \ geq 0} S ^ {n}}.

Liniowe przedstawienie porządku jest tryplet , w którym , jest morfizmem i . Reprezentacja rozpoznaje serię, jeśli dla dowolnego słowa . Reprezentacja liniowa jest rozszerzeniem zwykłych automatów skończonych, czasami nazywanych automatem ważonym . Szereg jest rozpoznawalny, jeśli istnieje reprezentacja liniowa, która ją rozpoznaje. NIE{\ displaystyle N}ρ=(λ,μ,γ){\ Displaystyle \ rho = (\ lambda, \ mu, \ gamma)}λ∈K.1×NIE{\ displaystyle \ lambda \ in K ^ {1 \ razy N}}μ:W∗→K.NIE×NIE{\ Displaystyle \ mu: A ^ {*} \ do K ^ {N \ razy N}}γ∈K.NIE×1{\ Displaystyle \ gamma \ w K ^ {N \ razy 1}}S{\ displaystyle S}(S,w)=λμ(w)γ{\ Displaystyle (S, w) = \ lambda \ mu (w) \ gamma}w{\ displaystyle w}S{\ displaystyle S}

Szereg jest algebraiczny, jeśli jest składową rozwiązania skończonego układu równań wielomianowych. Teoria szeregów algebraicznych jest podstawą wielu wyników kombinatorycznego wyliczania obiektów.

Do najbardziej znanych wyników Schützenberger należą:

• Twierdzenie Kleene-Schützenbergera  : Dla każdego półpierścienia i dowolnego skończonego alfabetu istnieje równość między szeregiem wymiernym a rozpoznawalnym szeregiem ze współczynnikami w  ;K.{\ displaystyle K}W{\ displaystyle A}W{\ displaystyle A}K.{\ displaystyle K}

• Twierdzenie Jungena-Schützenbergera  : Dla każdego przemiennego półpierścienia i dowolnego alfabetu skończonego iloczyn Hadamarda szeregu algebraicznego i szeregu wymiernego jest nadal szeregiem algebraicznym.K.{\ displaystyle K}W{\ displaystyle A}

Języki racjonalne bez gwiazdy

Racjonalny język jest bez gwiazdy ( star-Free Język angielski) jeżeli można otrzymać z liter alfabetu i zbioru pustego przez skończonego zbioru operacji logicznych i konkatenacji , ale bez gwiazdy operacji . Na przykład język słów w alfabecie , które nie zawierają dwóch kolejnych liter, jest bezgwiazdowy. Rzeczywiście, to zestaw jest określona , w którym oznacza komplementarnej części o . {w,b}{\ displaystyle \ {a, \, b \}}w{\ displaystyle a}(∅vsww∅vs)vs{\ Displaystyle (\ emptyset ^ {c} aa \ emptyset ^ {c}) ^ {c}}Xvs{\ displaystyle X ^ {c}}X{\ displaystyle X}{w,b}∗{\ Displaystyle \ {a, \, b \} ^ {*}}

Schützenberger scharakteryzował języki bezgwiazdowe jako języki, których monoid syntaktyczny jest skończony i aperiodyczny . Wynik ten jest punktem wyjścia dla teorii odmian języków formalnych.

Języki bez gwiazd mają inne cechy. Są to języki, które można zdefiniować w logice monadycznej pierwszego rzędu za pomocą operacji rzędu, oznaczonej jako FO [<].

Są to również języki akceptowane przez automaty bez liczników i jako języki definiowalne w liniowej logice temporalnej.

Kombinatoryczne grupy symetrycznej

Korespondencji Robinson-Schensted ustanawia bijection pomiędzy grupą symetrycznego i pary ( P, P ) z młodych macierzy . Schützenberger zawdzięczamy opis wielu właściwości konstrukcji Schensted. Schützenberger wprowadził również pozornie bardzo prosty algorytm, grę teaserową , która w szczególności zapewnia środki do skonstruowania tablicy P związanej z permutacją.

Rodzina

Marcel-Paul Schutzenberger, znany jako Marco, był synem psychiatry Pierre'a Schützenbergera i wnukiem inżyniera Léona Schützenbergera .

Jego pradziadek, chemik Paul Schützenberger , założył ESPCI w Paryżu w 1882 roku.

Bratem Marco był kompozytor Jean-Paul Schützenberger .

Marco miał córkę Hélène Schützenberger ze swoją pierwszą żoną, psycholog Anne Ancelin Schützenberger , a także syna Mahara Schützenbergera z drugą żoną. Ten ostatni zmarł bardzo młodo. W jego hołdzie powstała nagroda.

Publikacje

Aby przeczytać pracę Marcela-Paula Schützenbergera, zobacz stronę w przypisie.

• Różnorodność niektórych rodzajów raka. Pierre Florent Denoix, Paryż, 1954 r. ( OCLC 252601623 )
• Geometryczna teoria wielomianów Eulera. z Dominique Foata , Berlin, Heidelberg, Nowy Jork, Springer, 1970. ( OCLC 249981596 )
• Triangle de pansies , z Alainem Connesem i André Lichnerowiczem , Paryż, O. Jacob; Saint-Gély du Fesc: Espace 34, 2000. ( ISBN  9782738107626 )
• Wady darwinizmu , badań , N O  283Styczeń 1996
• Prace kompletne , pod redakcją Jean Berstel, Alain Lascoux i Dominique Perrin , Institut Gaspard-Monge, Université Paris-Est, 2009. ( OCLC 690381304 )

Cena £

• Nagroda Peano 2001 (pośmiertnie) za książkę Triangle de Thoughts , z Alainem Connesem i André Lichnerowiczem ; nagroda przyznana przez Associazione Subalpina Mathesis .

Uwagi i odniesienia

Uwagi

1. Dzieła Marcela-Paula Schützenbergera .

Bibliografia

1. Schützenberger 629 naukowych potomków patrz (w) „  Marcel-Paul Schützenberger  ” na stronie Mathematics Genealogy Project .
2. Robert Cori i Dominique Perrin , "  Wprowadzenie do wkładu naukowego Marcel-Paul Schützenberger  ", 1024 - Bulletin de la société Informatique de France , n o  9,listopad 2016, s.  35-49 ( czytaj online [PDF] ).
3. Pierre-Louis Curien, „  A Brief Scientific Biography of Maurice Nivat  ”, Theoretical Computer Science , vol.  281, 2002), s.  3-23 ( czytaj online ).
4. P. Mounier-Kuhn, Computing in France, from II World War to the Calculus plan. The Emergence of a Science , Paryż, PUPS, 2010, rozdz. 3 i 4.
5. „Okres Saint-Germain-des-Prés  ” M.-P. O Schützenbergerze wspomina Paul Braffort w książce The Great Doctor Marco .
6. (w) Noam Chomsky i Marcel-Paul Schützenberger, „The Algebraic Theory of Context-Free Languages” w: P. Braffort Hirschberg i D. (red.), Computer Programming and Formal Systems , North Holland , 1963, s. 118-161.
7. (w) Marcel-Paul Schützenberger , „  D -reprezentacja półgrup  ” , SARC , vol.  244,1957, s.  1994–1996 (MR 19, 249).
8. (w) Alfred H. Clifford i Gordon B. Preston , Algebraic Theory of Semigroups. Lot. Ja , Providence, RI, AMS ,1961, 352  pkt. ( ISBN  978-0-8218-0272-4 , czytaj online ), Link  Recenzje matematyczne .
9. (w) Marcel-Paul Schützenberger , „  to skończone monoidy MAJĄCE tylko trywialne podgrupy  ” , Information & Computation , vol.  8, N O  21965, s.  190–194 ( czytaj online [PDF] ).
10. (w) Volker Diekert i Paul Gastin, Logic and Automata: History and Perspectives , Amsterdam University Press,2008( ISBN  9789053565766 , przeczytaj online [PDF] ) , „Języki definiowalne pierwszego rzędu”.
11. (w) Robert McNaughton i Seymour Papert , Counter-free Automata , Cambridge, MIT Press ,1971, 163  pkt. ( ISBN  978-0-262-13076-9 , LCCN  71153294 ).
12. (w) Johan AW Kamp  (w :) , Tense Logic and the Theory of Linear Order , University of California w Los Angeles (UCLA)1968.
13. (w) MAA van Leeuwen , „Robinson Schensted connection” w Encyklopedii Matematyki , Springer online ( czytaj online ).
14. (it) Lista nagród Peano od 2000 do 2015 , [PDF].

Zobacz też

Bibliografia

Szeregi formalne w zmiennych nieprzemiennych są omówione w następujących książkach:

• (en) Jean Berstel i Christophe Reutenauer, Nieprzemienne serie wymierne z aplikacjami , Cambridge University Press, 2011.
• (en) M. Droste, W. Kuich i H. Vogler (red.), Handbook of Weighted Automata , Springer-Verlag, 2009.
• (en) Jacques Sakarovitch, Elementy teorii automatów , Cambridge University Press, 2009.

Powiązane artykuły

• M. Lothaire , pseudonim grupy matematyków ze szkoły Schützenbergera
• Schützenberger (rodzina)

Linki zewnętrzne

• Strona poświęcona Marcelowi-Paulowi Schützenbergerowi , znajdująca się na terenie Gaspard-Monge Institute of Electronics and Computer Science na Paris-Est Marne-la-Vallée University
• Zbiór hołdów oddanych przez jego kolegów na stronie Lotharingien Seminar of Combinatorics
• (en) John J. O'Connor i Edmund F. Robertson , „Marcel Paul Schützenberger” , w archiwum MacTutor History of Mathematics , University of St Andrews ( czytaj online ).
• Dokumentacja urzędowa  :
  • Plik wirtualnego organu międzynarodowego
  • Międzynarodowy identyfikator nazwy normy
  • Biblioteka Narodowa Francji ( dane )
  • System dokumentacji uczelni
  • Biblioteka Kongresu
  • Gemeinsame Normdatei
  • Królewska Biblioteka Holenderska
  • Biblioteka Uniwersytecka w Polsce
  • Biblioteka Narodowa Katalonii
  • Norweska baza biblioteczna
  • Czeska Biblioteka Narodowa
  • Biblioteka Narodowa Łotwy
  • WorldCat Id
  • WorldCat