×

A combinatorial theorem on p-power-free words and an application to semigroups. (English) Zbl 0701.68065

Summary: Some combinatorial properties of infinite words having a subword complexity which is linearly upper-bounded are considered. The main result is a theorem giving a characterization of infinite words having a linear subword complexity in terms of the number of completions of the factors which do not contain multiple overlaps. An interesting application of this theorem is that the monoid of the factors of an infinite p-overlap-free word is weakly-permutable. This generalizes previous results obtained by Restivo and the authors for the Fibonacci and the Thue-Morse monoids respectively.

MSC:

68Q45 Formal languages and automata
68R15 Combinatorics on words
20M05 Free semigroups, generators and relations, word problems
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. J. BERSTEL, Mots de Fibonacci, Seminaire d’Informatique Théorique, L.I.T.P. Université Paris-VI et VII, Année 1980/81, pp. 57-78.
[2] 2. R. D. BLYTH, Rewriting Products of Groups Elements, Ph. D. Thesis, 1987, University of Illinois at Urbana-Champain. MR2635772
[3] 3. A. DE LUCA and S. VARRICCHIO, Some Combinatorial Properties of the Thue-Morse Sequence and a Problem in Semigroups, Theoretical Computer Science, Vol. 63, 1989, pp. 333-348. Zbl0671.10050 MR993769 · Zbl 0671.10050 · doi:10.1016/0304-3975(89)90013-3
[4] 4. A. DE LUCA and S. VARRICCHIO, On the Factors of the Thue-Morse Word on Three Symbols, Information Processing Letters, Vol. 27, 1988, pp. 281-285. Zbl0746.68067 MR947256 · Zbl 0746.68067 · doi:10.1016/0020-0190(88)90214-1
[5] 5. A. EHRENFEUCHT and G. ROZENBERG, On the Subword Compîexity of DOL Languages with a Constant Distribution, Information Processing Letters, Vol. 13, 1981, pp. 108-113. Zbl0546.68062 MR645455 · Zbl 0546.68062 · doi:10.1016/0020-0190(81)90121-6
[6] 6. A. EHRENFEUCHT and G. ROZENBERG, On the Subword Complexity of Square-Free DOL Languages, Theoretical Computer Science, Vol. 16, 1981, pp. 25-32. Zbl0481.68073 MR632668 · Zbl 0481.68073 · doi:10.1016/0304-3975(81)90028-1
[7] 7. J. KARHUMAKI, On Cube-Free w-Words Generated by Binary Morphisms, Discrete Applied Mathematics, Vol. 5, 1983, pp. 279-297. Zbl0505.03022 MR690339 · Zbl 0505.03022 · doi:10.1016/0166-218X(83)90002-1
[8] 8. M. LOTHAIRE, Combinatorics on Words, Addition Wesley, Reading, MA, 1983. Zbl0514.20045 MR675953 · Zbl 0514.20045
[9] 9. A. RESTIVO and C. REUTENAUER, On the Burnside Problem for Semigroups, J. of Algebra, Vol. 89, 1984, pp. 102-104. Zbl0545.20051 MR748230 · Zbl 0545.20051 · doi:10.1016/0021-8693(84)90237-0
[10] 10. A. RESTIVO, Permutation Properties and the Fibonacci Semigroup, Semigroup Forum, Vol. 38, 1989, pp. 337-345. Zbl0663.20063 MR982013 · Zbl 0663.20063 · doi:10.1007/BF02573241
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.