Uniformly bounded duplication languages

AbstractWe consider a new type of language defined by a word through iterative factor duplications, inspired by the process of tandem repeats production in the evolution of DNA. We investigate the effect of restricting the factor length to a constant. We prove that all these languages are regular, any word has a unique uniformly bounded duplication root, and show how this root can be computed in linear time and memory. We also address the problem of computing the uniformly bounded duplication distance between two words