Fødsel |
24. oktober 1920 Paris |
---|---|
Død |
29. juli 1996 Paris |
Nasjonalitet | fransk |
Opplæring |
University of Paris University of Poitiers |
Aktiviteter | Matematiker , informatiker , statistiker , universitetsprofessor , lege |
Pappa | Pierre Schützenberger |
Søsken | Jean-Paul Schützenberger |
Ektefelle | Anne Ancelin-Schützenberger (fra1948 på 1949) |
Slektskap |
Paul Schützenberger (oldefar) Léon Schützenberger (bestefar) |
Jobbet for | University of Poitiers |
---|---|
Felt | Kombinatorisk |
Medlem av |
Academy of Sciences American Academy of Arts and Sciences |
Avhandlingsledere | Georges Darmois , Albert Châtelet |
Utmerkelser | Medlem av det franske vitenskapsakademiet |
Marcel-Paul Schützenberger (født den24. oktober 1920i Paris , døde den29. juli 1996i Paris) er en fransk forsker . Forskningen hans fokuserte først på medisin og biologi , men han er mest kjent for sitt arbeid innen matematikk , teoretisk informatikk og kombinatorikk . Han er grunnleggeren av ordets kombinatorikk og en pioner innen teorien om koder med variabel lengde. Han spilte en avgjørende rolle i opprettelsen av teoretisk informatikk i Frankrike, som det fremgår av antallet av disiplene hans.
Kommunistisk i sin ungdom, jobbet Marcel-Paul Schützenberger i motstanden under andre verdenskrig . På slutten av krigen var han en nær medarbeider av Charles Tillon og medlem av hans ministerkabinett.
I 1948 giftet han seg med Anne Ancelin Schützenberger, og de ble skilt noen år senere.
Marcel-Paul Schützenberger ble doktorgrad i medisin i 1949. Fra 1948 til 1953 var han forskningsassistent, deretter forsker ved National Institute of Hygiene , og han var konsulentassistent ved Genetics Centre of the Hospital. Saint-Louis fra 1948 til 1954. I løpet av denne perioden utviklet og brukte han statistiske metoder for analyse av ulike medisinske problemer. Mellom 1951 og 1954 konsulterte han biostatistiker i Verdens helseorganisasjon (WHO). Han underviste i matematisk statistikk og matematikk anvendt på biologi i Poitiers, Paris, Nancy, mellom 1950 og 1955. I 1953 sendte WHO ham til Indonesia som en del av et oppdrag for å kjempe mot kjevler , en kronisk smittsom sykdom i tropiske land. Der møtte han sin andre kone Hariati Soerosoegondo.
I 1953 forsvarte han en avhandling i matematikk med tittelen Bidrag til statistiske anvendelser av informasjonsteori . Fra 1953 var Schützenberger forsker ved CNRS i tre år. Han arbeider i teorien om halvgrupper , begynner sitt arbeid i teorien om koder , publiserer i teorien om automata .
I 1956 ble han invitert til Research Laboratory of Electronics ved Massachusetts Institute of Technology , hvor Shannon ble som gjesteprofessor. Han bodde mange andre opphold i USA, ved MIT somrene 1959, 1961, 1970, ved University of North Carolina i 1960-1961, ved Harvard University i 1961-1962. Han var ved University of Pennsylvania våren 1963, ved University of California i Berkeley våren 1967. Han var konsulent for IBM Research Center sommeren 1962 og for RAND Corporation sommeren 1966.
I 1957 ble Schützenberger utnevnt til professor ved Universitetet i Poitiers , hvor han underviste i statistikk, fra 1957 til 1963. Dette var perioden da han utviklet teorien om koder og den algebraiske teorien om formelle språk, basert på serieformell i ikke-kommutative variabler. . I løpet av 1961-62 underviste han ved Harvard Medical School. Han kom tilbake til CNRS i løpet av året 1963-64 som forskningsdirektør ved Institut Blaise Pascal. I 1964 ble han utnevnt til professor ved fakultetet for vitenskap i Paris, deretter, etter opprettelsen av de parisiske universitetene, ved Universitetet i Paris-VII i 1970. Schützenberger var konsulent for det vitenskapelige direktoratet for WHO fra 1969 til 1980 Han var vitenskapelig direktør ved IRIA (tidligere navn på INRIA ) fra 1968 til 1972.
I 1979 ble Schützenberger valgt til korrespondent for Academy of Sciences . Han ble valgt til medlem i 1988.
Venn av Boris Vian , han inspirerte karakteren til doktor Schutz, romanens helt Og vi vil drepe alt det forferdelige . Nær Raymond Queneau var han æresgjest på Oulipo i 1974.
Han er, sammen med Noam Chomsky , en pioner innen språkteorien . Hans arbeid har fokusert på teorien om halvgrupper, på den algebraiske teorien om koder i variabel lengde, teorien om endelige automater, formelle serier i ikke-kommutative variabler, rasjonelle transduksjoner. Han er en av grunnleggerne av kombinasjonen av ord . Han er en av skaperne av kombinatorikken til den plaksiske monoiden , bruken av den i Youngs tabeller og bruken av den i studiet av den symmetriske gruppen.
I algebra , i teorien for semi-grupper , en gruppe Schützenberger er en gruppe knyttet til en klasse av forhold Grønn H . Schützenberger-gruppene assosiert med forskjellige H- klasser er forskjellige, men gruppene av H- klasser av samme D- klasse er isomorfe . Videre, hvis en H- klasse er en gruppe, er Schützenberger-gruppen i denne H- klassen isomorf til selve H- klassen. Det er faktisk to grupper Schützenberger assosiert med H- klasse, og de er anti-isomorfe (in) .
Schützenberger-grupper ble oppdaget av Schützenberger i 1957. Terminologien vises i boken av Alfred H. Clifford og Gordon B. Preston.
The Chomsky-Schützenberger-setningen sier at det for ethvert algebraisk språk er et Dyck-språk , et rasjonelt språk og en alfabetisk morfisme (dvs. slik at bildet av en bokstav er en bokstav eller ordet tomt) som f.eks.
Denne setningen betyr at Dycks språk er de mest "typiske" algebraiske språkene. Schützenberger introduserer også batteridrevet automat i en annen artikkel .
En formell serie på et alfabet med koeffisienter i en halvring (eller halvring) er en kartlegging av den frie monoiden i . Verdien av for et ord blir notert og selve serien er skrevet
.I en serie artikler publisert på 1960-tallet utviklet Schützenberger en teori om rasjonelle og algebraiske ikke-kommutative serier som utvidet og utdypet teorien om formelle språk. Innføringen av lineær algebra tillater på den ene siden å kvantifisere tvetydigheten i algebraiske språk, og på den annen side å få algebraiske bevis. Teorien om rasjonelle serier i en variabel strekker seg bemerkelsesverdig til rasjonell serie i flere variabler. En serie er rasjonell hvis den er hentet fra polynomer ved et endelig antall tillegg, multiplikasjon og Kleene-stjerneoperasjoner (forutsatt at serieens konstante periode er null):
.En lineær fremstilling av orden er en triplett , hvor , er en morfisme og . Representasjonen gjenkjenner en serie hvis for noe ord . En lineær representasjon er en utvidelse av den vanlige endelige automaten, noen ganger kalt en vektet automat . En serie er gjenkjennelig hvis det er en lineær representasjon som gjenkjenner den.
En serie er algebraisk hvis den er en komponent i en løsning av et endelig system av polynomiske ligninger. Teorien om algebraiske serier er grunnlaget for mange resultater av kombinatorisk objektopptelling.
Blant de mest kjente Schützenberger-resultatene er:
Et rasjonelt språk er uten stjerne ( stjerneløst språk engelsk) hvis det kan oppnås fra bokstavene i alfabetet og det tomme settet med et endelig sett med boolske operasjoner og sammenkobling , men uten ' stjernedrift . Språket til ordene i alfabetet som ikke inneholder to bokstaver på rad, er for eksempel uten stjerne. Faktisk er det sett definert av , der betegner komplementet til en del av .
Schützenberger karakteriserte stjerneløse språk som språk hvis syntaktiske monoid er endelig og aperiodisk . Dette resultatet er utgangspunktet for teorien om varianter av formelle språk.
Stjerneløse språk har andre karakteriseringer. Dette er språkene som kan defineres i førsteordens monadisk logikk med ordreoperasjonen, betegnet FO [<].
Dette er også språkene som aksepteres av automater uten tellere og som definerbare språk i lineær tidslogikk.
Den Robinson-Schensted korrespondanse etablerer en Bijeksjon mellom den symmetriske gruppe og parene ( P, Q ) av unge matriser . Vi skylder Schützenberger beskrivelsen av mange egenskaper ved Schensted-konstruksjonen. Schützenberger introduserte også en tilsynelatende veldig enkel algoritme, teaserspillet , som spesielt gir et middel for å konstruere matrisen P assosiert med en permutasjon.
Marcel-Paul Schutzenberger, kjent som Marco, var sønn av psykiateren Pierre Schützenberger og barnebarnet til ingeniøren Léon Schützenberger .
Hans oldefar, kjemikeren Paul Schützenberger , grunnla ESPCI i Paris i 1882.
Broren til Marco var komponisten Jean-Paul Schützenberger .
Marco hadde en datter, Hélène Schützenberger, med sin første kone, psykolog Anne Ancelin Schützenberger , samt en sønn, Mahar Schützenberger, med sin andre kone. Sistnevnte døde veldig ung. En pris ble opprettet i hans hyllest.
For å lese arbeidet til Marcel-Paul Schützenberger, se siden i merknad.
Den formelle serien i ikke-kommutative variabler behandles i følgende bøker: