Affiliations: Laboratoire de Combinatoire et d'Informatique Mathématique, Université du Québec ă Montréal, C. P. 8888 Succursale “Centre-Ville”, Montréal (QC), Canada H3C 3P8. [email protected], [email protected]
Note: [] Address for correspondence: Laboratoire de Combinatoire et d'Informatique Mathématique, Université du Québec ă Montréal, C. P. 8888 Succursale “Centre-Ville”, Montréal (QC), CANADA H3C 3P8
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.
