Rich, Sturmian, and trapezoidal words. (English) Zbl 1153.68045
Summary: We explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced by the second and third authors together with J. Justin and S. Widmer, constitute a new class of finite and infinite words characterized by having the maximal number of palindromic factors. Every finite Sturmian word is rich, but not conversely. Trapezoidal words were first introduced by the first author in studying the behavior of the subword complexity of finite Sturmian words. Unfortunately this property does not characterize finite Sturmian words. In this note we show that the only trapezoidal palindromes are Sturmian. More generally we show that Sturmian palindromes can be characterized either in terms of their subword complexity (the trapezoidal property) or in terms of their palindromic complexity. We also obtain a similar characterization of rich palindromes in terms of a relation between palindromic complexity and subword complexity.
MSC:
| 68R15 | Combinatorics on words |
References:
| [1] | Ambrož, P.; Frougny, C.; Masáková, Z.; Pelantová, E., Palindromic complexity of infinite words associated with simple Parry numbers, Ann. Inst. Fourier (Grenoble), 56, 2131-2160 (2006) · Zbl 1121.68089 |
| [2] | Anne, V.; Zamboni, L. Q.; Zorca, I., Palindromes and pseudo-palindromes in episturmian and pseudo-palindromic infinite words, (Brlek, S.; Reutenauer, C., Words 2005. Words 2005, Publications du LACIM, vol. 36 (2005)), 91-100 |
| [3] | Berstel, J.; Séébold, P., (Sturmian Words. Sturmian Words, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, vol. 90 (2002), Cambridge University Press) · Zbl 1001.68093 |
| [4] | M. Bucci, A. De Luca, A. Glen, L.Q. Zamboni, A connection between palindromic and factor complexity using return words, Adv. Appl. Math. (2008), to appear; M. Bucci, A. De Luca, A. Glen, L.Q. Zamboni, A connection between palindromic and factor complexity using return words, Adv. Appl. Math. (2008), to appear · Zbl 1160.68027 |
| [5] | D’Alessandro, F., A combinatorial problem on trapezoidal words, Theoret. Comput. Sci., 273, 11-33 (2002) · Zbl 1050.68113 |
| [6] | de Luca, A., On the combinatorics of finite words, Theoret. Comput. Sci., 218, 13-39 (1999) · Zbl 0916.68119 |
| [7] | de Luca, A.; De Luca, A., Combinatorial properties of Sturmian palindromes, Internat. J. Found. Comput. Sci., 17, 557-574 (2006) · Zbl 1096.68126 |
| [8] | de Luca, A.; De Luca, A., Some characterizations of finite Sturmian words, Theoret. Comput. Sci., 356, 118-125 (2006) · Zbl 1160.68481 |
| [9] | A. De Luca, Private communication; A. De Luca, Private communication |
| [10] | Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci., 255, 539-553 (2001) · Zbl 0981.68126 |
| [11] | Droubay, X.; Pirillo, G., Palindromes and Sturmian words, Theoret. Comput. Sci., 223, 73-85 (1999) · Zbl 0930.68116 |
| [12] | S. Ferenczi, L.Q. Zamboni, Language of \(k\); S. Ferenczi, L.Q. Zamboni, Language of \(k\) · Zbl 1147.37008 |
| [13] | S. Ferenczi, L.Q. Zamboni, Structure of \(k\); S. Ferenczi, L.Q. Zamboni, Structure of \(k\) · Zbl 1225.37003 |
| [14] | A. Glen, J. Justin, S. Widmer, L.Q. Zamboni, Palindromic richness, European J. Combin. (2008), in press (doi:10.1016/j.ejc.2008.04.006; A. Glen, J. Justin, S. Widmer, L.Q. Zamboni, Palindromic richness, European J. Combin. (2008), in press (doi:10.1016/j.ejc.2008.04.006 · Zbl 1169.68040 |
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.
