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
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