Infinite words with linear subword complexity. (English) Zbl 0682.68083

Summary: In Section 1 we study the relations among some combinatorial properties of infinite words, especially in the case of infinite words with linear subword complexity; the main result of Section 1 concerns a permutation property of infinite words with linear complexity. In Section 2 we investigate the special case of the sturmian infinite words; the main result is that a sturmian infinite word associated to a real number \(\alpha\) contains no kth powers iff \(\alpha\) has a continued fraction expansion with bounded partial quotients. In Section 3 it is shown that some of the results of Sections 1 and 2 are optimal.


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
11A63 Radix representation; digital problems
11A55 Continued fractions
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Limit S_oo where S_0 = 0, S_i = S_{i-1} 1^(4^i) S_{i-1} for i >0.


[1] Berstel, J., Mots de Fibonacci, (Séminaire d’Informatique Théorique, LITP (1980/81), Université de Paris VI et VII), 57-78
[3] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[4] Blyth, R. D., Rewriting products of groups elements, (Ph.D. Thesis (1987), University of Illinois: University of Illinois Urbana-Champaign) · Zbl 0647.20033
[5] Coven, E. M.; Hedlund, G. A., Sequences with minimal block growth, Math. Systems Theory, 7, 138-153 (1973) · Zbl 0256.54028
[6] Curzio, M.; Longobardi, P.; Maj, M., Su di un prblema combinatorio in teoria dei gruppi, Atti Acc. Lincei Rend. Fis. VIII, 74, 136-142 (1983)
[7] Curzio, M.; Longobardi, P.; Maj, M.; Robinson, D. J.S., A permutational property of groups, Arch. Math., 44, 385-389 (1985) · Zbl 0544.20036
[8] de Luca, A.; Varricchio, S., Some combinatorical properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci., 63, 333-348 (1989) · Zbl 0671.10050
[9] de Luca, A.; Varricchio, S., On the factors of the Thue-Morse word on three symbols, Inform. Process. Lett., 27, 281-285 (1988) · Zbl 0746.68067
[11] Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of D0L languages with a constant distribution, Inform. Process. Lett., 13, 108-113 (1981) · Zbl 0546.68062
[12] Justin, J., Groupes et semigroupes à croissance lineaire, C.R. Acad. Sci. Paris Ser. A, 273, 212-214 (1971) · Zbl 0218.20050
[13] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers, ((1983), Oxford University Press) · Zbl 0020.29201
[14] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[15] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[16] Morse, M.; Hedlund, G. A., Symbolic dynamics II: Sturmian trajectories, Amer. J. Math., 62, 1-42 (1940) · JFM 66.0188.03
[17] Pirillo, G., On permutation properties for finitely generated semigroups, Combinatorics (1986), Conference Proc., Passo della Mendola, Italy
[18] Rauzy, G., Suites à termes dans un alphabet fini, Exposé No. 25, Séminaire de Théorie des Nombres de Bordeaux (1982/83)
[19] Rauzy, G., Mots infinis en arithmétique, (Nivat, M.; Perrin, D., Automata on Infinite Words. Automata on Infinite Words, Lecture Notes in Computer Science, Vol. 192 (1985), Springer: Springer Berlin), 165-171 · Zbl 0613.10044
[20] Restivo, A.; Reutenauer, C., On the Burnside problem for semigroups, J. Algebra, 89, 102-104 (1984) · Zbl 0545.20051
[22] Wilkie, A. J.; van den Dries, L., An effective bound for groups of linear growth, Arch. Math., 42, 391-396 (1984) · Zbl 0567.20016
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.