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.

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 | 1 citation dans Numdam

DOI : 10.1051/ita:2007064

Classification : 68R15
Mots-clés : 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 = {https://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  - https://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 https://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. https://www.numdam.org/articles/10.1051/ita:2007064/

Bibliographie
Cité par

[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). | MR | Zbl

[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. | MR

[4] M. Bucci, A. De Luca, A. De Luca and L.Q. Zamboni, On different generalizations of episturmian words. Theor. Comput. Sci., to appear. | MR | Zbl

[5] A. De Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci. 183 (1997) 45-82. | MR | Zbl

[6] A. De Luca and A. De Luca, Pseudopalindrome closure operators in free monoids. Theor. Comput. Sci. 362 (2006) 282-300. | MR | Zbl

[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. | MR | Zbl

[8] F. Durand, A characterization of substitutive sequences using return words. Discrete Mathematics 179 (1998) 89-101. | MR | Zbl

[9] J. Justin, Episturmian morphisms and a Galois theorem on continued fractions. RAIRO-Theor. Inf. Appl. 39 (2005) 207-215. | Numdam | MR | Zbl

[10] J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theor. Comput. Sci. 276 (2002) 281-313. | MR | Zbl

[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. | Zbl

Florian, Josef; Veselá, Tereza; Dvořáková, Ľubomíra Normalization of ternary generalized pseudostandard words, Theoretical Computer Science, Volume 780 (2019), pp. 29-53 | DOI:10.1016/j.tcs.2019.02.010 | Zbl:1437.68145
Florian, Josef; Dvořáková, L'ubomíra A new estimate on complexity of binary generalized pseudostandard words, Integers, Volume 17 (2017), p. paper | Zbl:1420.68162
Florian, Josef; Dvořáková, L'ubomíra On periodicity of generalized pseudostandard words, The Electronic Journal of Combinatorics, Volume 23 (2016) no. 1, p. research | Zbl:1334.68172
de Luca, Aldo; de Luca, Alessandro A generalized palindromization map in free monoids, Theoretical Computer Science, Volume 454 (2012), pp. 109-128 | DOI:10.1016/j.tcs.2012.01.029 | Zbl:1262.68096
de Luca, Aldo A palindromization map on free monoids, Proceedings of the Steklov Institute of Mathematics, Volume 274 (2011), pp. 124-135 | DOI:10.1134/s0081543811060095 | Zbl:1298.68204
Jamet, D.; Paquin, G.; Richomme, G.; Vuillon, L. On the fixed points of the iterated pseudopalindromic closure operator, Theoretical Computer Science, Volume 412 (2011) no. 27, pp. 2974-2987 | DOI:10.1016/j.tcs.2010.03.018 | Zbl:1220.68077
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro On the number of episturmian palindromes, Theoretical Computer Science, Volume 411 (2010) no. 40-42, pp. 3668-3684 | DOI:10.1016/j.tcs.2010.06.016 | Zbl:1207.68234
Bucci, Michelangelo; De Luca, Alessandro; Glen, Amy; Zamboni, Luca Q. A connection between palindromic and factor complexity using return words, Advances in Applied Mathematics, Volume 42 (2009) no. 1, pp. 60-74 | DOI:10.1016/j.aam.2008.03.005 | Zbl:1160.68027
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro; Zamboni, Luca Q. On $θ$ -episturmian words, European Journal of Combinatorics, Volume 30 (2009) no. 2, pp. 473-479 | DOI:10.1016/j.ejc.2008.04.010 | Zbl:1159.68028
Glen, Amy; Justin, Jacques Episturmian words: a survey, RAIRO. Theoretical Informatics and Applications, Volume 43 (2009) no. 3, pp. 403-442 | DOI:10.1051/ita/2009003 | Zbl:1182.68155
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro Characteristic morphisms of generalized episturmian words, Theoretical Computer Science, Volume 410 (2009) no. 30-32, pp. 2840-2859 | DOI:10.1016/j.tcs.2008.12.001 | Zbl:1173.68047
Tijdeman, R.; Zamboni, L. Q. Fine and Wilf words for any periods. II, Theoretical Computer Science, Volume 410 (2009) no. 30-32, pp. 3027-3034 | DOI:10.1016/j.tcs.2009.02.004 | Zbl:1173.68056
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro On a generalization of standard episturmian morphisms, Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings, Berlin: Springer, 2008, pp. 158-169 | DOI:10.1007/978-3-540-85780-8_12 | Zbl:1159.68027
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro; Zamboni, Luca Q. On different generalizations of episturmian words, Theoretical Computer Science, Volume 393 (2008) no. 1-3, pp. 23-36 | DOI:10.1016/j.tcs.2007.10.043 | Zbl:1136.68045
de Luca, Aldo; De Luca, Alessandro Pseudopalindrome closure operators in free monoids, Theoretical Computer Science, Volume 362 (2006) no. 1-3, pp. 282-300 | DOI:10.1016/j.tcs.2006.07.009 | Zbl:1101.68073

Cité par 15 documents. Sources : zbMATH