×

Characterizations of finite and infinite episturmian words via lexicographic orderings. (English) Zbl 1131.68076

Summary: We characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

References:

[1] Allouche, J.-P.; Shallit, J., Automatic sequences: theory, applications, generalizations, (2003), Cambridge University Press UK · Zbl 1086.11015
[2] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2 n + 1\), Bull. soc. math. France, 119, 199-215, (1991) · Zbl 0789.28011
[3] Berstel, J.; Séébold, P., Sturmian words, (), 45-110 · Zbl 0883.68104
[4] de Luca, A., Sturmian words: structure, combinatorics and their arithmetics, Theoret. comput. sci., 183, 45-82, (1997) · Zbl 0911.68098
[5] 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
[6] Droubay, X.; Pirillo, G., Palindromes and Sturmian words, Theoret. comput. sci., 223, 73-85, (1999) · Zbl 0930.68116
[7] Gan, S., Sturmian sequences and the lexicographic world, Proc. amer. math. soc., 129, 1445-1451, (2001) · Zbl 1004.37009
[8] A. Glen, Powers in a class of \(\mathcal{A}\)-strict standard episturmian words, in: 5th International Conference on Words, Université du Québec à Montréal, Publications du LaCIM 36 (2005) 249-263. Theoret. Comput. Sci., in press (doi:10.1016/j.tcs.2007.03.023)
[9] A. Glen, A characterization of fine words over a finite alphabet, in: International School and Conference on Combinatorics, Automata and Number Theory, Université de Liége, Belgium, 2006, p. 9
[10] Heinis, A.; Tijdeman, R., Characterisation of asymptotically Sturmian sequences, Publ. math. debrecen, 56, 3-4, 415-430, (2000) · Zbl 0961.11004
[11] Jenkinson, O.; Zamboni, L.Q., Characterisations of balanced words via orderings, Theoret. comput. sci., 310, 247-271, (2004) · Zbl 1071.68090
[12] Justin, J.; Pirillo, G., Decimations and Sturmian words, Theor. inform. appl., 31, 3, 271-290, (1997) · Zbl 0889.68090
[13] Justin, J.; Pirillo, G., Episturmian words and Episturmian morphisms, Theoret. comput. sci., 276, 281-313, (2002) · Zbl 1002.68116
[14] Justin, J.; Pirillo, G., On a characteristic property of arnoux-Rauzy sequences, Theor. inform. appl., 36, 4, 385-388, (2002) · Zbl 1060.68094
[15] Justin, J.; Pirillo, G., Episturmian words: shifts, morphisms and numeration systems, Internat. J. found. comput. sci., 15, 2, 329-348, (2004) · Zbl 1067.68115
[16] Justin, J.; Vuillon, L., Return words in sturmian and Episturmian words, Theor. inform. appl., 34, 5, 343-356, (2000) · Zbl 0987.68055
[17] Mignosi, F.; Zamboni, L.Q., On the number of arnoux-Rauzy words, Acta arith., 101, 2, 121-129, (2002) · Zbl 1005.68117
[18] Morse, M.; Hedlund, G.A., Symbolic dynamics II: Sturmian trajectories, Amer. J. math., 62, 1-42, (1940) · JFM 66.0188.03
[19] Pirillo, G., A new characteristic property of the palindrome prefixes of a standard Sturmian word, Sém. lothar. combin., 43, (1999), pp. 3 · Zbl 0941.68101
[20] Pirillo, G., Inequalities characterizing standard sturmian and Episturmian words, Theoret. comput. sci., 341, 1-3, 276-292, (2005) · Zbl 1077.68085
[21] G. Pirillo, Morse and Hedlund’s skew Sturmian words revisited, Ann. Comb. (in press) · Zbl 1189.68089
[22] Pytheas Fogg, N., ()
[23] Richomme, G., Conjugacy and Episturmian morphisms, Theoret. comput. sci., 302, 1-34, (2003) · Zbl 1044.68142
[24] Risley, R.N.; Zamboni, L.Q., A generalization of Sturmian sequences: combinatorial structure and transcendence, Acta arith., 95, 2, 167-184, (2000) · Zbl 0953.11007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.