Francúzsky jazyk

Sur l'automaticité des mots de Toeplitz

Vydavateľstvo: Éditions universitaires européennes
Rok vydania: 2010
Formát: Paperback
Rozmer: 220 x 150 mm
Jazyk: Francúzsky jazyk
ISBN: 9786131527555

Na objednávku

73.17 €

bežná cena: 81.30 €

O knihe

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.