Janusz Brzozowski (computer scientist)
Encyclopedia
Janusz Antoni Brzozowski (born on May 10, 1935 in Warsaw, Poland) is a Polish-Canadian computer scientist.
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 best known for his influential contributions to mathematical logic, circuit theory and automata theory
.
locally testable events together with Imre Simon
, which had a similar impact on the development of the algebraic theory of formal languages as Schützenberger
's famous characterization of the star-free language
s.
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 language
s, 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:
In 1962, Brzozowski earned his PhD in the field of electrical engineering at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
under Edward J. McCluskey
Edward J. McCluskey
Edward J. McCluskey in Orange, New Jersey, is a Professor Emeritus at Stanford University. He is a pioneer in the field of Electrical Engineering.-Biography:...
. 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 best known for his influential contributions to mathematical logic, circuit theory and automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
.
Achievements in research
Brzozowski is renowned in particular for his fundamental work on regular expressions and on syntactic semigroups of formal languages. A notable achievement was the algebraic characterization oflocally testable events together with Imre Simon
Imre Simon
Imre Simon was a Hungarian-born Brazilian mathematician and computer scientist. His research mainly focused on theoretical computer science, Automata theory, and tropical mathematics, a subject he founded, and which was so named because he lived in Brazil. He was a professor of mathematics at the...
, which had a similar impact on the development of the algebraic theory of formal languages as Schützenberger
Schützenberger
Schützenberger may refer to these people:* Anne Ancelin Schützenberger * Paul Schützenberger, French chemist* René Schützenberger, French painter* Marcel-Paul "Marco" Schützenberger, French mathematician and Doctor of Medicine...
's famous characterization of the star-free language
Star-free language
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star...
s.
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
Dfa minimization
In computer science, more specifically in the branch of automata theory, DFA minimization is the task of transforming a given deterministic finite automaton into an equivalent DFA that has minimum number of states. Here, two DFAs are called equivalent if they describe the same regular language...
. Third, Eilenberg
Samuel Eilenberg
Samuel Eilenberg was a Polish and American mathematician of Jewish descent. He was born in Warsaw, Russian Empire and died in New York City, USA, where he had spent much of his career as a professor at Columbia University.He earned his Ph.D. from University of Warsaw in 1936. His thesis advisor...
's reference work on automata theory has a chapter devoted to the so-called Brzozowski hierarchy inside the star-free language
Star-free language
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star...
s, 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
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
via Ehrenfeucht-Fraïssé games.
He received the following academic awards:
- NSERC Scientific Exchange Award to France (1974–1975)
- Japan Society for the Promotion of Science Research Fellowship (1984)
- Distinguished Professor Emeritus, University of WaterlooUniversity of WaterlooThe University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
, Canada (1996) - Medal of Merit, Catholic University of Lublin, Poland (2001)
- Canadian Pioneer in Computing (2005)
Influential 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: Asychronous Circuits. Springer-Verlag, 1995
External links
- Profile of John Brzozowski
- Brzozowski's personal website at the University of Waterloo
- The Theory of Computing Hall of Fame
- Publications by Brzozowski which are listed at DBLPDBLPDBLP is a computer science bibliography website hosted at Universität Trier, in Germany. It was originally a database and logic programming bibliography site, and has existed at least since the 1980s. DBLP listed more than 1.3 million articles on computer science in January 2010...
- Concatenation Hierarchies by Jean-Eric Pin