Janusz A. Brzozowski
Distinguished Professor Emeritus
Joined School 1967

BASc (Toronto),
MASc (Toronto),
MA (Princeton),
PhD (Princeton)

Email brzozo@uwaterloo.ca
Web http://maveric.uwaterloo.ca/~brzozo
Voice 519-888-4567 x34441
Fax 519-885-1208

Research Interests

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 finite automaton accepting a given regular language, and is commonly used as a complexity measure. He generalized the concept of “convex language” that unifies 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 finite automata by using look-ahead information. He has 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 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.

Major 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 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).

Representative Publications

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.


Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics


Valid HTML 4.01!Valid CSS! Last modified: Tuesday, 13-Nov-2012 09:17:28 EST


Menu:ShowHide