License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2019.1
URN: urn:nbn:de:0030-drops-104727
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10472/
Go to the corresponding LIPIcs Volume Portal

Gawrychowski, Pawel

How to Exploit Periodicity (Invited Talk)

pdf-format:
LIPIcs-CPM-2019-1.pdf (0.2 MB)

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 non-repetitive, 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:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Nadia Pisanti and Solon P. Pissis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10472},
  URN =		{urn:nbn:de:0030-drops-104727},
  doi =		{10.4230/LIPIcs.CPM.2019.1},
  annote =	{Keywords: periodicity, pattern matching, Hamming distance}
}

Keywords: periodicity, pattern matching, Hamming distance
Collection: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Issue Date: 2019
Date of publication: 06.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI