Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Janusz Brzozowski (computer scientist)
open-in-new
<h2 id="achievements-in-research">Achievements in research</h2> <p>Brzozowski worked on <a href="/facts/Regular_expressions/KFL3veHX">regular expressions</a> and on <a href="/facts/Syntactic_semigroup/7khpKalF">syntactic semigroups</a> of <a href="/facts/Formal_languages/crDTyP8q">formal languages</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> The result was <i>Characterizations of locally testable events</i> written together with <a href="/facts/Imre_Simon/YuekHvJf">Imre Simon</a>, which had a similar impact<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> on the development of the algebraic theory of formal languages as <a href="/facts/Marcel-Paul_Sch%C3%BCtzenberger/aF62Lo9H">Marcel-Paul Schützenberger</a>'s characterization of the <a href="/facts/Star-free_language/GJyaevnF">star-free languages</a>. </p><p>In the area, today at least four concepts bear Brzozowski's name in honour of his contributions: The first is the <i>Brzozowski's conjecture</i><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> about the regularity of noncounting classes. Second, <i><a href="/facts/DFA_minimization/qASLWje9">Brzozowski's algorithm</a></i>,<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> a conceptually simple algorithm for performing <a href="/facts/DFA_minimization/qASLWje9">DFA minimization</a>. Third, the <i><a href="/facts/Brzozowski_derivative/ceustUPV">Brzozowski derivative</a></i> of a formal language or of a generalised <a href="/facts/Regular_expression/KFL3veHX">regular expression</a>. Fourth, <a href="/facts/Samuel_Eilenberg/vs6aksKX">Eilenberg</a>'s reference work on automata theory has a chapter devoted to the so-called <i>Brzozowski hierarchy</i><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> inside the <a href="/facts/Star-free_language/GJyaevnF">star-free languages</a>, also known as <i>dot-depth hierarchy</i>. 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,<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> he later also was co-author of the paper resolving that problem after roughly ten years.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> 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 <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a> via <a href="/facts/Ehrenfeucht%E2%80%93Fra%C3%AFss%C3%A9_game/MJonU8Cb">Ehrenfeucht–Fraïssé games</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p><p>He received the following academic awards and honours: </p> <ul><li>NSERC Scientific Exchange Award to France (1974–1975)</li> <li>Japan Society for the Promotion of Science Research Fellowship (1984)</li> <li><a href="/facts/Computing_Research_Association/Bqn7Sj3v">Computing Research Association</a> Certificate of Appreciation for outstanding contributions and service as a member of the CRA Board of Directors (1992)</li> <li>Distinguished Professor Emeritus, <a href="/facts/University_of_Waterloo/NANSHN5Y">University of Waterloo</a>, Canada (1996)<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li>Medal of Merit, Catholic University of Lublin, Poland (2001)</li> <li>IBM Canada Canadian Pioneer in Computing (2005)<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li> <li>The Role of Theory in Computer Science, a one-day conference in honour of John Brzozowski's 80th birthday (2015)<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li> <li>The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski, World Scientific (2017)<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li> <li>Lifetime Achievement Award, Computer Science Canada/Informatique Canada (CS-CAN/INFO-CAN) (2016)<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a></li> <li>CIAA 2017 Sheng Yu Award for Best Paper for <i>Complexity of Proper Prefix-Convex Regular Languages</i> by J. Brzozowski and C. Sinnamon<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a></li> <li>CIAA 2018 Sheng Yu Award for Best Paper for <i>State Complexity of Overlap Assembly</i> by J. Brzozowski, <a href="/facts/Lila_Kari/5DGFt0Rk">L. Kar</a>i, B. Li, M. Szykula<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a></li></ul> <h2 id="research-papers">Research papers</h2> <ul><li>J. A. Brzozowski: <a href="/facts/Brzozowski_derivative/ceustUPV">Derivatives</a> of regular expressions, <i><a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a></i> 11(4): 481–494 (1964)</li> <li>J. A. Brzozowski, I. Simon: Characterizations of Locally Testable Events, <a href="/facts/FOCS/t0BvR59t">FOCS</a> 1971, pp. 166–176</li> <li>R. S. Cohen, J. A. Brzozowski: Dot-Depth of Star-Free Events. <i><a href="/facts/Journal_of_Computer_and_System_Sciences/cNek9ego">Journal of Computer and System Sciences</a></i> 5(1): 1–16 (1971)</li> <li>J. A. Brzozowski, R. Knast: The Dot-Depth Hierarchy of Star-Free Languages is Infinite. <i>Journal of Computer and System Sciences</i> 16(1): 37–55 (1978)</li></ul> <h2 id="books">Books</h2> <ul><li>J. A. Brzozowski, M. Yoeli: Digital Networks. Prentice–Hall, 1976</li> <li>J. A. Brzozowski, C.-J. H. Seger: Asynchronous Circuits. Springer-Verlag, 1995</li></ul> <h2 id="notes">Notes</h2> <ul><li>S. Eilenberg, <i>Automata, Languages and Machines</i>, Volume B. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-12-234001-9</li> <li>W. Thomas, <i>Classifying Regular Events in Symbolic Logic.</i> J. Comput. Syst. Sci. 25(3): 360–376 (1982)</li> <li><a href="/facts/Jean-%C3%89ric_Pin/hBjkW0FN">J.-É. Pin</a>, <a href="http://www.irif.fr/~jep/PDF/HandBook.pdf"><i>Syntactic semigroups</i></a>, Chapter 10 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 679–746</li> <li>A. de Luca and S. Varicchio, <i>Regularity and Finiteness Conditions</i>, Chapter 11 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 747–810</li> <li>V. Diekert, P. Gastin, M. Kufleitner, <a href="https://web.archive.org/web/20110604113332/http://www.fmi.uni-stuttgart.de/ti/veroeffentlichungen/pdffiles/DiekertGastinKufleitner2008ijfcs.pdf"><i>A Survey on Small Fragments of First-Order Logic over Finite Words.</i></a> Int. J. Found. Comput. Sci. 19(3): 513–548 (2008)</li> <li>J. Shallit, <i>A Second Course in Formal Languages and Automata Theory</i>, Cambridge University Press (2009)</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.cs.uwaterloo.ca/about/profile/brzozo.shtml">Profile of Janusz Brzozowski, University of Waterloo</a> <a href="https://web.archive.org/web/20121124212712/https://cs.uwaterloo.ca/about/profile/brzozo.shtml">Archived</a> 2012-11-24 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li> <li><a href="http://maveric.uwaterloo.ca/~brzozo/">Brzozowski's personal website</a> <a href="https://web.archive.org/web/20191030163904/http://maveric.uwaterloo.ca/~brzozo/">Archived</a> 2019-10-30 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> at the University of Waterloo</li> <li><a href="http://www.student.cs.uwaterloo.ca/~cs462/Hall/hall.html">The Theory of Computing Hall of Fame</a> <a href="https://web.archive.org/web/20191030163914/https://www.student.cs.uwaterloo.ca/~cs462/Hall/hall.html">Archived</a> 2019-10-30 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li> <li><a href="https://dblp.org/pid/b/JABrzozowski">Janusz A. Brzozowski</a> at <a href="/facts/DBLP_(identifier)/JLAIuLQQ">DBLP</a> Bibliography Server </li> <li><a href="http://www.irif.fr/~jep/Problemes/concatenation.html">Concatenation Hierarchies</a> by Jean-Éric Pin</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"John Brzozowski". David R. Cheriton School of Computer Science. Archived from the original on December 22, 2018. Retrieved December 21, 2018. <a href="https://web.archive.org/web/20181222082021/https://cs.uwaterloo.ca/people-profiles/john-brzozowsk" target="_blank">https://web.archive.org/web/20181222082021/https://cs.uwaterloo.ca/people-profiles/john-brzozowsk</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"Janusz BRZOZOWSKI Obituary (1935–2019) – Waterloo, ON – the Globe and Mail". Legacy.com. <a href="https://www.legacy.com/obituaries/theglobeandmail/obituary.aspx?n=janusz-a-brzozowski&pid=194286993&fhid=30885" target="_blank">https://www.legacy.com/obituaries/theglobeandmail/obituary.aspx?n=janusz-a-brzozowski&pid=194286993&fhid=30885</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Pin (1997) <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Diekert et al. (2008) <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>de Luca and Varicchio (1997) <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Shallit (2009), ch. 3.10 <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Eilenberg (1974) <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Cohen and Brzozowski (1971) <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Brzozowski and Knast (1979) <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Thomas (1982) <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>"Profile of John Brzozowski". Archived from the original on 2012-11-24. Retrieved 2009-07-14. <a href="https://web.archive.org/web/20121124212712/https://cs.uwaterloo.ca/about/profile/brzozo.shtml" target="_blank">https://web.archive.org/web/20121124212712/https://cs.uwaterloo.ca/about/profile/brzozo.shtml</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Pioneers of Computing in Canada, 2005, http://individual.utoronto.ca/klyons/files/pioneers.pdf Retrieved January 2, 2019. <a href="http://individual.utoronto.ca/klyons/files/pioneers.pdf" target="_blank">http://individual.utoronto.ca/klyons/files/pioneers.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>"Brzozowski 80: The Role of Theory in Computer Science". David R. Cheriton School of Computer Science. June 24, 2015. Retrieved December 21, 2018. <a href="https://cs.uwaterloo.ca/~shallit/DC2015/brz.html" target="_blank">https://cs.uwaterloo.ca/~shallit/DC2015/brz.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Konstantinidis, Stavros; Moreira, Nelma; Reis, Rogério; Shallit, Jeffrey (2017). "The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski". World Scientific. doi:10.1142/10239. ISBN 978-981-314-819-2. Retrieved November 29, 2021. <a href="978-981-314-819-2" target="_blank">978-981-314-819-2</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>"Lifetime Achievement Awards | 2016". Computer Science Canada/Information Canada (CS-CAN/ INFO-CAN). 2016. Retrieved December 21, 2018. <a href="https://cscan-infocan.ca/awards/john-brzozowski-2/" target="_blank">https://cscan-infocan.ca/awards/john-brzozowski-2/</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>"22nd International Conference Implementation and Application of Automata | 2017 Sheng Yu Award". Conference on Implementation and Application of Automata (CIAA 2017). 2017. Retrieved December 21, 2018. <a href="http://ciaa17.univ-mlv.fr" target="_blank">http://ciaa17.univ-mlv.fr</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>"23rd International Conference on Implementation and Applications of Automata | 2018 Sheng Yu Award". 23rd International Conference on Implementation and Applications of Automata (CIAA 2018). August 23, 2018. Retrieved December 21, 2018. <a href="http://www.smcs.upei.ca/ciaa2018/index.php?page=23" target="_blank">http://www.smcs.upei.ca/ciaa2018/index.php?page=23</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> </ol>