Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2021.1
URN: urn:nbn:de:0030-drops-139523
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13952/
Bannai, Hideo
Repetitions in Strings: A "Constant" Problem (Invited Talk)
| pdf-format: |
|
Abstract
Repeating structures in strings is one of the most fundamental characteristics of strings, and has been an important topic in the field of combinatorics on words and combinatorial pattern matching since their beginnings. In this talk, I will focus on squares and maximal repetitions and review the "runs" theorem [Hideo Bannai et al., 2017] as well as related results (e.g. [Aviezri S. Fraenkel and Jamie Simpson, 1998; Yuta Fujishige et al., 2017; Ryo Sugahara et al., 2019; Philip Bille et al., 2020; Hideo Bannai et al., 2020; Jonas Ellert and Johannes Fischer, 2021]) which address the two main questions: how many of them can be contained in a string of given length, and algorithms for computing them.
BibTeX - Entry
@InProceedings{bannai:LIPIcs.CPM.2021.1,
author = {Bannai, Hideo},
title = {{Repetitions in Strings: A "Constant" Problem}},
booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-186-3},
ISSN = {1868-8969},
year = {2021},
volume = {191},
editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13952},
URN = {urn:nbn:de:0030-drops-139523},
doi = {10.4230/LIPIcs.CPM.2021.1},
annote = {Keywords: Maximal repetitions, Squares, Lyndon words}
}
| Keywords: | Maximal repetitions, Squares, Lyndon words | |
| Seminar: | 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 30.06.2021 |
