Please note: This PhD seminar will be given online.
Daniel
Gabric,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
Supervisor: Professor Jeffrey Shallit
A word is said to be \emph{bordered} if it contains a non-empty proper prefix that is also a suffix. Otherwise, it is said to be \emph{unbordered}. Two words $u$ and $v$ are said to be conjugates if they are cyclic shifts of each other. For example, the words {\tt eat} and {\tt ate} are conjugates. Using a decision procedure based on automatic sequences, we complete the classification, due to Harju and Nowotka, of binary words with the maximum number of unbordered conjugates. Furthermore, we prove that for every possible number, up to the maximum, there exists a word having that number of unbordered conjugates.
To join this PhD seminar on Zoom, please go to https://us02web.zoom.us/j/87860417179?pwd=cGRFZVBnSmlsa3ltbnBHSWExZ0Uvdz09.