Geodesic
Ensembles Reconnaissables de Mots Biinfinis
Canadian journal of mathematics, Tome 38 (1986) no. 3, pp. 513-537

Voir la notice de l'article provenant de la source Cambridge University Press

Introduction. La théorie des automates finis fait partie de ce que l'on appelle aujourd'hui les mathématiques de l'informatique. Comme pour les autres spécialités de ce domaine, elle est née des travaux de logiciens et, pour les automates finis, c'est à Kleene que l'on doit le premier théorème. Cette théorie s'est considérablement développée depuis la période des fondations. La direction principale est l'étude des automates reconnaissant des suites finies ou mots. Elle présente des aspects mathématiques qui la rapprochent de domaines classiques comme par exemple la théorie combinatoire des groupes. Parallèlement, plusieurs auteurs ont étudié le comportement des automates finis sur des objets plus généraux que les mots. C'est le cas notamment pour la théorie des automates reconnaissant des arbres. C'est aussi le cas pour les automates reconnaissant des mots infinis qui sont le sujet de cet article. 
Nivat, Maurice; Perrin, Dominique. Ensembles Reconnaissables de Mots Biinfinis. Canadian journal of mathematics, Tome 38 (1986) no. 3, pp. 513-537. doi: 10.4153/CJM-1986-025-6
@article{10_4153_CJM_1986_025_6,
     author = {Nivat, Maurice and Perrin, Dominique},
     title = {Ensembles {Reconnaissables} de {Mots} {Biinfinis}},
     journal = {Canadian journal of mathematics},
     pages = {513--537},
     year = {1986},
     volume = {38},
     number = {3},
     doi = {10.4153/CJM-1986-025-6},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1986-025-6/}
}
TY  - JOUR
AU  - Nivat, Maurice
AU  - Perrin, Dominique
TI  - Ensembles Reconnaissables de Mots Biinfinis
JO  - Canadian journal of mathematics
PY  - 1986
SP  - 513
EP  - 537
VL  - 38
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1986-025-6/
DO  - 10.4153/CJM-1986-025-6
ID  - 10_4153_CJM_1986_025_6
ER  - 
%0 Journal Article
%A Nivat, Maurice
%A Perrin, Dominique
%T Ensembles Reconnaissables de Mots Biinfinis
%J Canadian journal of mathematics
%D 1986
%P 513-537
%V 38
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1986-025-6/
%R 10.4153/CJM-1986-025-6
%F 10_4153_CJM_1986_025_6

[1] 1. Beauquier, D., Bilimites de langages reconnaissables, Theoretical Comput. Sci. 33 (1984), 335–342. Google Scholar

[2] 2. Büchi, R., On a decision method in restricted second order arithmetic, in Logic, methodology and philosophy of science, Proc. 1960 Internat. Congress (Stanford Univ. Press, 1962), 1–11. Google Scholar

[3] 3. Compton, K., On rich words, in Combinatorics on words (Academic Press, 1983), 39–62. Google Scholar | DOI

[4] 4. Eilenberg, S., Automata, languages and machines, Vol. A (Academic Press, 1974). Google Scholar

[5] 5. Graham, R., Rotschild, B. and Spencer, J., Ramsey theory (Wiley, 1980). Google Scholar

[6] 6. Gurevitch, Y. et Harrington, L., Trees, automata and games, Proc. 14th ACM Symp. on Theor. of Computing (1982), 60–65. Google Scholar

[7] 7. Lallement, G., Semigroups and combinatorial applications (Wiley, 1979). Google Scholar

[8] 8. Muller, D. et Schupp, P., The theory of ends pushdown automata and second order logic, Theoret. Comput. Sci., 37 (1985), 51–76. Google Scholar

[9] 9. McNaughton, R., Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521–530. Google Scholar

[10] 10. Rabin, M., Decidability of second order theories and automata on infinite trees. Trans. AMS 141 (1969), 1–35. Google Scholar

[11] 11. Rabin, M., Automata on infinite objects and Church's problems, Amer. Math. Soc. Regional Conferences Series in Math. 13 (1972), 1–23. Google Scholar

[12] 12. Schützenberger, M. P., A propos des relations rationnelles fonctionnelles, in Automata, languages and programming (North Holland, 1973), 103–114. Google Scholar

[13] 13. Semenov, A., Decidability of monadic theories, in Mathematical foundations of computer science, Lecture Notes in Comput. Sci. 176 (1984), 162–175. Google Scholar

[14] 14. Shelah, S., The monadic theory of order, Annals of Math. 102 (1975), 379–419. Google Scholar

[15] 15. Thomas, W., A hierarchy of sets of infinite trees, in Theoretical computer science. Springer Lecture Notes in Comput. Sci. 145 (1982). Google Scholar

[16] 16. Weiss, B., Subshifts of finite type and sophic systems, Monatshefte für Mathematik 77 (1973), 462–474. Google Scholar

Cité par Sources :