Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T00:58:39.406Z Has data issue: false hasContentIssue false
  • English
  • Français

Ensembles Reconnaissables de Mots Biinfinis

Published online by Cambridge University Press:  20 November 2018

Maurice Nivat  and
Dominique Perrin
Maurice Nivat
Affiliation:
Université Paris 7, Paris, France
Dominique Perrin
Affiliation:
Université Paris 7, Paris, France
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 38 , Issue 3 , 01 June 1986 , pp. 513 - 537
Copyright
Copyright © Canadian Mathematical Society 1986

References

Bibliographie

1. Beauquier, D., Bilimites de langages reconnaissables, Theoretical Comput. Sci. 33 (1984), 335–342.Google Scholar
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. Compton, K., On rich words, in Combinatorics on words (Academic Press, 1983), 39–62.CrossRefGoogle Scholar
4. Eilenberg, S., Automata, languages and machines, Vol. A (Academic Press, 1974).Google Scholar
5. Graham, R., Rotschild, B. and Spencer, J., Ramsey theory (Wiley, 1980).Google Scholar
6. Gurevitch, Y. et Harrington, L., Trees, automata and games, Proc. 14th ACM Symp. on Theor. of Computing (1982), 60–65.Google Scholar
7. Lallement, G., Semigroups and combinatorial applications (Wiley, 1979).Google Scholar
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. McNaughton, R., Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521–530.Google Scholar
10. Rabin, M., Decidability of second order theories and automata on infinite trees. Trans. AMS 141 (1969), 1–35.Google Scholar
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. Schützenberger, M. P., A propos des relations rationnelles fonctionnelles, in Automata, languages and programming (North Holland, 1973), 103–114.Google Scholar
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. Shelah, S., The monadic theory of order, Annals of Math. 102 (1975), 379–419.Google Scholar
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. Weiss, B., Subshifts of finite type and sophic systems, Monatshefte für Mathematik 77 (1973), 462–474.Google Scholar