Finding Pseudo-repetitions.

Gawrychowski, Pawel, Manea, Florin, Mercas, Robert, Nowotka, Dirk and Tiseanu, Catalin (2013) Finding Pseudo-repetitions. LIPIcs - Leibniz International Proceedings in Informatics, 20 . pp. 257-268. DOI 10.4230/LIPIcs.STACS.2013.257.

[thumbnail of 27.pdf]
Preview
Text
27.pdf - Published Version
Available under License Creative Commons Attribution No Derivatives.

Download (617kB) | Preview

Supplementary data:

Abstract

Pseudo-repetitions are a natural generalization of the classical notion of repetitions in sequences.
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 pseudorepetition and find all the pseudo-repetitive factors of a word.

Document Type: Article
Keywords: Stringology, Pattern matching, Repetition, Pseudo-repetition
Research affiliation:
Kiel University
Refereed: Yes
Open Access Journal?: Yes
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Date Deposited: 16 Apr 2013 14:31
Last Modified: 23 Sep 2019 16:38
URI: https://oceanrep.geomar.de/id/eprint/20750

Actions (login required)

View Item View Item