Christiane Bercoff

Sur L'automaticité Des Mots De Toeplitz: Mots Automatiques Christiane Bercoff French edition

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.