Forschungstreffen 21189
The Number of Runs in Nonbinary Strings
( 02. May – 07. May, 2021 )
Permalink
        Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: 
        https://www.dagstuhl.de/21189
    
Organisator
- Johannes Fischer (TU Dortmund, DE)
Kontakt
- Heike Clemens (für administrative Fragen)
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.
 Johannes Fischer
                    Johannes Fischer
                
 Creative Commons BY 3.0 DE
                        Creative Commons BY 3.0 DE
                    