On some problems related to palindrome closure

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 $\vartheta$ is an involutory antimorphism of $A^{*}$, then both $\vartheta$-palindromic closures of any factor of a $\vartheta$-standard word are also factors of some $\vartheta$-standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting from a nonempty word. We prove that pseudostandard words with seed are morphic images of standard episturmian words. Moreover, for any given pseudostandard word $s$ with seed, there exists an integer $N$ such that for any $n\geq N$, $s$ has at most one right (resp. left) special factor of length $n$.

Publication
RAIRO - Theoretical Informatics and Applications