eGALITé DES FACTEURS DIAGONALES DE SéRIES FORMELLES

I. FAGNOT

IBP-Litp 1995/Th/01: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Litp / Litp research reports
123 pages - Mars/March 1995 - French document.

PostScript : Ko /Kb

Titre / Title: eGALITé DES FACTEURS DIAGONALES DE SéRIES FORMELLES

Résumé : Dans cette thèse, nous étudions deux sujets de combinatoire des mots.

Le premier est le problème de l'égalité des facteurs, c'est-à-dire la décidabilité de l'égalité des facteurs de deux mots infinis. Nous montrons que ce problème est décidable pour deux mots morphiques, sous réserve que les morphismes soient primitifs et à délai borné.Nous montrons, de même, que ce problème est décidable pour tout couple de mots morphiques dans le cas d'un alphabet à deux lettres. Le problème est également décidable pour deux mots automatiques. Nous démontrons aussi un théorème ``à la Cobham'' : Soient p et q deux entiers multiplicativement indépendants et soient x un mot p-automatique et y un mot q-automatique. Si x et y ont les mêmes facteurs, alors ils sont tous les deux ultimement périodiques.

Le deuxième sujet traite des diagonales de séries formelles. Un célèbre théorème de Furstenberg dit que, dans un corps fini, toute série formelle algébrique en une indéterminée est la diagonale d'une fraction rationnelle en deux indéterminées. Dans cette partie, nous donnons une nouvelle preuve de ce résultat par des méthodes purement combinatoires. Nous appliquons ensuite les techniques utilisées pour résoudre des problèmes similaires à propos des séries mahlériennes.

Abstract : In this thesis, two word combinatoric subjects are studied.
The first one is the subword equivalence problem, i. e. to decide whether two infinite words have the same set of finite subwords (factors). The problem is shown to be decidable for two morphic words, provided the morphisms are primitive and with bounded delays. It is also proved to be decidable for two morphic words on a binary alphabet. For two automatic words, the problem is also decidable. The study of this case leads to a generalization of Cobham's theorem : Let p and q be two multiplicatively independent integers and let x be a p-automatic word and y be a q-automatic word. If x and y have the same factors, then both are ultimately periodic.
The second subject deals with the formal series diagonals. Fusrtenberg proved that, in a finite field, every formal series of one variable is the diagonal of a two-variable rational fraction. In this part, a new proof of this result is given by combinatorial methods, which are then used to solve similar Mahler series problems.

Publications internes Litp 1995 / Litp research reports 1995