Open problems about regular
languages, 35 years later
J.-É. Pin
Résumé : En 1980, Janusz A. Brzozowski a
présenté une sélection de six problèmes ouverts
sur les langues réguliers et mentionné également deux
autres problèmes dans la conclusion de son article. Ces
problèmes ont été à l'origine de quelques-unes
des plus grandes percées dans la théorie des automates cours
des dernières 35 années. Cet article de synthèse
résume l'état de l'art sur ces questions et les espoirs pour
les 35 prochaines années.
Abstract : In 1980, Janusz A. Brzozowski presented a selection of
six open problems about regular languages and mentioned two other problems
in the conclusion of his article. These problems have been the source of
some of the greatest breakthroughs in automata theory over the past 35
years. This survey article summarizes the state of the art on these
questions and the hopes for the next 35 years.