File(s) under permanent embargo
Reason: This item is currently closed access.
Hide and seek with repetitions
journal contribution
posted on 2017-03-07, 11:21 authored by Pawel Gawrychowski, Florin Manea, Robert MercasRobert Mercas, Dirk NowotkaPseudo-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.
History
School
- Science
Department
- Computer Science