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
Published in
Journal of Computer and System SciencesVolume
101Pages
42 - 67Publisher
ElsevierVersion
- SMUR (Submitted Manuscript Under Review)
Rights holder
© ElsevierPublisher statement
This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/Acceptance date
2018-10-30Publication date
2018-11-20Notes
This is a pre-print of an article submitted to the Journal of Computer and System Sciences, it is in closed access.ISSN
0022-0000eISSN
1090-2724Publisher version
Language
- en