On some problems related to palindrome closure

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

doi:10.1051/ita:2007064

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

¹ Department of Mathematics, PO Box 311430, University of North Texas. Denton TX, USA;

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 4, pp. 679-700

Voir la notice de l'article provenant de la source Numdam

Résumé

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.

MR Zbl

DOI : 10.1051/ita:2007064

Classification : 68R15
Keywords: palindromes, palindrome closures, sturmian and episturmian words, involutory antimorphisms, pseudopalindromes, pseudostandard words

Affiliations des auteurs :

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

¹ Department of Mathematics, PO Box 311430, University of North Texas. Denton TX, USA;

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :

Parcourir par

Geodesic

Parcourir par