File(s) under permanent embargo

Reason: This item is currently closed access.

Hide and seek with repetitions

journal contribution
posted 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.

History

School

  • Science

Department

  • Computer Science

Published in

Journal of Computer and System Sciences

Volume

101

Pages

42 - 67

Publisher

Elsevier

Version

SMUR (Submitted Manuscript Under Review)

Rights holder

© Elsevier

Publisher 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

30/10/2018

Publication date

2018-11-20

Notes

This is a pre-print of an article submitted to the Journal of Computer and System Sciences, it is in closed access.

ISSN

0022-0000

eISSN

1090-2724

Language

en