PhD Seminar • Algorithms and Complexity • Words that Almost Commute and Anti-CommuteExport this event to calendar

Thursday, March 10, 2022 — 12:00 PM EST

Please note: This PhD seminar will be given online.

Daniel Gabric, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Jeffrey Shallit

The \emph{Hamming distance} $\text{ham}(u,v)$ between two equal-length words $u$, $v$ is the number of positions where $u$ and $v$ differ. The words $u$ and $v$ are said to be \emph{conjugates} if there exist non-empty words $x,y$ such that $u=xy$ and $v=yx$. The smallest value $\text{ham}(xy,yx)$ can take on is $0$, when $x$ and $y$ commute. But, interestingly, the next smallest value $\text{ham}(xy,yx)$ can take on is $2$ and not $1$. We provide an efficient formula to count the number $h(n)$ of length-$n$ words $u=xy$ over a $k$-letter alphabet that have a conjugate $v=yx$ such that $\text{ham}(xy,yx)=2$. We also provide efficient formulae for other quantities closely related to $h(n)$. Additionally, we give some results on the asymptotic behaviour of $h(n)$. Finally, we show some preliminary results on conjugates $u=xy$ and $v=yx$ that differ in all positions (i.e., $\text{ham}(xy,yx)=|xy|$).


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/98110702741?pwd=OXRad1FNV2gxZ0lwTHdISmNYZnVhZz09.

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 (123)
    1. July (5)
    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)