×

A characterization of fine words over a finite alphabet. (English) Zbl 1133.68065

Summary: To any infinite word \(\mathbf t\) over a finite alphabet \(\mathcal A\) we can associate two infinite words \(\min (\mathbf t)\) and \(\max (\mathbf t)\) such that any prefix of \(\min (\mathbf t)\) (resp. \(\max (\mathbf t)\)) is the lexicographically smallest (resp. greatest) amongst the factors of \(\mathbf t\) of the same length. We say that an infinite word \(\mathbf t\) over \(\mathcal A\) is fine if there exists an infinite word \(\mathbf s\) such that, for any lexicographic order, \(\min (\mathbf t) = a \mathbf s\) where \(a = \min (\mathcal A)\). In this paper, we characterize fine words; specifically, we prove that an infinite word \(\mathbf t\) is fine if and only if \(\mathbf t\) is either a strict episturmian word or a strict “skew episturmian word”. This characterization generalizes a recent result of G. Pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) Sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) Sturmian.

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] J.-P. Allouche, A. Glen, Extremal properties of (epi)sturmian sequences and distribution modulo 1 (in preparation) · Zbl 1254.68192
[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] de Luca, A., Sturmian words: structure, combinatorics and their arithmetics, Theoret. comput. sci., 183, 45-82, (1997) · Zbl 0911.68098
[4] 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
[5] Glen, A., Powers in a class of \(\mathcal{A}\)-strict standard Episturmian words, Theoret. comput. sci., 380, 330-354, (2007) · Zbl 1119.68140
[6] A. Glen, On Sturmian and episturmian words, and related topics, Ph.D. Thesis, The University of Adelaide, Australia. http://thesis.library.adelaide.edu.au/public/adt-SUA20060426.164255/index.html, April 2006
[7] Glen, A.; Justin, J.; Pirillo, G., Characterizations of finite and infinite Episturmian words via lexicographic orderings, European J. combin., 29, 45-58, (2007) · Zbl 1131.68076
[8] Eddie Godelle, Automorphismes de groupes libres, tresses et morphismes épisturmiens, preprint. http://hal.archives-ouvertes.fr/hal-00022410/en/, 2006
[9] Justin, J.; Pirillo, G., Episturmian words and Episturmian morphisms, Theoret. comput. sci., 276, 281-313, (2002) · Zbl 1002.68116
[10] Justin, J.; Pirillo, G., On a characteristic property of arnoux – rauzy sequences, Theor. inform. appl., 36, 385-388, (2002) · Zbl 1060.68094
[11] Justin, J.; Pirillo, G., Episturmian words: shifts, morphisms and numeration systems, Internat. J. found. comput. sci., 15, 329-348, (2004) · Zbl 1067.68115
[12] Justin, J.; Vuillon, L., Return words in sturmian and Episturmian words, Theor. inform. appl., 34, 343-356, (2000) · Zbl 0987.68055
[13] Morse, M.; Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories, Amer. J. math., 62, 1-42, (1940) · JFM 66.0188.03
[14] Pirillo, G., Inequalities characterizing standard sturmian and Episturmian words, Theoret. comput. sci., 341, 276-292, (2005) · Zbl 1077.68085
[15] G. Pirillo, Morse and Hedlund’s skew Sturmian words revisited, Ann. Comb. (in press) · Zbl 1189.68089
[16] Richomme, G., Conjugacy and Episturmian morphisms, Theoret. comput. sci., 302, 1-34, (2003) · Zbl 1044.68142
[17] Risley, R.N.; Zamboni, L.Q., A generalization of Sturmian sequences: combinatorial structure and transcendence, Acta arith., 95, 167-184, (2000) · Zbl 0953.11007
[18] Wen, Z.-W.; Zhang, Y., Some remarks on invertible substitutions on three letter alphabet, Chinese sci. bull., 44, 1755-1760, (1999) · Zbl 1040.20504
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.