Janusz A. Brzozowski
Distinguished Professor Emeritus Joined School 1967 BASc (Toronto),

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 nondeterminism in ﬁnite automata by using lookahead information. He has applied ideas from the theory of automata to the “traceassertion” 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 multivalued 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 randomaccess 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 (19741975)
Professor Brzozowski has held visiting appointments at University of California, Berkeley, CA (196566); Istituto Nazionale di Alta Matematica, Rome, Italy (1972); Institut de Programmation, Université Paris VI and VII, Paris, France (197475); 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 (198990).
J. Brzozowski, G. Jirásková, and B. Li. Quotient Complexity of Ideal Languages. 9th Latin American Theoretical Informatics Symposium, LATIN 2010, Oaxaca, Mexico, April 1923, 2010. A. LopezOrtiz. ed., LNCS 6034, pp. 208221, 2010.
J. Brzozowski. Quotient Complexity of Regular Languages. Descriptional Complexity of Formal Systems, DCFS 2009 Magdeburg, Germany, July 69, 2009. OttovonGuerickeUniversität Magdeburg, pp. 2542, 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 28, 2009. A. Dediu, A. Ionescu, C. MartinVide, eds., LNCS 5457, pp. 247258, 2009. To appear in Information and Computation.
J. Brzozowski and N. Santean. Predictable Semiautomata. Theoretical Computer Science, 410:32363249, 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 30July 3, 2009. V. Diekert, D. Nowotka, eds., LNCS 5583, pp. 125144, 2009. To appear in Int. J. Foundations of Computer Science.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 5198884567 x33293
Fax: 5198851208
Contact  Feedback: cswebmaster@cs.uwaterloo.ca  David R. Cheriton School of Computer Science  Faculty of Mathematics