Pseudopalindrome closure operators in free monoids

Abstract

We consider involutory antimorphisms $\vartheta$ of a free monoid $A^{*}$ and their fixed points, called $\vartheta$-palindromes or pseudopalindromes. A $\vartheta$-palindrome reduces to a usual palindrome when $\vartheta$ is the reversal operator. For any word $w\in A^{*}$ the right (resp. left) $\vartheta$-palindrome closure of $w$ is the shortest $\vartheta$-palindrome having $w$ as a prefix (resp. suffix). We prove some results relating $\vartheta$-palindrome closure operators with periodicity and conjugacy, and derive some interesting closure properties for the languages of finite Sturmian and episturmian words. In particular, a finite word $w$ is Sturmian if and only if both its palindromic closures are so. Moreover, in such a case, both the palindromic closures of $w$ share the same minimal period of $w$. A new characterization of finite Sturmian words follows, in terms of periodicity and special factors of their palindromic closures. Some weaker results can be extended to the episturmian case. By using the right $\vartheta$-palindrome closure, we extend the construction of standard episturmian words via directive words. In this way one obtains a family of infinite words, called $\vartheta$-standard words, which are morphic images of episturmian words, as well as a wider family of infinite words including the Thue-Morse word on two symbols.

Publication
Theoretical Computer Science