Sur l''automaticité Des Mots de Toeplitz [French]

By Bercoff-C and Christiane Bercoff

On etudie une famille de mots infinis, a savoir les mots de Toeplitz. Un mot de Toeplitz sur un alphabet A est defini iterativement a partir d'une suite infinie de motifs (qui sont des mots finis sur A U { }) ou chaque occurrence de la lettre " " est remplacee par une lettre de A a chaque iteration. L'objectif etant la recherche de conditions sous lesquelles un mot de Toeplitz peut etre engendre par un automate fini. On a recense tous les mots de la litterature qui s'averent etre des mots de Toeplitz et on montre qu'ils se repartissent en trois categories: les mots de Toeplitz simples (construits a 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 memes positions) telles les suites de m-pliage de papier ou q = 2 et les autres (telles les suites de Neveu). En ne considerant, pour chaque classe, que les mots dont la suite de motifs est ultimement periodique, 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."

• Format: Paperback
• Language: French
• ISBN: 6131527555
• ISBN13: 9786131527555
• Release Date: September 2010
• Publisher: Omniscriptum
• Length: 248 Pages
• Weight: 0.81 lbs.
• Dimensions: 0.6" x 6.0" x 9.0"