Périodes locales et propagation de périodes dans un mot

✍ Scribed by Jean-Pierre Duval

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 766 KB
• Volume: 204
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00033-4

✦ Synopsis

A word of length n over an alphabet A is a sequence al . . a,, of letters of A. It is convenient to consider a "long enough" word over A as an infinite right word, that is an infinite sequence al . ai of elements of A. An integer 1 is a period of the word in the interval [j . k] if we have a, = a;+~. for those indices i and i + 1 in the considered interval. The period of a word designates its smallest period over its whole length. A point p of a word is the cut (al . a,, up+, . .). A non-negative integer 1 is a local period at point p iff i is a period in the interval [p -1 + I . p + A]. According to the critical point's theorem [ 1,2], the period of a "long enough (or not)" word is the maximum of the minimal local periods taken in each point of this word. M.P. Schiitzenberger, who was at the origin of the research work on the relations between local periods and periods of a word obtained by concatenation of periodical words, and our ability to characterize its period from the observation of the local period at the concatenation points only. This is the formulation of the unpublished answer we offered him that we suggest here. @ 1998--Elsevier Science B.V. All rights reserved R&urn6 Un mot de longueur n sur un alphabet A est une suite al a, de lettres de A. 11 est commode de considerer un mot "suffisamment long" sur A comme un mot infini a droite, c'est a dire d'une suite infinie al ui.. d'eliments de A. Un entier ,? est une pkriode du mot sur l'intervalle [j.. k] si l'on a a, = a;+~, pour ceux des indices i et i + i du mot qui sont dans l'intervalle consider&. La periode d'un mot designe sa plus petite periode sur toute sa longueur. Un point p d'un mot designe la coupure (al . a,, a,+~ . .) ; un entier positif 1 est une pkriode locale au point p si et seulement si 1 est une periode sur l'intervalle [p -I + 1 . p + 11. D'apres le theoreme du point critique [ 1,2], la periode d'un mot suffisamment long ou non est le maximum des periodes locales minimales prises en chacun des points de ce mot. M.P. Schiitzenberger qui est a l'origine des travaux sur les relations entre p&odes locales et ptriodes d'un mot, nous a plus recemment interrogt sur le cas d'un mot obtenu par concatenation de mots periodiques et la possibilite de caracttriser sa p&ode par une observation de la ptriode locale aux seuls points de concatenation. C'est une formulation de la rtponse non publiee que nous lui avons apportee que nous proposons ici.