Janusz Brzozowski (počítačový vědec) - Janusz Brzozowski (computer scientist)

Janusz Brzozowski
Portrét profesora Janusze Brzozowského pořízený v Davisově centru na univerzitě ve Waterloo
Brzozowski v roce 2018
narozený(1935-05-10)10. května 1935
Varšava, Polsko
Zemřel24. října 2019(2019-10-24) (ve věku 84)
Lisaard House, Cambridge, Ontario, Kanada
Alma materUniverzita Princeton
Známý jakoBrzozowského derivát
Vědecká kariéra
PolePočítačová věda
TezeTechniky regulárního výrazu pro sekvenční obvody (1962)
Doktorský poradceEdward J. McCluskey

Janusz (John) Antoni Brzozowski (10. května 1935 - 24. října 2019) byl polsko-kanadský počítačový vědec a význačný emeritní profesor[1] na University of Waterloo je David R. Cheriton School of Computer Science.[2]

V roce 1962 získal Brzozowski titul PhD v oboru elektrotechnika na Univerzita Princeton pod Edward J. McCluskey. Tématem diplomové práce bylo Techniky regulárního výrazu pro sekvenční obvody. V letech 1967 až 1996 působil jako profesor na University of Waterloo. On je známý pro jeho příspěvky k matematická logika, teorie obvodů, a teorie automatů.

Úspěchy ve výzkumu

Brzozowski pracoval regulární výrazy a dál syntaktické poloskupiny z formální jazyky.[3] Výsledek byl Charakterizace místně testovatelných událostí napsáno společně s Imre Simon, který měl podobný dopad[4] o rozvoji algebraické teorie formálních jazyků jako Marcel-Paul Schützenberger charakterizace jazyky bez hvězd.

V této oblasti dnes na počest jeho příspěvků nesou Brzozowského jméno nejméně tři koncepty: První je Brzozowského domněnka[5] o pravidelnosti neúčtovacích tříd. Druhý, Brzozowského algoritmus[6] koncepčně jednoduchý algoritmus pro provedení Minimalizace DFA. Třetí, Eilenberg Referenční práce na teorii automatů má kapitolu věnovanou tzv Brzozowského hierarchie[7] uvnitř jazyky bez hvězd, také známý jako hierarchie hloubky teček. Je zajímavé, že Brzozowski nebyl jen spoluautorem příspěvku, který definoval hierarchie hloubky teček a nastolila otázku, zda je tato hierarchie přísná,[8] později byl také spoluautorem článku, který tento problém vyřešil zhruba po deseti letech.[9] Brzozowského hierarchie získala další význam poté, co Thomas objevil vztah mezi algebraickým konceptem hloubky teček a hloubkou střídání kvantifikátorů v logika prvního řádu přes Hry Ehrenfeucht – Fraïssé.[10]

Získal následující akademická ocenění a vyznamenání:

  • Cena NSERC za vědeckou výměnu do Francie (1974–1975)
  • Japonská společnost pro podporu vědeckého stipendia (1984)
  • Asociace pro výzkum v oblasti výpočetní techniky Osvědčení o uznání za vynikající příspěvky a služby člena představenstva CRA (1992)
  • Emeritní profesor, University of Waterloo, Kanada (1996)[11]
  • Medaile za zásluhy, Katolická univerzita v Lublinu, Polsko (2001)
  • IBM Canada Canadian Pioneer in Computing (2005)[12]
  • Role teorie v informatice, jednodenní konference na počest 80. narozenin Johna Brzozowského (2015)[13]
  • Cena za celoživotní přínos, Computer Science Canada / Informatique Canada (CS-CAN / INFO-CAN) (2016)[14]
  • Cena CIAA 2017 Sheng Yu za nejlepší papír pro Složitost správných předpony-konvexních regulárních jazyků J. Brzozowski a C. Sinnamon[15]
  • Cena CIAA 2018 Sheng Yu za nejlepší papír pro Stavová složitost překrývající se sestavy J. Brzozowski, L. Kar i, B. Li, M. Szykula[16]

Výzkumné práce

  • J. A. Brzozowski: Deriváty of regular expressions, Journal of the ACM 11 (4): 481–494 (1964)
  • J. A. Brzozowski, I. Simon: Charakterizace místně testovatelných událostí, FOCS 1971, s. 166–176
  • R. S. Cohen, J. A. Brzozowski: Dot-Depth of Star-Free Events. Journal of Computer and System Sciences 5 (1): 1-16 (1971)
  • J. A. Brzozowski, R. Knast: Hierarchie jazyků bez hvězd je Dot-Depth Hierarchie je nekonečná. Journal of Computer and System Sciences 16 (1): 37–55 (1978)

Knihy

  • J. A. Brzozowski, M. Yoeli: Digitální sítě. Prentice – Hall, 1976
  • J.A. Brzozowski, C.-J. H. Seger: Asynchronní obvody. Springer-Verlag, 1995

Poznámky

  1. ^ „John Brzozowski“. David R. Cheriton School of Computer Science. Citováno 21. prosince 2018.
  2. ^ https://www.legacy.com/obituaries/theglobeandmail/obituary.aspx?n=janusz-a-brzozowski&pid=194286993&fhid=30885
  3. ^ Pin (1997)
  4. ^ Diekert a kol. (2008)
  5. ^ de Luca a Varicchio (1997)
  6. ^ Shallit (2009), kap. 3.10
  7. ^ Eilenberg (1974)
  8. ^ Cohen a Brzozowski (1971)
  9. ^ Brzozowski a Knast (1979)
  10. ^ Thomas (1982)
  11. ^ Profil Johna Brzozowského
  12. ^ Pioneers of Computing in Canada, 2005, http://individual.utoronto.ca/klyons/files/pioneers.pdf Citováno 2. ledna 2019.
  13. ^ „Brzozowski 80: The Role of Theory in Computer Science“. David R. Cheriton School of Computer Science. 24. června 2015. Citováno 21. prosince 2018.
  14. ^ „Ocenění za celoživotní přínos | 2016“. Computer Science Canada / Information Canada (CS-CAN / INFO-CAN). 2016. Citováno 21. prosince 2018.
  15. ^ „22. mezinárodní konference Implementace a aplikace automatů | Cena Sheng Yu za rok 2017“. Konference o implementaci a aplikaci automatů (CIAA 2017). 2017. Citováno 21. prosince 2018.
  16. ^ „23. mezinárodní konference o implementaci a aplikacích automatů | Cena Sheng Yu za rok 2018“. 23. mezinárodní konference o implementaci a aplikacích automatů (CIAA 2018). 23. srpna 2018. Citováno 21. prosince 2018.

Reference

  • S. Eilenberg, Automaty, jazyky a stroje, Svazek B. ISBN  0-12-234001-9
  • W. Thomas, Klasifikace pravidelných událostí v symbolické logice. J. Comput. Syst. Sci. 25 (3): 360-376 (1982)
  • J.-E. Kolík, Syntaktické poloskupiny, Kapitola 10 v „Příručce teorie formálního jazyka“, sv. 1, G. Rozenberg a A. Salomaa (eds.), Springer Verlag, (1997) sv. 1, s. 679–746
  • A. de Luca a S. Varicchio, Podmínky pravidelnosti a konečnosti, Kapitola 11 v „Příručce teorie formálního jazyka“, sv. 1, G. Rozenberg a A. Salomaa (eds.), Springer Verlag, (1997) sv. 1, s. 747–810
  • V. Diekert, P. Gastin, M. Kufleitner, Průzkum malých fragmentů logiky prvního řádu nad konečnými slovy. Int. J. Nalezeno. Comput. Sci. 19 (3): 513-548 (2008)
  • J. Shallit, Druhý kurz formálních jazyků a teorie automatů, Cambridge University Press (2009)

externí odkazy