Abstract
We consider words on a finite alphabet Σ and study the structure of its σ-palindromes, i.e. words w satisfying w = σ($\tilde{w}$) for some involution σ on the alphabet. We provide algorithms for the computation of σ-lacunas in w, that is the positions where the longest σ-palindromic suffix is not uni-occurrent. The σ-palindromic defect is explicitly computed for Sturmian words and the Thue-Morse word. Finally, the problem of reconstructing words from a given fixed set of σ-palindromes is decidable.
Get full access to this article
View all access options for this article.