On some properties of doubly-periodic words

Baiocchi, Claudio

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni, Tome 8 (1997), p. 39-47 / Harvested from Biblioteca Digitale Italiana di Matematica

Access to full text
Full (PDF)
Full (DjVu)

Abstract
Résumé

We study the functional equation: $(1) A B C = C D A$ where $A, B, C$ and $D$ are words over an alphabet $A$ . In particular we prove a «structure result» for the inner factors $B, D$ : for suitably chosen words $X, Y, Z$ one has: $(2) B = X Y Z$ , $D = Z Y X$ $(2) B = X Y Z$ , $D = Z Y X$ $(2) B = X Y Z$ , $D = Z Y X$ $(2) B = X Y Z$ , $D = Z Y X$ . It is a generalization of the Lyndon-Schützenberger's Theorem (see [7]): if in (1) $A$ or $C$ is empty, formula (2) holds true with one among $X, Y, Z$ which can be chosen empty.

Si studia l'equazione funzionale: $(1) A B C = C D A$ in cui $A, B, C$ e $D$ sono parole su un alfabeto $A$ . In particolare si ottiene una «formula di struttura» per i fattori centrali $B$ e $D$ : per opportune parole $X, Y, Z$ vale: $(2) B = X Y Z$ , $D = Z Y X$ . Si tratta di una generalizzazione del Teorema di Lyndon-Schützenberger (cfr. [7]): con due soli fattori nella (1) (cioè se una delle parole $A, C$ è vuota) in (2) bastano due fattori (cioè: una almeno tra $X, Y$ e $Z$ è vuota).

Publié le : 1997-04-01

MR 1484544 | Zbl 0886.68107

@article{RLIN_1997_9_8_1_39_0,
     author = {Claudio Baiocchi},
     title = {On some properties of doubly-periodic words},
     journal = {Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni},
     volume = {8},
     year = {1997},
     pages = {39-47},
     zbl = {0886.68107},
     mrnumber = {1484544},
     language = {en},
     url = {http://dml.mathdoc.fr/item/RLIN_1997_9_8_1_39_0}
}

Baiocchi, Claudio. On some properties of doubly-periodic words. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni, Tome 8 (1997) pp. 39-47. http://gdmltest.u-ga.fr/item/RLIN_1997_9_8_1_39_0/

Bibliographie

[1] De Luca, A., A combinatorial property of the Fibonacci word. Information Processing Letters, 12, 1981, 193-195. | MR 632866 | Zbl 0468.20049

[2] De Luca, A., Sturmian words: new combinatorial results. In: J. Almeida - G. M. S. Gomes - P. V. Silva (eds.), Semigroups, Automata and Languages. World Scientific, 1996, 67-83. | MR 1477723 | Zbl 0917.20042

[3] De Luca, A., Sturmian words: Structure, Combinatorics, and their Arithmetics. Theoretical Computer Science, special issue on Formal Language, to appear. | Zbl 0911.68098

[4] De Luca, A. - Mignosi, F., Some combinatorial properties of sturmian words. Theoretical Computer Science, 136, 1994, 361-385. | MR 1311214 | Zbl 0874.68245

[5] Fine, N. J. - Wilf, S. H., Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc., 16, 1965, 109-114. | MR 174934 | Zbl 0131.30203

[6] Lothaire, M., Combinatorics on Words. Addison-Wesley, Reading, MA, 1983. | MR 675953 | Zbl 0514.20045

[7] Lyndon, R. C. - Schützenberger, M. P., On the equation $a^{M} = b^{N} c^{P}$ in a free group. Michigan Math. J., 9, 1962, 289-298. | MR 162838 | Zbl 0106.02204

[8] Perdersen, A., Solution of Problem E 3156. The American Mathematical Monthly, 95, 1988, 954-955.

[9] Robinson, P. M., Problem E 3156. The American Mathematical Monthly, 93, 1986, 482.