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.

Janusz (John) Brzozowski

Janusz Brzozowski en 2018.

Données clés

Naissance	10 mai 1935 Varsovie (Pologne)
Décès	24 octobre 2019 (à 84 ans) Waterloo (Canada)

Données clés

Domaines	Informatique théorique
Diplôme	Université de Princeton
Directeur de thèse	Edward J. McCluskey
Étudiants en thèse	Imre Simon, Denis Therien, Rina Cohen
Renommé pour	Minimisation, dérivation, hiérarchies d'automates finis

modifier

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^[1]. Un résultat notable a été la caractérisation algébrique des langages localement testables avec Imre Simon, qui a donné une impulsion similaire ^[2] 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^[3] à propos la régularité des classes sans compteur. Le deuxième est « l'algorithme de Brzozowski » qui figure dans de nombreux manuels^[4], 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 »^[5] à l'intérieur des langages sans étoile, aussi connue maintenant sous le nom dot-depth hierarchy. Brzozowski est coauteur de l'article^[6] où est défini la hiérarchie de concaténation et où est posée la question de savoir si cette hiérarchie est stricte ; il est également coauteur de l'article^[7] 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é^[8].

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^[9] (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