File(s) under permanent embargo
Reason: This item is currently closed access.
Hide and seek with repetitions
journal contributionposted on 07.03.2017, 11:21 by Pawel Gawrychowski, Florin Manea, Robert MercasRobert Mercas, Dirk Nowotka
Pseudo-repetitions are a natural generalization of the classical notion of repetitions in sequences: they are the repeated concatenation of a word and its encoding under a certain morphism or antimorphism. Thus, such occurrences can be regarded as hidden repetitive structures of, or within, a word. We solve fundamental algorithmic questions on pseudo-repetitions by application of insightful combinatorial results on words. More precisely, we efficiently decide whether a word is a pseudo-repetition and find all the pseudo-repetitive factors of a word. We also approach the problem of deciding whether there exists an anti-/morphism for which a word is a pseudo-repetition. We show that some variants of this later problem are efficiently solvable, while some others are NPcomplete.
- Computer Science