Sur L'automaticiti Des Mots De Toeplitz Mots Automatiques (french Edition) [Paperback]

On ?tudie une famille de mots infinis, ? savoir les mots de Toeplitz. Un mot de Toeplitz sur un alphabet A est d?fini it?rativement ? partir d'une suite infinie de motifs (qui sont des mots finis sur A U {?}) o? chaque occurrence de la lettre ? est remplac?e par une lettre de A ? chaque it?ration. L'objectif ?tant la recherche de conditions sous lesquelles un mot de Toeplitz peut ?tre engendr? par un automate fini. On a recens? tous les mots de la litt?rature qui s'av?rent ?tre des mots de Toeplitz et on montre qu'ils se r?partissent en trois cat?gories : les mots de Toeplitz simples (construits ? partir d'un motif unique) tels la suite de Hanoi ou le mot de Prodinger, les mots de Toeplitz synchrones (dont les motifs sont de longueur mq et dont les q ? occupent les m?mes positions) telles les suites de m-pliage de papier o? q = 2 et les autres (telles les suites de Neveu). En ne consid?rant, pour chaque classe, que les mots dont la suite de motifs est ultimement p?riodique, on a construit explicitement des automates dits universels , au sens qu'il suffit de modifier leur fonction de sortie pour obtenir n'importe quel mot de la classe.