PhD Seminar • Algorithms and Complexity • The Maximum Number of Unbordered Conjugates Among Binary Words Export this event to calendar

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
Canada
Event tags 

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