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:
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)
S. Eilenberg, Automata, Languages and Machines, Volume B. ISBN0-12-234001-9
W. Thomas, Classifying Regular Events in Symbolic Logic. J. Comput. Syst. Sci. 25(3): 360–376 (1982)
J.-É. Pin, 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