Janusz Brzozowski (computer scientist)
{{Short description|Polish-Canadian computer scientist (1935–2019)}}
{{Infobox scientist
| name = Janusz Brzozowski
| image = Portrait of Professor Janusz Brzozowski.jpg
| image_size =
| alt = Portrait of Professor Janusz Brzozowski taken in the Davis Centre at the University of Waterloo
| caption = Brzozowski in 2018
| birth_date = {{Birth date|1935|05|10}}
| birth_place = Warsaw, Poland
| death_date = {{Death date and age|2019|10|24|1935|05|10}}
| death_place = Lisaard House, Cambridge, Ontario, Canada
| residence =
| citizenship =
| nationality =
| fields = Computer science
| workplaces =
| alma_mater = Princeton University
| thesis_title = Regular Expression Techniques for Sequential Circuits
| thesis_year = 1962
| doctoral_advisor = Edward J. McCluskey
| academic_advisors =
| doctoral_students =
| notable_students =
| known_for = Brzozowski derivative Brzozowski's algorithm
| author_abbrev_bot =
| author_abbrev_zoo =
| influences =
| influenced =
| awards =
| signature =
| signature_alt =
| footnotes =
| spouse =
}}
Janusz (John) Antoni Brzozowski (May 10, 1935 – October 24, 2019) was a Polish-Canadian computer scientist and Distinguished Professor Emeritus{{Cite web|url=https://cs.uwaterloo.ca/people-profiles/john-brzozowsk|title=John Brzozowski|website=David R. Cheriton School of Computer Science|access-date=December 21, 2018|archive-date=December 22, 2018|archive-url=https://web.archive.org/web/20181222082021/https://cs.uwaterloo.ca/people-profiles/john-brzozowsk|url-status=dead}} at the University of Waterloo's David R. Cheriton School of Computer Science.{{Cite web|url=https://www.legacy.com/obituaries/theglobeandmail/obituary.aspx?n=janusz-a-brzozowski&pid=194286993&fhid=30885|title = Janusz BRZOZOWSKI Obituary (1935–2019) – Waterloo, ON – the Globe and Mail| website=Legacy.com }}
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.Pin (1997) The result was Characterizations of locally testable events written together with Imre Simon, which had a similar impactDiekert et al. (2008) 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 conjecturede Luca and Varicchio (1997) about the regularity of noncounting classes. Second, Brzozowski's algorithm,Shallit (2009), ch. 3.10 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 hierarchyEilenberg (1974) 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,Cohen and Brzozowski (1971) he later also was co-author of the paper resolving that problem after roughly ten years.Brzozowski and Knast (1979) 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.Thomas (1982)
He received the following academic awards and honours:
- NSERC Scientific Exchange Award to France (1974–1975)
- Japan Society for the Promotion of Science Research Fellowship (1984)
- Computing Research Association Certificate of Appreciation for outstanding contributions and service as a member of the CRA Board of Directors (1992)
- Distinguished Professor Emeritus, University of Waterloo, Canada (1996){{Cite web |url=http://www.cs.uwaterloo.ca/about/profile/brzozo.shtml |title=Profile of John Brzozowski |access-date=2009-07-14 |archive-date=2012-11-24 |archive-url=https://web.archive.org/web/20121124212712/https://cs.uwaterloo.ca/about/profile/brzozo.shtml |url-status=dead }}
- Medal of Merit, Catholic University of Lublin, Poland (2001)
- IBM Canada Canadian Pioneer in Computing (2005)Pioneers of Computing in Canada, 2005, http://individual.utoronto.ca/klyons/files/pioneers.pdf Retrieved January 2, 2019.
- The Role of Theory in Computer Science, a one-day conference in honour of John Brzozowski's 80th birthday (2015){{Cite news|url=https://cs.uwaterloo.ca/~shallit/DC2015/brz.html|title=Brzozowski 80: The Role of Theory in Computer Science|date=June 24, 2015|work=David R. Cheriton School of Computer Science|access-date=December 21, 2018}}
- The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski, World Scientific (2017){{Cite news|url=https://doi.org/10.1142/10239|title=The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski|date=2017|work=World Scientific|doi=10.1142/10239 |access-date=November 29, 2021|last1=Konstantinidis |first1=Stavros |last2=Moreira |first2=Nelma |last3=Reis |first3=Rogério |last4=Shallit |first4=Jeffrey |author4link = Jeffrey Shallit|isbn=978-981-314-819-2 }}
- Lifetime Achievement Award, Computer Science Canada/Informatique Canada (CS-CAN/INFO-CAN) (2016){{Cite web|url=https://cscan-infocan.ca/awards/john-brzozowski-2/|title=Lifetime Achievement Awards {{!}} 2016|date=2016|website=Computer Science Canada/Information Canada (CS-CAN/ INFO-CAN)|access-date=December 21, 2018}}
- CIAA 2017 Sheng Yu Award for Best Paper for Complexity of Proper Prefix-Convex Regular Languages by J. Brzozowski and C. Sinnamon{{Cite web|url=http://ciaa17.univ-mlv.fr|title=22nd International Conference Implementation and Application of Automata {{!}} 2017 Sheng Yu Award|date=2017|website=Conference on Implementation and Application of Automata (CIAA 2017)|access-date=December 21, 2018}}
- CIAA 2018 Sheng Yu Award for Best Paper for State Complexity of Overlap Assembly by J. Brzozowski, L. Kar
i, B. Li, M. Szykula{{Cite web|url=http://www.smcs.upei.ca/ciaa2018/index.php?page=23|title=23rd International Conference on Implementation and Applications of Automata {{!}} 2018 Sheng Yu Award|date=August 23, 2018|website=23rd International Conference on Implementation and Applications of Automata (CIAA 2018)|access-date=December 21, 2018}}
Research papers
- J. A. Brzozowski: Derivatives of regular expressions, Journal of the ACM 11(4): 481–494 (1964)
- J. A. Brzozowski, I. Simon: Characterizations of Locally Testable Events, FOCS 1971, pp. 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: The Dot-Depth Hierarchy of Star-Free Languages is Infinite. Journal of Computer and System Sciences 16(1): 37–55 (1978)
Books
- J. A. Brzozowski, M. Yoeli: Digital Networks. Prentice–Hall, 1976
- J. A. Brzozowski, C.-J. H. Seger: Asynchronous Circuits. Springer-Verlag, 1995
Notes
References
- S. Eilenberg, Automata, Languages and Machines, Volume B. {{ISBN|0-12-234001-9}}
- W. Thomas, Classifying Regular Events in Symbolic Logic. J. Comput. Syst. Sci. 25(3): 360–376 (1982)
- J.-É. Pin, [http://www.irif.fr/~jep/PDF/HandBook.pdf Syntactic semigroups], Chapter 10 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 679–746
- A. de Luca and S. Varicchio, Regularity and Finiteness Conditions, Chapter 11 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 747–810
- V. Diekert, P. Gastin, M. Kufleitner, [https://web.archive.org/web/20110604113332/http://www.fmi.uni-stuttgart.de/ti/veroeffentlichungen/pdffiles/DiekertGastinKufleitner2008ijfcs.pdf A Survey on Small Fragments of First-Order Logic over Finite Words.] 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)
External links
- [http://www.cs.uwaterloo.ca/about/profile/brzozo.shtml Profile of Janusz Brzozowski, University of Waterloo] {{Webarchive|url=https://web.archive.org/web/20121124212712/https://cs.uwaterloo.ca/about/profile/brzozo.shtml |date=2012-11-24 }}
- [http://maveric.uwaterloo.ca/~brzozo/ Brzozowski's personal website] {{Webarchive|url=https://web.archive.org/web/20191030163904/http://maveric.uwaterloo.ca/~brzozo/ |date=2019-10-30 }} at the University of Waterloo
- [http://www.student.cs.uwaterloo.ca/~cs462/Hall/hall.html The Theory of Computing Hall of Fame] {{Webarchive|url=https://web.archive.org/web/20191030163914/https://www.student.cs.uwaterloo.ca/~cs462/Hall/hall.html |date=2019-10-30 }}
- {{DBLP|name=Janusz A. Brzozowski}}
- [http://www.irif.fr/~jep/Problemes/concatenation.html Concatenation Hierarchies] by Jean-Éric Pin
{{Authority control}}
{{DEFAULTSORT:Brzozowski, Janusz}}
Category:Canadian computer scientists
Category:Polish computer scientists
Category:Polish emigrants to Canada
Category:Princeton University alumni