PhD Seminar • Algorithms and Complexity • Mutual Borders and OverlapsExport this event to calendar

Thursday, June 30, 2022 — 1:00 PM to 2:00 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 bordered if it contains a non-empty proper prefix that is also a suffix. We can naturally extend this definition to pairs of non-empty words. A pair of words (u,v) is said to be mutually bordered if there exists a word that is a non-empty proper prefix of u and suffix of v, and there exists a word that is a non-empty proper suffix of u and prefix of v. In other words, (u,v) is mutually bordered if u overlaps v and v overlaps u. We give a recurrence for the number of mutually bordered pairs of words. Furthermore, we show that, asymptotically, there are c · k2n mutually bordered words of length-n over a k-letter alphabet, where c is a constant. Finally, we show that the expected shortest overlap between pairs of words is bounded above by a constant.


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/97749736516.

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
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
2
  1. 2022 (126)
    1. July (8)
    2. June (17)
    3. May (20)
    4. April (24)
    5. March (22)
    6. February (16)
    7. January (19)
  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)