Reconstructing Words from a σ-palindromic Language

We consider words on a finite alphabet Sigma and study the structure of its sigma- palindromes, i.e. words omega satisfying omega = sigma((omega) over tilde) for some involution sigma on the alphabet. We provide algorithms for the computation of sigma-lacunas in omega, that is the positions where the longest sigma-palindromic suffix is not uni-occurrent. The sigma-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 sigma-palindromes is decidable.