May 2 – 7 , 2021, Event 21189

The Number of Runs in Nonbinary Strings


Johannes Fischer (TU Dortmund, DE)

For support, please contact

Heike Clemens


A run is a string of the form αk for α∈Σ* and k≥2. For example, the string bananatree contains the runs anana = (an) 5/2 and ee = e2. It is known that the number of runs in a string of length n is at most n-1 [H. Bannai et al.: The "Runs" Theorem. SIAM J. Comput. 46(5): 1501-1514 (2017)]. However, for binary strings a stronger upper bound 183/193 is known [S. Holub: Prefix frequency of lost positions. Theor. Comput. Sci. 684: 43-52 (2017)]. The purpose of this project is to extend this stronger upper bound to nonbinary strings. Maybe in a first step, one could try to extend the techniques to ternary strings and then generalize what happens for larger alphabets.

Motivation text license
  Creative Commons BY 3.0 DE
  Johannes Fischer

Online Publications

We offer several possibilities to publish the results of your event. Please contact publishing(at) if you are interested.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf in the library.