Janusz A. Brzozowski
# Janusz A. Brzozowski

Janusz Antoni Brzozowski, né le 10 mai 1935 à Varsovie en Pologne et mort le 24 octobre 2019 à Waterloo au Canada, était un informaticien polonais canadien.

Brzozowski était surtout connu pour ses contributions fondamentales à la logique mathématique, la théorie des circuits et la théorie des automates.

## Biographie

En 1962, Brzozowski obtint un doctorat dans le domaine de l'ingénierie électrique à l'université de Princeton sous la direction de Edward J. McCluskey, avec une thèse intitulée Regular Expression Techniques for Sequential Circuits. De 1967 à 1996 il fut professeur à l'université de Waterloo. Depuis 1966, il était « Distinguished Professor Emeritus » de l'université de Waterloo.

## Contributions scientifiques

Brzozowski est réputé notamment pour ses travaux fondamentaux sur les expressions régulières et les monoïdes syntaxiques de langages formels. Un résultat notable a été la caractérisation algébrique des langages localement testables avec Imre Simon, qui a donné une impulsion similaire au développement de la théorie algébrique des langages formels que la célèbre caractérisation des langages sans étoile par Marcel-Paul Schützenberger .

Dans ce domaine, il existe aujourd'hui au moins trois concepts portant le nom de Brzozowski en l'honneur de ses contributions : Le premier est la « conjecture de Brzozowski » nommé ainsi par de Luca et Varicchio à propos la régularité des classes sans compteur. Le deuxième est « l'algorithme de Brzozowski » qui figure dans de nombreux manuels, un algorithme conceptuellement simple pour effectuer la minimisation d'un automate fini déterministe. Enfin, Eilenberg, dans le volume B de son ouvrage de référence sur la théorie des automates, consacre un chapitre à ce qu'il appelle la « hiérarchie de Brzozowski » à l'intérieur des langages sans étoile, aussi connue maintenant sous le nom dot-depth hierarchy. Brzozowski est coauteur de l'article où est défini la hiérarchie de concaténation (en) et où est posé la question de savoir si cette hiérarchie est stricte ; il est également coauteur de l'article paru environ dix ans plus tard qui répond à la question. La hiérarchie de Brzozowski a gagné en importance depuis que Wolfgang Thomas a découvert une relation entre le concept algébrique de la hiérarchie de concaténation et la profondeur de l'alternance de quantificateurs dans la logique du premier ordre via les jeux d'Ehrenfeucht-Fraïssé.

## Honneurs et récompenses

* Bourse d'échange scientifique NSERC pour la France (1974–1975)
* Japan Society for the Promotion of Science Research Fellowship (1984)
* Medaille du mérite, université catholique de Lublin, Pologne (2001)
* Canadian Pioneer in Computing, IBM (2005)

## Articles scientifiques à grand impact

* John A. Brzozowski, « Derivatives of regular expressions », Journal of the ACM, vol. 11, $n^o$ 4,‎ 1964, p. 481-494
* John A. Brzozowski et Imre Simon, « Characterizations of Locally Testable Events », dans Proc. 12th. Annual Symposium on Switching and Automata Theory, Piscataway, NJ, IEEE, 1971, p. 166-176
* Rina S. Cohen et John A. Brzozowski, « Dot-Depth of Star-Free Events », Journal of Computer and System Sciences, vol. 5, $n^o$ 1,‎ 1971, p. 1-16
* John A. Brzozowski et R. Knast, « The Dot-Depth Hierarchy of Star-Free Languages is Infinite », Journal of Computer and System Sciences, vol. 16, $n^o$ 1,‎ 1978, p. 37–55

## Livres

* John A. Brzozowski et M. Yoeli, Digital Networks, Prentice–Hall, 1976
* John A. Brzozowski et Carl-Johan H. Seger, Asychronous Circuits, Springer-Verlag, 1995
