2009/11/11 by Chiniforooshan, Ehsan, Kari, Lila, Xu, Zhi · 1 citation
#Data Structures and Algorithms (cs.DS) #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #J.3
paper · doi:10.48550/arxiv.0911.2233
Repetition avoidance has been studied since Thue's work. In this paper, we considered another type of repetition, which is called pseudo-power. This concept is inspired by Watson-Crick complementarity in DNA sequence and is defined over an antimorphic involution ϕ. We first classify the alphabet Σ and the antimorphic involution ϕ, under which there exists sufficiently long pseudo-kth-power-free words. Then we present algorithms to test whether a finite word w is pseudo-kth-power-free.