Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T02:36:39.731Z Has data issue: false hasContentIssue false
  • English
  • Français

On some problems related to palindrome closure

Published online by Cambridge University Press:  15 January 2008

Michelangelo Bucci ,
Aldo de Luca ,
Alessandro De Luca  and
Luca Q. Zamboni
Michelangelo Bucci
Affiliation:
Dipartimento di Matematica e Applicazioni “R. Caccioppoli”, Università degli Studi di Napoli Federico II. Via Cintia, Monte S. Angelo, I-80126 Napoli, Italy; [email protected]; [email protected]; [email protected]
Aldo de Luca
Affiliation:
Dipartimento di Matematica e Applicazioni “R. Caccioppoli”, Università degli Studi di Napoli Federico II. Via Cintia, Monte S. Angelo, I-80126 Napoli, Italy; [email protected]; [email protected]; [email protected]
Alessandro De Luca
Affiliation:
Dipartimento di Matematica e Applicazioni “R. Caccioppoli”, Università degli Studi di Napoli Federico II. Via Cintia, Monte S. Angelo, I-80126 Napoli, Italy; [email protected]; [email protected]; [email protected]
Luca Q. Zamboni
Affiliation:
Department of Mathematics, PO Box 311430, University of North Texas. Denton TX, USA; [email protected]
Get access

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.

Keywords

Palindromespalindrome closuresSturmian and episturmian wordsinvolutory antimorphismspseudopalindromespseudostandard words.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 4: Fibonacci words , October 2008 , pp. 679 - 700
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.
J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985).
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.
M. Bucci, A. de Luca, A. De Luca and L.Q. Zamboni, On different generalizations of episturmian words. Theor. Comput. Sci., to appear.
de Luca, A., Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci. 183 (1997) 45–82. CrossRef
de Luca, A. and De Luca, A., Pseudopalindrome closure operators in free monoids. Theor. Comput. Sci. 362 (2006) 282–300. CrossRef
Droubay, X., Justin, J. and Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci. 255 (2001) 539–553. CrossRef
Durand, F., A characterization of substitutive sequences using return words. Discrete Mathematics 179 (1998) 89–101. CrossRef
Justin, J., Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl. 39 (2005) 207–215. CrossRef
Justin, J. and Pirillo, G., Episturmian words and episturmian morphisms. Theor. Comput. Sci. 276 (2002) 281–313. CrossRef
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.