Janusz A. Brzozowski

Janusz Antoni Brzozowski, né le à Varsovie en Pologne et mort le à Waterloo au Canada, était un informaticien polonais canadien.

Janusz (John) Brzozowski
Janusz Brzozowski en 2018.
Naissance
Varsovie (Pologne)
Décès
Waterloo (Canada)
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

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 (en) et où est posé 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, no 4,‎ , 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, , p. 166-176
  • Rina S. Cohen et John A. Brzozowski, « Dot-Depth of Star-Free Events », Journal of Computer and System Sciences, vol. 5, no 1,‎ , 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, no 1,‎ , p. 37–55

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

Notes et références
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Janusz Brzozowski (computer scientist) » (voir la liste des auteurs).
  1. Jean-Éric Pin, « Syntactic semigroups », dans G. Rozenberg et A. Salomaa (éditeurs), Handbook of Formal Language Theory, vol. I, Springer Verlag, (lire en ligne), p. 679-746 (chapitre 10).
  2. Volker Diekert, Paul Gastin et Manfred Kufleitner, « A Survey on Small Fragments of First-Order Logic over Finite Words », Int. J. Found. Comput. Sci., vol. 19, no 3,‎ , p. 513-548.
  3. Aldo de Luca et Stefano Varricchio, « Regularity and Finiteness Conditions », dans G. Rozenberg et A. Salomaa (éditeurs), Handbook of Formal Language Theory, vol. I, Springer Verlag, , p. 747–810 (chapitre 11).
  4. Jeff Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, , 240 p. (ISBN 978-0-521-86572-2).
  5. Samuel Eilenberg, Automata, Languages and Machines, vol. B, Academic Press, (ISBN 0-12-234001-9).
  6. Cohen et Brzozowski 1971.
  7. Brzozowski et Knast 1978.
  8. Wolfgang Thomas, « Classifying Regular Events in Symbolic Logic », J. Comput. Syst. Sci., vol. 25, no 3,‎ , p. 360-376.
  9. Pioneers of Computing in Canada « Copie archivée » (version du 13 juillet 2011 sur l'Internet Archive)

Articles connexes

Liens externes


  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.