Janusz Brzozowski (computer scientist) explained

Janusz Brzozowski
Birth Date:10 May 1935
Birth Place:Warsaw, Poland
Death Place:Lisaard House, Cambridge, Ontario, Canada
Fields:Computer science
Alma Mater:Princeton University
Thesis Title:Regular Expression Techniques for Sequential Circuits
Thesis Year:1962
Doctoral Advisor:Edward J. McCluskey
Known For:Brzozowski derivative Brzozowski's algorithm

Janusz (John) Antoni Brzozowski (May 10, 1935  - October 24, 2019) was a Polish-Canadian computer scientist and Distinguished Professor Emeritus[1] at the University of Waterloo's David R. Cheriton School of Computer Science.[2]

In 1962, Brzozowski earned his PhD in the field of electrical engineering at Princeton University under Edward J. McCluskey. The topic of the thesis was Regular Expression Techniques for Sequential Circuits. From 1967 to 1996 he was Professor at the University of Waterloo. He is known for his contributions to mathematical logic, circuit theory, and automata theory.

Achievements in research

Brzozowski worked on regular expressions and on syntactic semigroups of formal languages.[3] The result was Characterizations of locally testable events written together with Imre Simon, which had a similar impact[4] on the development of the algebraic theory of formal languages as Marcel-Paul Schützenberger's characterization of the star-free languages.

In the area, today at least four concepts bear Brzozowski's name in honour of his contributions: The first is the Brzozowski's conjecture[5] about the regularity of noncounting classes. Second, Brzozowski's algorithm,[6] a conceptually simple algorithm for performing DFA minimization. Third, the Brzozowski derivative of a formal language or of a generalised regular expression. Fourth, Eilenberg's reference work on automata theory has a chapter devoted to the so-called Brzozowski hierarchy[7] inside the star-free languages, also known as dot-depth hierarchy. Notably, Brzozowski was not only co-author of the paper that defined the dot-depth hierarchy and raised the question whether this hierarchy is strict,[8] he later also was co-author of the paper resolving that problem after roughly ten years.[9] The Brzozowski hierarchy gained further importance after Wolfgang Thomas discovered a relation between the algebraic concept of dot-depth and the alternation depth of quantifiers in first-order logic via Ehrenfeucht–Fraïssé games.[10]

He received the following academic awards and honours:

Research papers

Books

Notes

  1. Web site: John Brzozowski. David R. Cheriton School of Computer Science. December 21, 2018. December 22, 2018. https://web.archive.org/web/20181222082021/https://cs.uwaterloo.ca/people-profiles/john-brzozowsk. dead.
  2. Web site: Janusz BRZOZOWSKI Obituary (1935–2019) – Waterloo, ON – the Globe and Mail. .
  3. Pin (1997)
  4. Diekert et al. (2008)
  5. de Luca and Varicchio (1997)
  6. Shallit (2009), ch. 3.10
  7. Eilenberg (1974)
  8. Cohen and Brzozowski (1971)
  9. Brzozowski and Knast (1979)
  10. Thomas (1982)
  11. Web site: Profile of John Brzozowski . 2009-07-14 . 2012-11-24 . https://web.archive.org/web/20121124212712/https://cs.uwaterloo.ca/about/profile/brzozo.shtml . dead .
  12. Pioneers of Computing in Canada, 2005, http://individual.utoronto.ca/klyons/files/pioneers.pdf Retrieved January 2, 2019.
  13. News: Brzozowski 80: The Role of Theory in Computer Science. June 24, 2015. David R. Cheriton School of Computer Science. December 21, 2018.
  14. News: The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski. 2017. World Scientific. 10.1142/10239 . November 29, 2021. Konstantinidis . Stavros . Moreira . Nelma . Reis . Rogério . Shallit . Jeffrey . Jeffrey Shallit. 978-981-314-819-2 .
  15. Web site: Lifetime Achievement Awards 2016. 2016. Computer Science Canada/Information Canada (CS-CAN/ INFO-CAN). December 21, 2018.
  16. Web site: 22nd International Conference Implementation and Application of Automata 2017 Sheng Yu Award. 2017. Conference on Implementation and Application of Automata (CIAA 2017). December 21, 2018.
  17. Web site: 23rd International Conference on Implementation and Applications of Automata 2018 Sheng Yu Award. August 23, 2018. 23rd International Conference on Implementation and Applications of Automata (CIAA 2018). December 21, 2018.

References

External links

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Janusz Brzozowski (computer scientist)".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.