Шютценберже, Марсель-Поль

Марсель-Поль Шютценберже

фр. Marcel-Paul Schützenberger

Файл:Schützenberger.jpeg

Марсель-Поль Шютценберже в 1972 году.

Дата рождения

24 октября 1920 года

Место рождения

Париж

Дата смерти

29 июля 1996 года

Место смерти

Париж

Гражданство

Франция

Род деятельности

математик

Награды и премии

Член Академии наук

Марсель-Поль Шютценберже (фр. Marcel-Paul Schützenberger; ^{[Нет даты!]}) — французский учёный, математик и врач. Известен работами в области теоретической информатики и комбинаторики, основатель комбинаторики слов и пионер теории кодов переменной длины.

Биография

Во время Второй мировой войны Марсель-Поль Шютценберже участвовал в движении Сопротивления. В конце войны он был близким сотрудником Шарля Тийона и членом его министерского кабинета. В 1948 году он женился на Анн Анселен Шютценберже; через несколько лет они развелись.

Марсель-Поль Шютценберже получил степень доктора медицины в 1949 году. С 1948 по 1953 год он был научным сотрудником Национального института гигиены, а с 1948 по 1954 год — ассистентом-консультантом в Центре генетики больницы Сен-Луи. В этот период он разрабатывал и применял статистические методы для анализа различных медицинских проблем. Он участвовал в написании двух книг из серии «Монографии Национального института гигиены» под руководством Пьера Флорана Денуа. В период с 1951 по 1954 год он работал консультантом-биостатистиком во Всемирной организации здравоохранения (ВОЗ). С 1950 по 1955 год он преподавал математическую статистику и прикладную математику в биологии в Пуатье, Париже и Нанси. В 1953 году ВОЗ направила его в Индонезию с миссией по борьбе с фрамбезией, хроническим инфекционным заболеванием тропических стран. Там он встретил свою вторую жену Хариати Суросоэгондо.

В 1953 году он защитил диссертацию по математике на тему «Вклад в статистические приложения теории информации». С 1953 года Шютценберже в течение трёх лет работал исследователем в Национальном центре научных исследований (CNRS). Он работал в области теории полугрупп, начал исследования в теории кодов и публиковал работы по теории автоматов.

В 1956 году он был приглашён в Исследовательскую лабораторию электроники Массачусетского технологического института (MIT), где Клод Шеннон находился в качестве приглашённого профессора. Он совершил множество других поездок в США: в MIT летом 1959, 1961 и 1970 годов, в Университет Северной Каролины в Чапел-Хилле в 1960—1961 годах, в Гарвардский университет в 1961—1962 годах. Весной 1963 года он находился в Пенсильванском университете, а весной 1967 года — в Калифорнийском университете в Беркли. Летом 1962 года он был консультантом в Исследовательском центре IBM, а летом 1966 года — в RAND Corporation.

В 1957 году Шютценберже был назначен профессором Университета Пуатье, где преподавал статистику с 1957 по 1963 год. В этот период он разрабатывал теорию кодов и алгебраическую теорию формальных языков, основанную на формальных рядах от некоммутирующих переменных. В 1961—1962 учебном году он преподавал на медицинском факультете Гарварда. В 1963—1964 учебном году он вернулся в CNRS в качестве директора по исследованиям в Институт Блеза Паскаля. В 1964 году он был назначен профессором Парижского факультета наук, а после создания парижских университетов — в Университет Париж VII в 1970 году. Шютценберже был консультантом научного руководства ВОЗ с 1969 по 1980 год. С 1968 по 1972 год он был научным директором IRIA (прежнее название INRIA).

В 1979 году Шютценберже был избран членом-корреспондентом Академии наук Франции. В 1988 году он стал её действительным членом.

Будучи другом Бориса Виана, он послужил прототипом доктора Шютца, героя романа «И всех уродов убьют». Близкий к Раймону Кено, он был почётным гостем УЛИПО в 1963 году.

В 1980-х и 1990-х годах Шютценберже стал антидарвинистом, ставя под сомнение ряд фундаментальных принципов эволюционизма. Журнал La Recherche опубликовал интервью с Шютценберже, которое вызвало ожесточённую полемику: многочисленные письма читателей, статьи в Charlie Hebdo и Le Monde, ответы биологов.

Научные труды

Вместе с Ноамом Хомским он является пионером теории языков. Его работы были посвящены теории полугрупп, алгебраической теории кодов переменной длины, теории конечных автоматов, формальным рядам от некоммутирующих переменных и рациональным трансдукциям. Он является одним из основателей комбинаторики слов. Он является одним из создателей комбинаторики плаксического моноида, её использования в таблицах Юнга и её приложений в изучении симметрической группы.

Теория полугрупп

В алгебре, в теории полугрупп, группа Шютценберже — это группа, связанная с классом отношения Грина H. Группы Шютценберже, связанные с различными H-классами, различны, но группы H-классов одного и того же D-класса изоморфны. Кроме того, если H-класс является группой, группа Шютценберже этого H-класса изоморфна самому H-классу. Фактически, с H-классом связаны две группы Шютценберже, и они антиизоморфны.

Группы Шютценберже были открыты Шютценберже в 1957 году. Терминология появилась в книге Альфреда Х. Клиффорда и Гордона Б. Престона.

Теория формальных языков

Теорема Хомского — Шютценберже утверждает, что для любого контекстно-свободного языка $L$ существует язык Дика $D$, регулярный язык $K$ и алфавитный морфизм $\varphi$ (то есть такой, что образ буквы является буквой или пустым словом) такие, что

$L=\varphi (D\cap K)$

Эта теорема означает, что языки Дика являются наиболее «типичными» контекстно-свободными языками. Шютценберже также ввёл в другой статье автоматы с магазинной памятью.

Формальные ряды от некоммутирующих переменных

Формальный ряд над алфавитом $A$ с коэффициентами в полукольце $K$ — это отображение $S$ свободного моноида $A^{*}$ в $K$. Значение $S$ для слова $w$ обозначается $(S,w)$, а сам ряд записывается как

$S=\sum _{w\in A^{*}}(S,w)\,w$.

В серии статей, опубликованных в 1960-х годах, Шютценберже разработал теорию некоммутативных рациональных и алгебраических рядов, которая расширяет и углубляет теорию формальных языков. Введение линейной алгебры позволяет, с одной стороны, количественно оценить неоднозначность в контекстно-свободных языках, а с другой — получить алгебраические доказательства. Теория рациональных рядов от одной переменной замечательным образом обобщается на рациональные ряды от нескольких переменных. Ряд $S$ является рациональным, если он получен из многочленов конечным числом операций сложения, умножения и звезды Клини (при условии, что постоянный член ряда равен нулю):

$S^{*}=\sum _{n\geq 0}S^{n}$.

Линейное представление порядка $N$ — это тройка $\rho =(\lambda ,\mu ,\gamma )$, где $\lambda \in K^{1\times N}$, $\mu :A^{*}\to K^{N\times N}$ — морфизм, а $\gamma \in K^{N\times 1}$. Представление распознаёт ряд $S$, если $(S,w)=\lambda \mu (w)\gamma$ для любого слова $w$. Линейное представление является расширением обычных конечных автоматов, иногда называемым взвешенным автоматом. Ряд $S$ является распознаваемым, если существует линейное представление, которое его распознаёт.

Ряд является алгебраическим, если он является компонентой решения конечной системы полиномиальных уравнений. Теория алгебраических рядов лежит в основе многих результатов перечисления комбинаторных объектов.

Среди наиболее известных результатов Шютценберже:

• Теорема Клини — Шютценберже: Для любого полукольца $K$ и любого конечного алфавита $A$ классы рациональных рядов и распознаваемых рядов над $A$ с коэффициентами в $K$ совпадают;
• Теорема Юнгена — Шютценберже: Для любого коммутативного полукольца $K$ и любого конечного алфавита $A$ произведение Адамара алгебраического ряда и рационального ряда также является алгебраическим рядом.

Регулярные языки без звезды

Регулярный язык является языком без звезды (star-free language), если он может быть получен из букв алфавита и пустого множества с помощью конечного числа булевых операций и конкатенаций, но без операции звезды Клини. Например, язык слов над алфавитом $\{a,\,b\}$, не содержащих двух подряд идущих букв $a$, является языком без звезды. Действительно, это множество определяется как $(\emptyset ^{c}aa\emptyset ^{c})^{c}$, где $X^{c}$ обозначает дополнение подмножества $X$ в $\{a,\,b\}^{*}$.

Шютценберже охарактеризовал языки без звезды как языки, синтаксический моноид которых конечен и апериодичен. Этот результат является отправной точкой теории многообразий формальных языков.

Языки без звезды имеют и другие характеризации. Это языки, определимые в монадической логике первого порядка с операцией порядка, обозначаемой FO[<].

Это также языки, распознаваемые автоматами без счётчиков, и языки, определимые в линейной темпоральной логике.

Комбинаторика симметрической группы

Соответствие Робинсона — Шенстеда устанавливает биекцию между симметрической группой и парами (P,Q) таблиц Юнга. Шютценберже описал многие свойства конструкции Шенстеда. Шютценберже также ввёл алгоритм, известный как пятнашки Шютценберже, который даёт способ построения таблицы P, связанной с перестановкой.

Награды

• Член Академии наук Франции.
• Член Американской академии искусств и наук.
• Премия Пеано 2001 года (посмертно) за книгу «Треугольник мыслей», написанную совместно с Аленом Конном и Андре Лихнеровичем, присуждённая Associazione Subalpina Mathesis.

Семья

Марсель-Поль Шютценберже, известный как Марко, был сыном психиатра Пьера Шютценберже и внуком инженера Леона Шютценберже.

Его прадед, химик Поль Шютценберже, основал Высшую школу промышленной физики и химии города Парижа (ESPCI) в 1882 году.

Брат Марко — композитор Жан-Поль Шютценберже.

У Марко была дочь Элен Шютценберже от первой жены, психолога Анн Анселен Шютценберже, и сын Махар Шютценберже от второй жены, Хариати Суросоэгондо.

Махар, родившийся 22 января 1957 года в Кембридже (Массачусетс), погиб 29 марта 1980 года в автокатастрофе под Парижем. Была учреждена премия для поощрения работ индонезийских исследователей, готовящих докторскую диссертацию во Франции. Индонезийская семья Махара создала в его честь ассоциацию «Yayasan Mahargijono Schützenberger Indonesia», занимающуюся начальным образованием.

Библиография

• Théorie géométrique des polynômes eulériens. avec Dominique Foata, Berlin, Heidelberg, New York, Springer, 1970.
• Triangle de pensées, avec Alain Connes et André Lichnerowicz, Paris, O. Jacob ; Saint-Gély du Fesc : Espace 34, 2000. ISBN 9782738107626
• Les failles du darwinisme, La Recherche, № 283, janvier 1996
• Œuvres complètes, éditées par Jean Berstel, Alain Lascoux et Dominique Perrin, Institut Gaspard-Monge, Université Paris-Est, 2009.

Литература

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

Ссылки

• Site consacré à Marcel-Paul Schützenberger, sur le site de l’Institut d'électronique et d’informatique Gaspard-Monge à l’université Paris-Est Marne-la-Vallée

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Шютценберже, Марсель-Поль», расположенная по адресу: — https://ru.ruwiki.ru/wiki/Шютценберже,_Марсель-Поль Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».