| Janusz A. Brzozowski
Distinguished Professor Emeritus
Joined School 1967
Professor Brzozowski’s current research interests are in the theory of automata and formal languages, particularly in descriptional complexity issues for regular languages.
He has worked on “state complexity” problems in regular languages, where state complexity is the minimal number of states of a ﬁnite automaton accepting a given regular language, and is commonly used as a complexity measure. He generalized the concept of “convex language” that uniﬁes many diverse language classes under the same umbrella. He studied the state complexity of operations in the class of convex regular languages and its subclasses: the closed, free and ideal languages. He developed methods of reducing non-determinism in ﬁnite automata by using look-ahead information. He has applied ideas from the theory of automata to the “trace-assertion” speciﬁcation method of software modules.
Professor Brzozowski worked for many years in the area of asynchronous circuit theory. He wrote a monograph “Asynchronous Circuits”, Springer, 1995 (with C.-J. Seger), and many papers on this topic. He is interested in 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 research 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.
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)
Professor Brzozowski has held visiting appointments at University of California, Berkeley, CA (1965-66); Istituto Nazionale di Alta Matematica, Rome, Italy (1972); Institut de Programmation, Université Paris VI and VII, Paris, France (1974-75); Gesellschaft für Mathematik und Datenverarbeitung Bonn, Germany (1975); Instituto de Matemática e Estatística, 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).
J. Brzozowski, G. Jirásková, and B. Li. Quotient Complexity of Ideal Languages. 9th Latin American Theoretical Informatics Symposium, LATIN 2010, Oaxaca, Mexico, April 19-23, 2010. A. Lopez-Ortiz. ed., LNCS 6034, pp. 208-221, 2010.
J. Brzozowski. Quotient Complexity of Regular Languages. Descriptional Complexity of Formal Systems, DCFS 2009 Magdeburg, Germany, July 6-9, 2009. Otto-von-Guericke-Universität Magdeburg, pp. 25-42, 2009. To appear in Journal of Automata, Languages and Combinatorics.
J. Brzozowski, J. Shallit, and Z. Xu. Decision Problems for Convex Languages. Language and Automata Theory and Applications, LATA 2009, Tarragona, Spain, April 2-8, 2009. A. Dediu, A. Ionescu, C. Martin-Vide, eds., LNCS 5457, pp. 247-258, 2009. To appear in Information and Computation.
J. Brzozowski and N. Santean. Predictable Semiautomata. Theoretical Computer Science, 410:3236-3249, 2009.
J. Brzozowski, E. Grant, and J. Shallit. Closures in Formal Languages and Kuratowski's Theorem. Developments in Language Theory, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. V. Diekert, D. Nowotka, eds., LNCS 5583, pp. 125-144, 2009. To appear in Int. J. Foundations of Computer Science.