×

Periods in extensions of words. (English) Zbl 1100.68088

Summary: Let \(\pi(w)\) denote the minimum period of the word \(w\), let \(w\) be a primitive word with period \(\pi(w) < |w|\), and let \(z\) be a prefix of \(w\). It is shown that if \(\pi(wz) = \pi(w)\), then \(|z| < \pi(w) - \text{gcd}\left(|w|, |z|\right)\). Detailed improvements of this result are also proven. Finally, we show that each primitive word \(w\) has a conjugate \(w' = vu\), where \(w = uv\), such that \(\pi(w') = |w '|\) and \(|u| < \pi(w)\). As a corollary we give a short proof of the fact that if \(u,v,w\) are words such that \(u^2\) is a prefix of \(v^2\), and \(v^2\) is a prefix of \(w^2\), and \(v\) is primitive, then \(|w| > 2|u|\).

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel J., Karhumäki J. (2003). Combinatorics on words – a tutorial. Bull. EATCS 79:178–229 · Zbl 1169.68560
[2] Césari Y., Vincent M. (1978). Une caractérisation des Mots Périodiques. C. R. Acad. Sci. Paris Ser. A 286:1175–1177 · Zbl 0392.20039
[3] Crochemore M., Perrin D. (1991). Two-Way String-Matching. J. ACM 38(3):651–675 · Zbl 0808.68063 · doi:10.1145/116825.116845
[4] Crochemore M., Rytter W. (1995). Squares, cubes, and time-space efficient string searching. Algorithmica 13(5):405–425 · Zbl 0849.68044 · doi:10.1007/BF01190846
[5] Duval J.P. (1979). Périodes et Répétitions des mots de monoïde libre. Theor. Comput. Sci. 9(1):17–26 · Zbl 0402.68052 · doi:10.1016/0304-3975(79)90003-3
[6] Fine N.J., Wilf H.S. (1965). Uniqueness theorem for periodic functions. Proc. Am. Math. Soc. 16:109–114 · Zbl 0131.30203 · doi:10.1090/S0002-9939-1965-0174934-9
[7] Harju T., Nowotka D. (2002). Density of Critical factorizations. Theor. Inf. Appl. 36(3):315–327 · Zbl 1013.68154 · doi:10.1051/ita:2002016
[8] Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics, vol. 17. Addision-Wesley, Reading (1983). Reprinted in the Cambridge Mathematical Library, Cambridge University Press, 1997
[9] Lothaire M. (2002). Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, Cambridge · Zbl 1001.68093
[10] Lothaire M. (2005). Applied Combinatorics on Words. Cambridge University Press, Cambridge · Zbl 1133.68067
[11] Morita H., van Wijngaarden A.J., Han Vinck A.J. (1996). On the construction of maximal prefix-synchronized codes. IEEE Trans. Inf. Theory 42:2158–2166 · Zbl 0869.94010 · doi:10.1109/18.556604
[12] Schützenberger, M.P.: A property of finitely generated submonoids of free monoids. In: Algebraic Theory of Semigroups (Proceedings of the Sixth Algebraic Conference Szeged, 1976),Colloq. Math. Soc. János Bolyai, vol. 20, pp. 545–576. North-Holland, Amsterdam (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.