Reconstructing Words from a σ-palindromic Language

被引：0
|
作者：
Brlek, Srecko [1 ]
Lafreniere, Nadia [1 ]
机构：
[1] Univ Quebec, Lab Combinatoire & Informat Math, Montreal, PQ H3C 3P8, Canada
来源：
FUNDAMENTA INFORMATICAE | 2014年 / 135卷 / 1-2期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Generalized palindromes; complexity; sigma-palindromic lacunas; sigma-palindromic defect; COMBINATORIAL PROPERTIES; OPERATORS;
D O I：
10.3233/FI-2014-1112
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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.
引用
收藏
页码：59 / 72
页数：14
相关论文
共 50 条
12345