Student Seminar - November 2017
Join us for the November installment of our recurring Student Seminar series. Refreshments will be provided.
*Updated Social Event*
After the seminar we will be hosting a movie double feature with popcorn. We will be showing Office Space and Little Shop of Horrors
Parallelization and Verification of Sequential Code using Discrete Event Systems
Research on the possibilities of using discrete event systems (DES) in the modeling and verification of sequential codes. The DES are used to model both the sequential and parallel versions of the code, and the system properties of the DES indicate the correctness of the parallel code.
Lyndon factors and Periodicities in Strings
Runs represent a type of maximal periodicity in strings. Though first conjectured in 1999 by Kolpakov and Kucherov, the runs conjecture that there are fewer runs than the length of the string was only settled in 2015 by Bannai et al. via specific Lyndon roots referred to as L-roots. This method allows mapping of runs to the starting points of its L-roots that form mutually disjoint subsets of the indices of the string. Thus, computing the all maximal Lyndon factors efficiently becomes of importance.
In the talk, I will present a new and conceptually simple data structure called Lyndon array and its relationship to the suffix array. I will also discuss the 2015 Baier's algorithm for sorting suffixes that identifies and sorts in phase 2 the maximal Lyndon factors in O(n log(|Ʃ)) steps for a string of length n over an alphabet Ʃ. The talk presents the fact that Baier's algorithm sorts the suffixes by sorting the maximal Lyndon factors, and present a different, potentially faster algorithm for phase 2.