Gawrychowski, Pawel
How to Exploit Periodicity (Invited Talk)
Abstract
Periodicity is a fundamental combinatorial property of strings. We say that p is a period of a string s[1..n] when s[i]=s[i+p] for every i such that both s[i] and s[i+p] are defined. While this notion is interesting on its own, it can be often used as a tool for designing efficient algorithms. At a high level, such algorithms often operate differently depending on whether a given string does or does not have a small period, where small usually means smaller than half of its length (or, say, quarter). In other words, we design an algorithm that is efficient if the given string is repetitive, and another algorithm that is efficient if the given string is nonrepetitive, in every case carefully exploiting either the periodicity or the fact that input looks sufficiently "random", and then choose the appropriate algorithm depending on the input. Of course, in some cases, one needs to proceed in a more complex manner, for example by classifying the whole string look at its substrings and process each of them differently depending on its structure.
I will survey results, mostly connected to different version of pattern matching, that are based on this paradigm. This will include the recent generalization of periodicity that can be applied in approximate pattern matching, and some examples of how the notion of periodicity can be applied to design a better data structure.
BibTeX  Entry
@InProceedings{gawrychowski:LIPIcs:2019:10472,
author = {Pawel Gawrychowski},
title = {{How to Exploit Periodicity (Invited Talk)}},
booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
pages = {1:11:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771030},
ISSN = {18688969},
year = {2019},
volume = {128},
editor = {Nadia Pisanti and Solon P. Pissis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10472},
URN = {urn:nbn:de:0030drops104727},
doi = {10.4230/LIPIcs.CPM.2019.1},
annote = {Keywords: periodicity, pattern matching, Hamming distance}
}
06.06.2019
Keywords: 

periodicity, pattern matching, Hamming distance 
Seminar: 

30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Issue date: 

2019 
Date of publication: 

06.06.2019 