Sur l'automaticite des mots de toeplitz

• Date de parution : 19/09/2010
• Editeur : Editions Universitaires Europeennes
• EAN : 9786131527555
• Série : (-)
• Support : Papier

• Nombre de pages : (-)
• Collection : (-)
• Genre : Lettres et linguistique
• Thème : Critiques et Essais de Lettres et linguistique
• Prix littéraire(s) : (-)

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... Voir plus

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.