Alma mater Princeton University Education Princeton University Known for Brzozowski derivative Fields Computer Science | Name Janusz Brzozowski Role Computer scientist Notable students Imre Simon | |

Born May 10, 1935Warsaw, Poland (1935-05-10) Thesis Regular Expression Techniques for Sequential Circuits (1962) Books Asynchronous circuits | ||

Doctoral advisor Edward J. McCluskey |

**Janusz (John) Antoni Brzozowski** (born on May 10, 1935 in Warsaw, Poland) is a Polish-Canadian computer scientist.

## Contents

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. The result was *Characterizations of locally testable events* written together with Imre Simon, which had a similar impact 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, there are today at least three concepts bearing Brzozowski's name in honour of his contributions: The first is the *Brzozowski conjecture* about the regularity of noncounting classes. Second, *Brzozowski's algorithm* is a conceptually simple algorithm for performing DFA minimization. Third, Eilenberg's reference work on automata theory has a chapter devoted to the so-called *Brzozowski hierarchy* inside the star-free languages, also known as *dot-depth hierarchy*. Curiously, Brzozowski was not only co-author of the paper that defined the dot-depth hierarchy and raised the question whether this hierarchy is strict, he later also was co-author of the paper resolving that problem after roughly ten years. The Brzozowski hierarchy gained further importance after 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.

He received the following academic awards: