TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


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

Kontakt

Description

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.

Copyright Johannes Fischer