# PhD Seminar • Algorithms and Complexity • The Maximum Number of Unbordered Conjugates Among Binary Words

Wednesday, November 3, 2021 — 2:15 PM EDT

## 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.

Location
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Event tags

### January 2022

S M T W T F S
26
27
28
29
30
31
1
2
3
5
7
8
9
11
12
15
16
22
23
25
26
28
29
30
1
2
3
4
5
1. 2022 (19)
1. February (1)
2. January (18)
2. 2021 (210)
1. December (21)
2. November (13)
3. October (12)
4. September (21)
5. August (20)
6. July (17)
7. June (11)
8. May (16)
9. April (27)
10. March (20)
11. February (13)
12. January (19)
3. 2020 (217)
4. 2019 (255)
5. 2018 (217)
6. 2017 (36)
7. 2016 (21)
8. 2015 (36)
9. 2014 (33)
10. 2013 (23)
11. 2012 (4)
12. 2011 (1)
13. 2010 (1)
14. 2009 (1)
15. 2008 (1)