Janusz (John) Antoni Brzozowski (May 10, 1935 – October 24, 2019) was a Polish-Canadian

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

and Distinguished Professor Emeritus at the

University of Waterloo The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...

's David R. Cheriton School of Computer Science. In 1962, Brzozowski earned his PhD in the field of

electrical engineering Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems which use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...

Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...

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

. He is known for his contributions to

mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...

circuit theory Circuit may refer to: Science and technology Electrical engineering * Electrical circuit, a complete electrical network with a closed-loop giving a return path for current ** Analog circuit, uses continuous signal levels ** Balanced circui ...

, and

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

Achievements in research

Brzozowski worked on

regular expressions A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...

and on syntactic semigroups of

formal languages In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (formal languages), alphabet and are well-formedness, well-formed ...

.Pin (1997) The result was ''Characterizations of locally testable events'' written together with

Imre Simon Imre Simon (August 14, 1943 – August 13, 2009) 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, ...

, which had a similar impact on the development of the algebraic theory of formal languages as

Marcel-Paul Schützenberger Marcel-Paul "Marco" Schützenberger (24 October 1920 – 29 July 1996) was a French mathematician and Doctor of Medicine. He worked in the fields of formal language, combinatorics, and information theory.Herbert Wilf, Dominique Foata, ''et al.' ...

's characterization of the

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

s. In the area, today at least four concepts bear Brzozowski's name in honour of his contributions: The first is the ''Brzozowski's conjecture''de Luca and Varicchio (1997) about the regularity of noncounting classes. Second, '' Brzozowski's algorithm'', a conceptually simple algorithm for performing

DFA minimization In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equival ...

. Third, the ''

Brzozowski derivative In theoretical computer science, in particular in formal language theory, the Brzozowski derivative u^S of a set S of strings and a string u is the set of all strings obtainable from a string in S by cutting off the prefix u, as illustrated in th ...

'' of a formal language or of a generalised

regular expression A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...

. Fourth, Eilenberg's reference work on automata theory has a chapter devoted to the so-called ''Brzozowski hierarchy'' inside the

s, also known as ''dot-depth hierarchy''. Notably, 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 Wolfgang Thomas discovered a relation between the algebraic concept of dot-depth and the alternation depth of quantifiers in

first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

via

Ehrenfeucht–Fraïssé game In the mathematical discipline of model theory, the Ehrenfeucht–Fraïssé game (also called back-and-forth games) is a technique based on game semantics for determining whether two structures are elementarily equivalent. The main application of ...

s. He received the following academic awards and honours: * NSERC Scientific Exchange Award to France (1974–1975) * Japan Society for the Promotion of Science Research Fellowship (1984) *

Computing Research Association The Computing Research Association (CRA) is a 501(c)3 non-profit association of North American academic departments of computer science, computer engineering, and related fields; laboratories and centers in industry, government, and academia enga ...

Certificate of Appreciation for outstanding contributions and service as a member of the CRA Board of Directors (1992) * Distinguished Professor Emeritus,

, Canada (1996) * Medal of Merit, Catholic University of Lublin, Poland (2001) * IBM Canada Canadian Pioneer in Computing (2005) *The Role of Theory in Computer Science, a one-day conference in honour of John Brzozowski's 80th birthday (2015) *The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski, World Scientific (2017) *Lifetime Achievement Award, Computer Science Canada/Informatique Canada (CS-CAN/INFO-CAN) (2016) *CIAA 2017 Sheng Yu Award for Best Paper for ''Complexity of Proper Prefix-Convex Regular Languages'' by J. Brzozowski and C. Sinnamon *CIAA 2018 Sheng Yu Award for Best Paper for ''State Complexity of Overlap Assembly'' by J. Brzozowski, L. Kari, B. Li, M. Szykula

Research papers

* J. A. Brzozowski:

Derivatives The derivative of a function is the rate of change of the function's output relative to its input value. Derivative may also refer to: In mathematics and economics * Brzozowski derivative in the theory of formal languages * Formal derivative, an ...

of regular expressions, ''

Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan ...

'' 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 The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been publishe ...

'' 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: Asynchronous Circuits. Springer-Verlag, 1995

Notes

References

* S. Eilenberg, ''Automata, Languages and Machines'', Volume B. * W. Thomas, ''Classifying Regular Events in Symbolic Logic.'' J. Comput. Syst. Sci. 25(3): 360–376 (1982) * J.-É. Pin
''Syntactic semigroups''
Chapter 10 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 679–746 * A. de Luca and S. Varicchio, ''Regularity and Finiteness Conditions'', Chapter 11 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 747–810 * V. Diekert, P. Gastin, M. Kufleitner
''A Survey on Small Fragments of First-Order Logic over Finite Words.''
Int. J. Found. Comput. Sci. 19(3): 513–548 (2008) * J. Shallit, ''A Second Course in Formal Languages and Automata Theory'', Cambridge University Press (2009)

External links

Profile of Janusz Brzozowski, University of Waterloo

Brzozowski's personal website
at the University of Waterloo

*

by Jean-Éric Pin {{DEFAULTSORT:Brzozowski, Janusz 1935 births 2019 deaths Canadian computer scientists Polish computer scientists Polish emigrants to Canada Princeton University alumni Theoretical computer scientists Academic staff of the University of Waterloo