The dot-depth hierarchy, 45 years later

J.-É. Pin



Résumé : En 1970, R. S. Cohen et Janusz A. Brzozowski ont introduit une hiérarchie de langues sans étoile appellée "dot-depth hierarchy". Cette hiérarchie, ses généralisations et les problèmes afférants ont eu une influence durable sur la développement de la théorie des automates. Cet article fait la synthèse des nombreux résultats et conjectures attachés à cette hiérarchie.

Abstract : In 1970, R. S. Cohen and Janusz A. Brzozowski introduced a hierarchy of star-free languages called the dot-depth hierarchy. This hierarchy and its generalisations, together with the problems attached to them, had a long-lasting influence on the development of automata theory. This survey article reports on the numerous results and conjectures attached to this hierarchy.

PDF file

Valid HTML 4.01!