1. Open problems about regular languages, 35 years later
- Author
-
Konstantinidis, Stavros, Moreira, Nelma, Reis, Rogério, Shallit, Jeffrey, Pin, Jean-Éric, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Stavros Konstantinidis, Nelma Moreira, Rogério Reis, and Jeffrey Shallit
- Subjects
Computer science ,010102 general mathematics ,ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages ,Open problems ,0102 computer and information sciences ,Regular languages ,01 natural sciences ,Linguistics ,ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.0: Algebraic language theory ,Regular language ,010201 computation theory & mathematics ,Automata theory ,[INFO]Computer Science [cs] ,State (computer science) ,0101 mathematics ,[MATH]Mathematics [math] ,Selection (genetic algorithm) - Abstract
International audience; 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.; 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.
- Published
- 2017