On some problems related to palindrome closure

Michelangelo Bucci; Aldo de Luca; Alessandro De Luca; Luca Q. Zamboni

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 4, page 679-700
  • ISSN: 0988-3754

Abstract

top
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 A*, 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 s with seed, all sufficiently long left special factors of s are prefixes of it.

How to cite

top

Bucci, Michelangelo, et al. "On some problems related to palindrome closure." RAIRO - Theoretical Informatics and Applications 42.4 (2008): 679-700. <http://eudml.org/doc/250275>.

@article{Bucci2008,
abstract = { 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 A*, 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 s with seed, all sufficiently long left special factors of s are prefixes of it. },
author = {Bucci, Michelangelo, de Luca, Aldo, De Luca, Alessandro, Zamboni, Luca Q.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Palindromes; palindrome closures; Sturmian and episturmian words; involutory antimorphisms; pseudopalindromes; pseudostandard words.; palindromes; pseudostandard words},
language = {eng},
month = {1},
number = {4},
pages = {679-700},
publisher = {EDP Sciences},
title = {On some problems related to palindrome closure},
url = {http://eudml.org/doc/250275},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Bucci, Michelangelo
AU - de Luca, Aldo
AU - De Luca, Alessandro
AU - Zamboni, Luca Q.
TI - On some problems related to palindrome closure
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/1//
PB - EDP Sciences
VL - 42
IS - 4
SP - 679
EP - 700
AB - 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 A*, 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 s with seed, all sufficiently long left special factors of s are prefixes of it.
LA - eng
KW - Palindromes; palindrome closures; Sturmian and episturmian words; involutory antimorphisms; pseudopalindromes; pseudostandard words.; palindromes; pseudostandard words
UR - http://eudml.org/doc/250275
ER -

References

top
  1. V. Anne, L.Q. Zamboni and I. Zorca, 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. J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985).  
  3. J. Berstel and P. Séébold, Sturmian words, in Algebraic Combinatorics on Words, edited by M. Lothaire. Cambridge University Press, Cambridge UK (2002). Chapter 2.  
  4. M. Bucci, A. de Luca, A. De Luca and L.Q. Zamboni, On different generalizations of episturmian words. Theor. Comput. Sci., to appear.  
  5. A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci.183 (1997) 45–82.  
  6. A. de Luca and A. De Luca, Pseudopalindrome closure operators in free monoids. Theor. Comput. Sci.362 (2006) 282–300.  
  7. X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci.255 (2001) 539–553.  
  8. F. Durand, A characterization of substitutive sequences using return words. Discrete Mathematics179 (1998) 89–101.  
  9. J. Justin, Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl.39 (2005) 207–215.  
  10. J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theor. Comput. Sci.276 (2002) 281–313.  
  11. L. Kari and K. Mahalingam, Watson-Crick conjugate and commutative words. Preliminary proceedings of DNA Computing 13, Memphis, USA. M.Garzon, H.Yan, Eds. (2007) 75–87.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.