In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if is an involutory antimorphism of , then the right and left -palindromic closures of any factor of a -standard word are also factors of some -standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting from a nonempty word. We show that pseudostandard words with seed are morphic images of standard episturmian words. Moreover, we prove that for any given pseudostandard word with seed, all sufficiently long left special factors of are prefixes of it.
Mots clés : palindromes, palindrome closures, sturmian and episturmian words, involutory antimorphisms, pseudopalindromes, pseudostandard words
@article{ITA_2008__42_4_679_0,
author = {Bucci, Michelangelo and Luca, Aldo de and Luca, Alessandro De and Zamboni, Luca Q.},
title = {On some problems related to palindrome closure},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {679--700},
publisher = {EDP-Sciences},
volume = {42},
number = {4},
year = {2008},
doi = {10.1051/ita:2007064},
mrnumber = {2458701},
zbl = {1155.68061},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007064/}
}
TY - JOUR AU - Bucci, Michelangelo AU - Luca, Aldo de AU - Luca, Alessandro De AU - Zamboni, Luca Q. TI - On some problems related to palindrome closure JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2008 SP - 679 EP - 700 VL - 42 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2007064/ DO - 10.1051/ita:2007064 LA - en ID - ITA_2008__42_4_679_0 ER -
%0 Journal Article %A Bucci, Michelangelo %A Luca, Aldo de %A Luca, Alessandro De %A Zamboni, Luca Q. %T On some problems related to palindrome closure %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 679-700 %V 42 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2007064/ %R 10.1051/ita:2007064 %G en %F ITA_2008__42_4_679_0
Bucci, Michelangelo; Luca, Aldo de; Luca, Alessandro De; Zamboni, Luca Q. On some problems related to palindrome closure. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 4, pp. 679-700. doi : 10.1051/ita:2007064. http://www.numdam.org/articles/10.1051/ita:2007064/
[1] , and , Palindromes and pseudo-palindromes in episturmian and pseudo-palindromic infinite words, in Words 2005, number 36 in Publications du LaCIM, edited by S. Brlek and C. Reutenauer (2005) 91-100.
[2] and , Theory of Codes. Academic Press (1985). | MR | Zbl
[3] and , Sturmian words, in Algebraic Combinatorics on Words, edited by M. Lothaire. Cambridge University Press, Cambridge UK (2002). Chapter 2. | MR
[4] , , and , On different generalizations of episturmian words. Theor. Comput. Sci., to appear. | MR | Zbl
[5] , Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci. 183 (1997) 45-82. | MR | Zbl
[6] and , Pseudopalindrome closure operators in free monoids. Theor. Comput. Sci. 362 (2006) 282-300. | MR | Zbl
[7] , and , Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci. 255 (2001) 539-553. | MR | Zbl
[8] , A characterization of substitutive sequences using return words. Discrete Mathematics 179 (1998) 89-101. | MR | Zbl
[9] , Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl. 39 (2005) 207-215. | Numdam | MR | Zbl
[10] and , Episturmian words and episturmian morphisms. Theor. Comput. Sci. 276 (2002) 281-313. | MR | Zbl
[11] and , Watson-Crick conjugate and commutative words. Preliminary proceedings of DNA Computing 13, Memphis, USA. M.Garzon, H.Yan, Eds. (2007) 75-87. | Zbl
Cité par Sources :
