Janusz (John) Antoni Brzozowski (10. Mai 1935 – 24. Oktober 2019) war ein polnisch-kanadischer Informatiker und Distinguished Professor Emeritus [ 1 ] an der David R. Cheriton School of Computer Science der University of Waterloo . [ 2 ]

1962 promovierte Brzozowski an der Princeton University im Bereich Elektrotechnik bei Edward J. McCluskey . Seine Dissertation befasste sich mit regulären Ausdrücken für sequentielle Schaltungen . Von 1967 bis 1996 war er Professor an der University of Waterloo . Er ist bekannt für seine Beiträge zur mathematischen Logik , Schaltungstheorie und Automatentheorie .

Forschungserfolge

Brzozowski beschäftigte sich mit regulären Ausdrücken und syntaktischen Halbgruppen formaler Sprachen . [ 3 ] Das Ergebnis waren Charakterisierungen lokal testbarer Ereignisse , die er zusammen mit Imre Simon verfasste und die einen ähnlichen Einfluss [ 4 ] auf die Entwicklung der algebraischen Theorie formaler Sprachen hatten wie Marcel-Paul Schützenbergers Charakterisierung der sternfreien Sprachen .

In diesem Gebiet tragen heute mindestens vier Konzepte Brzozowskis Namen zu Ehren seiner Beiträge: Erstens die Brzozowski-Vermutung [ 5 ] über die Regularität nichtzählender Klassen. Zweitens der Brzozowski-Algorithmus [ 6 ] , ein konzeptionell einfacher Algorithmus zur Minimierung von DFAs . Drittens die Brzozowski-Ableitung einer formalen Sprache oder eines verallgemeinerten regulären Ausdrucks . Viertens widmet Eilenbergs Standardwerk zur Automatentheorie ein Kapitel der sogenannten Brzozowski-Hierarchie [ 7 ] innerhalb sternfreier Sprachen , auch bekannt als Punkttiefenhierarchie . Brzozowski war nicht nur Mitautor der Arbeit, die die Punkttiefenhierarchie definierte und die Frage nach ihrer Strenge aufwarf [ 8 ] , sondern auch Mitautor der Arbeit, die dieses Problem etwa zehn Jahre später löste. [ 9 ] Die Brzozowski-Hierarchie gewann weiter an Bedeutung, nachdem Wolfgang Thomas über Ehrenfeucht-Fraïssé-Spiele eine Beziehung zwischen dem algebraischen Konzept der Punkttiefe und der Alternationstiefe von Quantoren in der Prädikatenlogik erster Stufe entdeckt hatte . [ 10 ]

Er erhielt folgende akademische Auszeichnungen und Ehrungen:

  • NSERC-Wissenschaftsaustauschstipendium für Frankreich (1974–1975)
  • Forschungsstipendium der Japanischen Gesellschaft zur Förderung der Wissenschaft (1984)
  • Anerkennungsurkunde der Computing Research Association für herausragende Beiträge und Verdienste als Mitglied des CRA-Vorstands (1992)
  • Ausgezeichneter Professor Emeritus, Universität Waterloo , Kanada (1996) [ 11 ]
  • Verdienstmedaille der Katholischen Universität Lublin, Polen (2001)
  • IBM Kanada Kanadischer Pionier im Bereich Computing (2005) [ 12 ]
  • Die Rolle der Theorie in der Informatik, eine eintägige Konferenz zu Ehren des 80. Geburtstags von John Brzozowski (2015) [ 13 ]
  • Die Rolle der Theorie in der Informatik: Essays zu Ehren von Janusz Brzozowski, World Scientific (2017) [ 14 ]
  • Lifetime Achievement Award, Computer Science Canada/Informatique Canada (CS-CAN/INFO-CAN) (2016) [ 15 ]
  • CIAA 2017 Sheng Yu Award für die beste Arbeit zur Komplexität von eigentlichen präfixkonvexen regulären Sprachen von J. Brzozowski und C. Sinnamon [ 16 ]
  • CIAA 2018 Sheng Yu Award für die beste Arbeit zum Thema Zustandskomplexität der Überlappungsassemblierung von J. Brzozowski, L. Kar i, B. Li, M. Szykula [ 17 ]

Forschungsarbeiten

  • JA Brzozowski: Ableitungen regulärer Ausdrücke, Journal of the ACM 11(4): 481–494 (1964)
  • J. A. Brzozowski, I. Simon: Charakterisierungen lokal testbarer Ereignisse, FOCS 1971, S. 166–176
  • RS Cohen, JA Brzozowski: Punkttiefe sternfreier Ereignisse. Journal of Computer and System Sciences 5(1): 1–16 (1971)
  • J. A. Brzozowski, R. Knast: Die Punkt-Tiefen-Hierarchie sternfreier Sprachen ist unendlich. Journal of Computer and System Sciences 16(1): 37–55 (1978)

Bücher

  • JA Brzozowski, M. Yoeli: Digitale Netzwerke. Prentice-Hall, 1976
  • JA Brzozowski, C.-JH Seger: Asynchrone Schaltungen. Springer-Verlag, 1995

Anmerkungen

  1. ^ „John Brzozowski“ . David R. Cheriton School of Computer Science . Archiviert vom Original am 22. Dezember 2018. Abgerufen am 21. Dezember 2018 .
  2. ^ „Nachruf auf Janusz BRZOZOWSKI (1935–2019) – Waterloo, ON – the Globe and Mail“ . Legacy.com .
  3. ^ Pin (1997)
  4. ^ Diekert et al. (2008)
  5. ^ de Luca und Varicchio (1997)
  6. ^ Shallit (2009), Kap. 3.10
  7. ^ Eilenberg (1974)
  8. ^ Cohen und Brzozowski (1971)
  9. ^ Brzozowski und Knast (1979)
  10. ^ Thomas (1982)
  11. ^ „Profil von John Brzozowski“ . Archiviert vom Original am 24.11.2012 . Abgerufen am 14.07.2009 .
  12. ^ Pioniere des Computing in Kanada, 2005, http://individual.utoronto.ca/klyons/files/pioneers.pdf Abgerufen am 2. Januar 2019.
  13. ^ „Brzozowski 80: Die Rolle der Theorie in der Informatik“ . David R. Cheriton School of Computer Science . 24. Juni 2015. Abgerufen am 21. Dezember 2018 .
  14. ^ Konstantinidis, Stavros; Moreira, Nelma; Reis, Rogerio; Shallit, Jeffrey (2017). „Die Rolle der Theorie in der Informatik: Essays über Janusz Brzozowski“ . Weltwissenschaftlich . doi : 10.1142/10239 . ISBN 978-981-314-819-2Abgerufen am 29. November 2021 .
  15. ^ „Lifetime Achievement Awards | 2016“ . Computer Science Canada/Information Canada (CS-CAN/INFO-CAN) . 2016. Abgerufen am 21. Dezember 2018 .
  16. ^ „22. Internationale Konferenz zur Implementierung und Anwendung von Automaten | Sheng-Yu-Preis 2017“ . Konferenz zur Implementierung und Anwendung von Automaten (CIAA 2017) . 2017. Abgerufen am 21. Dezember 2018 .
  17. ^ „23. Internationale Konferenz über Implementierung und Anwendungen von Automaten | Sheng-Yu-Preis 2018“ . 23. Internationale Konferenz über Implementierung und Anwendungen von Automaten (CIAA 2018) . 23. August 2018. Abgerufen am 21. Dezember 2018 .

Referenzen

  • S. Eilenberg, Automaten, Sprachen und Maschinen , Band B. ISBN 0-12-234001-9
  • W. Thomas, Klassifizierung regulärer Ereignisse in der symbolischen Logik. J. Comput. Syst. Sci. 25(3): 360–376 (1982)
  • J.-É. Pin , Syntaktische Halbgruppen , Kapitel 10 in „Handbook of Formal Language Theory“, Band 1, G. Rozenberg und A. Salomaa (Hrsg.), Springer Verlag, (1997) Band 1, S. 679–746
  • A. de Luca und S. Varicchio, Regularitäts- und Endlichkeitsbedingungen , Kapitel 11 in „Handbook of Formal Language Theory“, Band 1, G. Rozenberg und A. Salomaa (Hrsg.), Springer Verlag, (1997) Band 1, S. 747–810
  • V. Diekert, P. Gastin, M. Kufleitner, Eine Übersicht über kleine Fragmente der Prädikatenlogik erster Stufe über endlichen Wörtern. Int. J. Found. Comput. Sci. 19(3): 513–548 (2008)
  • J. Shallit, A Second Course in Formal Languages ​​and Automata Theory , Cambridge University Press (2009)