|Department of Computing and Software|
Title: Lyndon factors and periodicities in strings
Runs represent a type of maximal periodicities in a string. The conjecture that the maximum number of runs in a string is bounded by its length was resolved recently by Bannai, I, Inenaga, Nakashima, Takeda, and Tsuruta. Their approach is based on the use of the Lyndon roots of runs. The same approach was applied by Deza and Franek to verify the related d-step conjecture. In our talk, we will expose the connections of the Lyndon factors of a string to its runs, analyze applications of the Lyndon roots approach to problems concerning runs, investigate how the Lyndon factors of a string relate to the sorting of its suffixes, and discuss algorithms to compute the Lyndon array of a string.