DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2026.23

Improved Bounds on the Sum of Exponents of Runs in a String

Authors: Arkadiusz Czarkowski

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract

A substring of a word is a run if it is at least twice as long as its minimum period and cannot be extended to either side with the same period. The exponent of a run is the quotient of its length and its minimum period. ρ(n) is the maximum number of runs in a string of length n, while σ(n) is the maximum sum of exponents of runs in a string of length n. While quite tight bounds on ρ(n) are known (0.944575712n ≤ ρ(n) ≤ n), the best upper bound on σ(n) is 3n whereas the best lower bound on σ(n) is 2.035n. In this paper, we improve the upper bound on σ(n) to 2.3n and the lower bound on σ(n) to 2.04448n. We also provide an improved upper bound on σ(n) of 2.2n in the case of a binary alphabet. Our results are achieved using a combination of theoretical and computer-based approaches.

Cite as

Arkadiusz Czarkowski. Improved Bounds on the Sum of Exponents of Runs in a String. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{czarkowski:LIPIcs.CPM.2026.23,
  author =	{Czarkowski, Arkadiusz},
  title =	{{Improved Bounds on the Sum of Exponents of Runs in a String}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.23},
  URN =		{urn:nbn:de:0030-drops-259494},
  doi =		{10.4230/LIPIcs.CPM.2026.23},
  annote =	{Keywords: strings, runs, sum of exponents of runs, Lyndon words, L-roots, maximal repetitions, combinatorics on words}
}

Search Results

Documents authored by Czarkowski, Arkadiusz

Improved Bounds on the Sum of Exponents of Runs in a String

Abstract

Cite as

Thanks for your feedback!

Could not send message