Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Janusz A. Brzozowski
Résumé
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.
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.
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 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.