Reconstructing Words from a σ-palindromic Language

We consider words on a finite alphabet Σ and study the structure of its σ-palindromes, i.e. words w satisfying ω = σ( ω) for some involution σ on the alphabet. We provide algorithms for the computation of σ-lacunas in ω, 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.