×

On different generalizations of episturmian words. (English) Zbl 1136.68045

Summary: We study some classes of infinite words generalizing episturmian words, and analyse the relations occurring among such classes. In each case, the reversal operator \(R\) is replaced by an arbitrary involutory antimorphism \(\vartheta\) of the free monoid \(A^{*}\). In particular, we define the class of \(\vartheta\)-words with seed, whose “standard” elements (\(\vartheta\)-standard words with seed) are constructed by an iterative \(\vartheta\)-palindrome closure process, starting from a finite word \(u_{0}\) called the seed. When the seed is empty, one obtains \(\vartheta\)-words; episturmian words are exactly the \(R\)-words. One of the main theorems of the paper characterizes \(\vartheta\)-words with seed as infinite words closed under \(\vartheta\) and having at most one left special factor of each length \(n\geq N\) (where \(N\) is some nonnegative integer depending on the word). When \(N=0\) we call such words \(\vartheta\)-episturmian. Further results on the structure of \(\vartheta\)-episturmian words are proved. In particular, some relationships between \(\vartheta\)-words (with or without seed) and \(\vartheta\)-episturmian words are shown.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anne, V.; Zamboni, L. Q.; Zorca, I., Palindromes and pseudo-palindromes in episturmian and pseudo-palindromic infinite words, (Brlek, S.; Reutenauer, C., Words 2005, Publications du LaCIM, vol. 36 (2005)), 91-100
[2] M. Bucci, A. de Luca, A. De Luca, L.Q. Zamboni, On some problems related to palindrome closure, Theoretical Informatics and Applications, 2008 (in press); M. Bucci, A. de Luca, A. De Luca, L.Q. Zamboni, On some problems related to palindrome closure, Theoretical Informatics and Applications, 2008 (in press) · Zbl 1155.68061
[3] de Luca, A.; De Luca, A., Pseudopalindrome closure operators in free monoids, Theoretical Computer Science, 362, 282-300 (2006) · Zbl 1101.68073
[4] Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy, Theoretical Computer Science, 255, 539-553 (2001) · Zbl 0981.68126
[5] Fischler, S., Palindromic prefixes and episturmian words, Journal of Combinatorial Theory, Series A, 113, 1281-1304 (2006) · Zbl 1109.68082
[6] Justin, J.; Pirillo, G., Episturmian words and episturmian morphisms, Theoretical Computer Science, 276, 281-313 (2002) · Zbl 1002.68116
[7] Kari, L.; Konstantinidis, S.; Sosík, P.; Thierrin, G., On hairpin-free words and languages, (De Felice, C.; Restivo, A., Developments in Language Theory. Developments in Language Theory, LNCS, vol. 3572 (2005), Springer), 296-307 · Zbl 1132.68451
[8] Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge University Press · Zbl 1001.68093
[9] Lothaire, M., Applied Combinatorics on Words (2005), Cambridge University Press · Zbl 1133.68067
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.