Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Janusz Brzozowski (computer scientist)
Summary
Janusz (John) Antoni Brzozowski (May 10, 1935 – October 24, 2019) was a Polish-Canadian computer scientist and Distinguished Professor Emeritus at the University of Waterloo's David R. Cheriton School of Computer Science.
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.
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, today at least four concepts bear Brzozowski's name in honour of his contributions: The first is the Brzozowski's conjecture about the regularity of noncounting classes. Second, Brzozowski's algorithm, 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 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, he later also was co-author of the paper resolving that problem after roughly ten years. 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.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.