Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.257
URN: urn:nbn:de:0030-drops-39394
URL: https://drops.dagstuhl.de/opus/volltexte/2013/3939/
Gawrychowski, Pawel ; Manea, Florin ; Mercas, Robert ; Nowotka, Dirk ; Tiseanu, Catalin
Finding Pseudo-repetitions
| pdf-format: |
|
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 pseudo-repetition and find all the pseudo-repetitive factors of a word.
BibTeX - Entry
@InProceedings{gawrychowski_et_al:LIPIcs:2013:3939,
author = {Pawel Gawrychowski and Florin Manea and Robert Mercas and Dirk Nowotka and Catalin Tiseanu},
title = {{Finding Pseudo-repetitions}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {257--268},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-50-7},
ISSN = {1868-8969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3939},
URN = {urn:nbn:de:0030-drops-39394},
doi = {10.4230/LIPIcs.STACS.2013.257},
annote = {Keywords: Stringology, Pattern matching, Repetition, Pseudo-repetition}
}
| Keywords: | Stringology, Pattern matching, Repetition, Pseudo-repetition | |
| Seminar: | 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) | |
| Issue date: | 2013 | |
| Date of publication: | 26.02.2013 |
