Janusz A. Brzozowski
Naissance |
Varsovie (Pologne) |
---|---|
Décès |
(à 84 ans) 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 |
Janusz Antoni Brzozowski, né le à Varsovie en Pologne et mort le à 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
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]- 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
[modifier | modifier le code]- 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
[modifier | modifier le code]- 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
[modifier | modifier le code]- 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).
- 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.
- 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).
- Jeff Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, , 240 p. (ISBN 978-0-521-86572-2).
- Samuel Eilenberg, Automata, Languages and Machines, vol. B, Academic Press, (ISBN 0-12-234001-9).
- Cohen et Brzozowski 1971.
- Brzozowski et Knast 1978.
- Wolfgang Thomas, « Classifying Regular Events in Symbolic Logic », J. Comput. Syst. Sci., vol. 25, no 3, , p. 360-376.
- Pioneers of Computing in Canada « Copie archivée » (version du sur Internet Archive)
Articles connexes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]
- Ressources relatives à la recherche :
- Hiérarchies de concaténation, Jean-Eric Pin