Януш (Джон) Antoni Brzozowski (10 мая 1935 - 24 октября 2019) был польско-канадский ученый и почетным профессором [1] в Университете Ватерлоо «s Дэвид Р. Cheriton Школы компьютерных наук . [2]
Януш Бжозовски | |
---|---|
Родившийся | |
Умер | 24 октября 2019 г. Дом Лизаард , Кембридж, Онтарио , Канада | (84 года)
Альма-матер | Университет Принстона |
Известен | Производная Бжозовского |
Научная карьера | |
Поля | Информатика |
Тезис | Методы регулярных выражений для последовательных схем (1962) |
Докторант | Эдвард Дж. Маккласки |
В 1962 году Бжозовский получил докторскую степень в области электротехники в Принстонском университете под руководством Эдварда Дж. Маккласки . Тема диссертации - Методы регулярных выражений для последовательных цепей . С 1967 по 1996 год он был профессором Университета Ватерлоо . Он известен за его вклад в математическую логику , теории цепей и теории автоматов .
Достижения в исследованиях
Brzozowski работал над регулярными выражениями и синтаксических полугрупп из формальных языков . [3] Результат был характеризации локально проверяемых событий , написанных вместе с Имре Саймона , который имел такое же влияние [4] на развитие алгебраической теории формальных языков как Марсель-Поль Шютценберже характеризации «s из звездных свободных языков .
В этой области сегодня по крайней мере три концепции носят имя Бжозовского в честь его вклада: первая - это гипотеза Бжозовского [5] о регулярности несчетных классов. Во- вторых, алгоритм Brzozowski в , [6] концептуально простой алгоритм для выполнения минимизации DFA . В-третьих, в справочнике Эйленберга по теории автоматов есть глава, посвященная так называемой иерархии Бжозовского [7] внутри языков без звезд , также известной как иерархия глубины точек . Любопытно, что Бжозовский был не только соавтором статьи, в которой определялась иерархия глубины точек и поднимался вопрос, является ли эта иерархия строгой [8], но позже он также был соавтором статьи, решающей эту проблему примерно через десять лет. [9] Иерархия Бжозовского приобрела еще большее значение после того, как Томас обнаружил связь между алгебраической концепцией глубины точки и глубиной чередования кванторов в логике первого порядка с помощью игр Эренфойхта – Фраисе . [10]
Он получил следующие академические награды и награды:
- Премия NSERC за научные обмены для Франции (1974–1975)
- Стипендия Японского общества содействия научным исследованиям (1984)
- Почетная грамота Ассоциации компьютерных исследований за выдающийся вклад и службу в качестве члена Совета директоров CRA (1992 г.)
- Заслуженный профессор Университета Ватерлоо , Канада (1996 год) [11]
- Медаль за заслуги перед католическим университетом Люблина, Польша (2001 г.)
- IBM Canada - пионер в области вычислительной техники (2005 г.) [12]
- Роль теории в информатике, однодневная конференция в честь 80-летия Джона Бжозовского (2015) [13]
- Награда за выслугу, Computer Science Canada / Informatique Canada (CS-CAN / INFO-CAN) (2016) [14]
- Премия CIAA 2017 Sheng Yu за лучшую работу по сложности правильных префиксно-выпуклых регулярных языков Дж. Бжозовски и К. Синнамон [15]
- Премия CIAA 2018 Sheng Yu Award за лучшую работу за сложность сборки перекрытий, подготовленная Дж. Бжозовским, Л. Кари, Б. Ли, М. Шикула [16]
Научно-исследовательские работы
- JA Brzozowski: Производные регулярных выражений, Журнал ACM 11 (4): 481–494 (1964)
- JA Brzozowski, I. Simon: Характеристики локально тестируемых событий, FOCS 1971, стр. 166–176
- Р. С. Коэн, Дж. А. Бжозовски: Глубина точек беззвездных событий. Журнал компьютерных и системных наук 5 (1): 1-16 (1971).
- JA Brzozowski, R. Knast: Точечная иерархия беззвездных языков бесконечна. Журнал компьютерных и системных наук 16 (1): 37–55 (1978).
Книги
- JA Brzozowski, M. Yoeli: Цифровые сети. Прентис-Холл, 1976 г.
- JA Brzozowski, C.-JH Seger: Асинхронные схемы. Springer-Verlag, 1995 г.
Заметки
- ^ "Джон Бжозовский" . Школа компьютерных наук Дэвида Р. Черитона . Проверено 21 декабря 2018 года .
- ^ https://www.legacy.com/obituaries/theglobeandmail/obituary.aspx?n=janusz-a-brzozowski&pid=194286993&fhid=30885
- ↑ Пин (1997)
- ^ Дикерт и др. (2008)
- ^ Де Лука и Varicchio (1997)
- ^ Шаллит (2009), гл. 3.10
- ^ Эйленберг (1974)
- ^ Коэн и Бжозовский (1971)
- ↑ Бжозовский и Кнаст (1979)
- ↑ Томас (1982)
- ^ Профиль Джона Бжозовского
- ↑ Pioneers of Computing in Canada, 2005, http://individual.utoronto.ca/klyons/files/pioneers.pdf , последнее посещение - 2 января 2019 г.
- ^ "Бжозовский 80: роль теории в компьютерных науках" . Школа компьютерных наук Дэвида Р. Черитона . 24 июня 2015 . Проверено 21 декабря 2018 года .
- ^ «Награды за заслуги | 2016» . Computer Science Canada / Information Canada (CS-CAN / INFO-CAN) . 2016 . Проверено 21 декабря 2018 года .
- ^ «22-я Международная конференция« Внедрение и применение автоматов | Премия Шэн Ю, 2017 » . Конференция по внедрению и применению автоматов (CIAA 2017) . 2017 . Проверено 21 декабря 2018 года .
- ^ «23-я Международная конференция по внедрению и применению автоматов | Премия Шэн Ю 2018» . 23-я Международная конференция по внедрению и применению автоматов (CIAA 2018) . 23 августа 2018 . Проверено 21 декабря 2018 года .
Рекомендации
- С. Эйленберг, Автоматы, языки и машины , Том Б. ISBN 0-12-234001-9
- В. Томас, Классификация регулярных событий в символической логике. J. Comput. Syst. Sci. 25 (3): 360-376 (1982).
- Ж.-Э. Пин, Синтаксические полугруппы , Глава 10 в "Справочнике по теории формального языка", Vol. 1, Г. Розенберг и А. Саломаа (ред.), Springer Verlag, (1997) Vol. 1. С. 679–746.
- А. де Лука и С. Вариккио, Условия регулярности и конечности , глава 11 в «Справочнике по теории формального языка», т. 1, Г. Розенберг и А. Саломаа (ред.), Springer Verlag, (1997) Vol. 1. С. 747–810.
- В. Дикерт, П. Гастин, М. Куфлейтнер, Обзор малых фрагментов логики первого порядка над конечными словами. Int. J. Found. Comput. Sci. 19 (3): 513-548 (2008).
- Дж. Шаллит, Второй курс формальных языков и теории автоматов , Cambridge University Press (2009)
Внешние ссылки
- Профиль Януша Бжозовского, Университет Ватерлоо
- Персональный сайт Бжозовского в университете Ватерлоо
- Зал славы теории вычислений
- Януш А. Бжозовский на сервере библиографии DBLP
- Конкатенационные иерархии Жан-Эрика Пина