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

Mignosi, Filippo

Theor. Comput. Sci. 65, No. 2, 221-242 (1989).

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.

MSC:

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

Keywords:

linear complexity and combinatorial properties; infinite words; subword complexity; sturmian infinite words

References:

[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