×

On a combinatorial property of Sturmian words. (English) Zbl 0872.68144

Summary: Recall that a semigroup has the property \(P^{\ast}_{n}\) if for any sequence of \(n\) of its elements, two differently permuted products of these \(n\) elements are equal. Let \(s\) be an infinite Sturmian word (on a 2-letter alphabet \(A\)). We prove that the Rees quotient of \(A^{\ast}\) by the set of the non-factors of \(s\) has \(P^{\ast}_{4}\) and that this result is the best possible. We prove also that if \(St\) is the set of all finite Sturmian words, then the Rees quotient \(A^{\ast}/(A^{\ast}-St)\) has \(P^{\ast}_{8}.\)

MSC:

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

References:

[1] Berstel, J.; Pocchiola, M., A geometric proof of the enumeration formula for Sturmian words, Internat. J. Algebra Comput., 3, 3, 349-355 (1993) · Zbl 0802.68099
[2] Berstel, J.; Séébold, P., A characterization of Sturmian morphisms, (Borzykowski, A.; Sokolowski, S., Proc. MFCS’93. Proc. MFCS’93, Lecture Notes in Computer Science, Vol. 711 (1993), Springer: Springer Berlin), 281-290 · Zbl 0925.11026
[3] Coven, E.; Hedlung, G., Sequences with minimal block growth, Math. Systems Theory, 7, 138-153 (1973) · Zbl 0256.54028
[4] de Luca, A.; Varricchio, S., Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci., 63, 333-348 (1989) · Zbl 0671.10050
[5] Dulucq, S.; Gouyou-Beauchamps, D., Sur les facteurs des suites de Sturm, Theoret. Comput. Sci., 71, 381-400 (1990) · Zbl 0694.68048
[6] Hedlung, G.; Morse, M., Symbolic dynamics II: Sturmian sequences, Amer. J. Math., 61, 1-42 (1940) · JFM 66.0188.03
[7] Justin, J.; Pirillo, G., Infinite words and permutation properties, (Semigroup Forum, 40 (1990)), 13-22 · Zbl 0681.20039
[8] Justin, J.; Pirillo, G., Factorial Languages and some combinatorial properties of semigroups, Internat. J. Algebra Comput., 3, 3, 295-316 (1993) · Zbl 0796.20045
[9] Lothaire, Combinatorics on words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[10] Mignosi, F., Infinite words with linear subwords complexity, Theoret. Comput. Sci., 65, 221-242 (1989) · Zbl 0682.68083
[11] Mignosi, F., On the number of factors of Sturmian words, Theoret. Comput. Sci., 82, 71-84 (1991) · Zbl 0728.68093
[12] Mignosi, F.; Séébold, P., Morphismes Sturmiens et règles de Rauzy, J. Theorie Nombres Bordeaux, 5, 221-233 (1993) · Zbl 0797.11029
[13] Pirillo, G., On a combinatorial property of Fibonacci semigroup, Discrete Math., 122, 263-267 (1993) · Zbl 0811.20051
[14] Restivo, A., Permutation properties and the Fibonacci semigroup, (Semigroup Forum, 38 (1989)), 337-345 · Zbl 0663.20063
[15] Séébold, P., Fibonacci morphisms and Sturmian words, Theoret. Comput. Sci., 88, 365-384 (1991) · Zbl 0737.68068
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.