# PhD Seminar • Algorithms and Complexity • Words that Almost Commute and Anti-Commute 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|$).

Location
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Event tags

### June 2022

S M T W T F S
29
30
31
1
2
4
5
6
10
11
12
13
14
16
17
18
19
21
25
26
28
29
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)