Cyclic complexity of words. (English) Zbl 1425.68326
Csuhaj-Varjú, Erzsébet (ed.) et al., Mathematical foundations of computer science 2014. 39th international symposium, MFCS 2014, Budapest, Hungary, August 25–29, 2014. Proceedings, Part I. Berlin: Springer. Lect. Notes Comput. Sci. 8634, 159-170 (2014).
Summary: We introduce and study a new complexity function on words, which we call cyclic complexity, which counts the number of conjugacy classes of factors of each given length. We extend the famous Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words having different slopes. More precisely, we prove that if \(x\) is a Sturmian word and \(y\) is a word having the same cyclic complexity of \(x\) then \(y\) is Sturmian and, up to renaming letters, it has the same language of factors of \(x\).
For the entire collection see [Zbl 1294.68016].
For the entire collection see [Zbl 1294.68016].
MSC:
| 68R15 | Combinatorics on words |
References:
| [1] | Berstel, J.; Bozapalidis, S.; Rahonis, G., Sturmian and episturmian words (a survey of some recent results), Algebraic Informatics, 23-47 (2007), Heidelberg: Springer, Heidelberg · Zbl 1149.68065 · doi:10.1007/978-3-540-75414-5_2 |
| [2] | Berstel, J., Lauve, A., Reutenauer, C., Saliola, F.: Combinatorics on Words: Christoffel Words and Repetition in Words. CRM monograph series, vol. 27. American Mathematical Society (2008) · Zbl 1161.68043 |
| [3] | Blanchet-Sadri, F.; Fox, N.; Béal, M.-P.; Carton, O., On the asymptotic abelian complexity of morphic words, Developments in Language Theory, 94-105 (2013), Heidelberg: Springer, Heidelberg · Zbl 1381.68228 · doi:10.1007/978-3-642-38771-5_10 |
| [4] | Borel, J.-P.; Reutenauer, C., On Christoffel classes, RAIRO Theor. Inform. Appl., 40, 1, 15-27 (2006) · Zbl 1085.68116 · doi:10.1051/ita:2005038 |
| [5] | Brlek, S.; Hamel, S.; Nivat, M.; Reutenauer, C., On the palindromic complexity of infinite words, Internat. J. Found. Comput. Sci., 15, 2, 293-306 (2004) · Zbl 1067.68113 |
| [6] | Jenkinson, O.; Zamboni, L. Q., Characterisations of balanced words via orderings, Theoret. Comput. Sci., 310, 1-3, 247-271 (2004) · Zbl 1071.68090 · doi:10.1016/S0304-3975(03)00397-9 |
| [7] | Kamae, T.; Zamboni, L., Maximal pattern complexity for discrete systems, Ergodic Theory Dynam. Systems, 22, 4, 1201-1214 (2002) · Zbl 1014.37003 |
| [8] | Karhumäki, J.; Saarela, A.; Zamboni, L. Q., On a generalization of abelian equivalence and complexity of infinite words, J. Comb. Theory, Ser. A, 120, 8, 2189-2206 (2013) · Zbl 1278.05009 · doi:10.1016/j.jcta.2013.08.008 |
| [9] | Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge: Cambridge University Press, Cambridge · Zbl 1001.68093 · doi:10.1017/CBO9781107326019 |
| [10] | Madill, B.; Rampersad, N., The abelian complexity of the paperfolding word, Discrete Math., 313, 7, 831-838 (2013) · Zbl 1260.05002 · doi:10.1016/j.disc.2013.01.005 |
| [11] | Mantaci, S.; Restivo, A.; Sciortino, M., Burrows-Wheeler transform and Sturmian words, Inform. Process. Lett., 86, 5, 241-246 (2003) · Zbl 1162.68511 · doi:10.1016/S0020-0190(02)00512-4 |
| [12] | Mignosi, F.; Restivo, A., A new complexity function for words based on periodicity, Internat. J. Algebra Comput., 23, 4, 963-988 (2013) · Zbl 1269.68077 · doi:10.1142/S0218196713400080 |
| [13] | Mignosi, F.; Restivo, A.; Sciortino, M., Words and forbidden factors, Theoret. Comput. Sci., 273, 1-2, 99-117 (2002) · Zbl 0997.68093 · doi:10.1016/S0304-3975(00)00436-9 |
| [14] | Morse, M.; Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, 1-42 (1938) · JFM 66.0188.03 · doi:10.2307/2371264 |
| [15] | Fogg, N.P.: Substitutions in Dynamics, Arithmetics and Combinatorics. Lecture Notes in Math., vol. 1794. Springer (2002) · Zbl 1014.11015 |
| [16] | Richomme, G.; Saari, K.; Zamboni, L., Abelian complexity of minimal subshifts, J. Lond. Math. Soc., 83, 1, 79-95 (2011) · Zbl 1211.68300 · doi:10.1112/jlms/jdq063 |
| [17] | Rigo, M.; Salimov, P.; Karhumäki, J.; Lepistö, A.; Zamboni, L., Another generalization of abelian equivalence: Binomial complexity of infinite words, Combinatorics on Words, 217-228 (2013), Heidelberg: Springer, Heidelberg · Zbl 1325.68175 · doi:10.1007/978-3-642-40579-2_23 |
| [18] | Saarela, A., Ultimately constant abelian complexity of infinite words, J. Autom. Lang. Comb., 14, 3-4, 255-258 (2010) · Zbl 1205.68274 |
| [19] | Turek, O., Abelian complexity and abelian co-decomposition, Theoret. Comput. Sci., 469, 77-91 (2013) · Zbl 1285.68139 · doi:10.1016/j.tcs.2012.10.034 |
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.
