Distinguished Professor Emeritus Janusz (John) A. Brzozowski passed away on Thursday, October 24, 2019 at age 84. Please see the in memoriam for our tribute to him and details about his personal and academic life.
His research profile has been preserved for historical interest.
Research interests
Professor Brzozowski’s research interests were in the theory of automata and formal languages, particularly in complexity of regular languages and finite automata.
Finite automata and regular languages are the simplest models of computation, and appear in many applications. State complexity is a frequently used measure of complexity of regular language operations. It is the maximal number of states in a minimal deterministic finite automaton (DFA) of the language resulting from the operation as a function of the state complexities of minimal DFAs of the operands.
Professor Brzozowski generalized the concept of convex languages and unified many diverse regular language classes under the same convex umbrella. He proved that star-free languages, a proper subclass of regular languages, meet all the complexity bounds of regular languages with one very small exception. He proposed syntactic complexity of a regular language as another complexity measure; this is the size of the syntactic semigroup of the language, and is the same as the size of the transition semigroup of a minimal DFA of that language. (The transition semigroup of a DFA is the set of transformations of the states of the DFA induced by its inputs.) He studied the state and syntactic complexities in many subclasses of convex and star-free languages.
He introduced and studied a nondeterministic finite automaton (NFA), called a'tomaton, uniquely defined by every regular language, and studied complexity issues associated with that NFA. He developed methods of reducing non-determinism in NFAs by using look-ahead information.
Previously, he applied ideas from the theory of automata to the “trace-assertion” specification method of software modules. Professor Brzozowski worked for many years in the area of asynchronous circuit theory. He wrote the monograph “Asynchronous Circuits”, Springer, 1995 (with C.-J. Seger), and many papers on this topic. He developed efficient methods for detecting hazards (erroneous signals) in VLSI circuits using multi-valued algebras.
In the past, he also worked on circuit testing for a number of years. This work involved finding formal models for circuit faults, and the derivation of short test sequences. Most of this work was oriented towards faults in random-access memories.
Degrees and awards
- Canadian Pioneer in Computing, IBM, 2005
- Medal of Merit, Catholic University of Lublin, Poland, 2001
- Distinguished Professor Emeritus, University of Waterloo, 1996
- Japan Society for the Promotion of Science Research Fellowship, 1984
- NSERC Scientific Exchange Award to France, 1974-1975
Industrial and sabbatical experience
Professor Brzozowski held visiting appointments at University of California, Berkeley, CA (1965-66); Istituto Nazionale di Alta Matematica, Rome, Italy (1972); Institut de Programmation, Universite' Paris VI and VII, Paris, France (1974-75); Gesellschaft für Mathematik und Datenverarbeitung Bonn, Germany (1975); Instituto de Matemática e Estatística da Universidade de São Paulo, São Paulo, Brazil (1983); Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan (1984); Department of Mathematics and Computing Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands (1989-90).
Representative publications
J. Brzozowski, H. Tamm. Theory of A'tomata. Theoret. Comput. Sc. 539: 13-27, 2014.
J. Brzozowski. In Search of Most Complex Regular Languages. Internat. J. Found. Comput. Sc. 24(6): 691-708, 2013.
J. Brzozowski, B. Liu. Quotient Complexity of Star-Free Languages. Internat. J. Found. Comput. Sc. 23(6): 1261-1276, 2012.
J. Brzozowski, B. Li, Y. Ye. Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages. Theoret. Comput. Sc. 449: 37-53, 2012.
J. Brzozowski, E. Grant, J. Shallit. Closures in Formal Languages and Kuratowski's Theorem. Internat. J. Found. Comput. Sc. 22(2): 310-321, 2011.
