Please note: This PhD defence will take place online.
Daniel Gabric, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Jeffrey Shallit
Combinatorics on words is a field of mathematics and theoretical computer science that is concerned with sequences of symbols called words, or strings. One class of words that are ubiquitous in combinatorics on words, and theoretical computer science more broadly, are the \emph{bordered words}. The word $w$ has a border $u$ if $u$ is a non-empty proper prefix and suffix of $w$. The word $w$ is said to be bordered if it has a border. Otherwise $w$ is said to be \emph{unbordered}.
This thesis is primarily concerned with variations and generalizations of bordered and unbordered words.
The main results of this thesis are new and improved upper and lower bounds for the number of length-$n$ privileged and closed words. A word is said to be \emph{closed} if it is of length $\leq 1$ or if it has a border that occurs exactly twice within the word. A word is said to be \emph{privileged} if it is of length $\leq 1$ or if it has a privileged border that occurs exactly twice in the word. We resolve the asymptotic behaviour of the number of length-$n$ closed words over a $k$-letter alphabet, show showing that it is asymptotically $\Theta(\frac{k^n}{n})$. We also give a family of upper and lower bounds on the number of length-$n$ privileged words that are separated by a factor that grows arbitrarily slowly.
We complete the characterization, due to Harju and Nowotka, of binary words with the maximum number of unbordered conjugates. We show that for every number, up to this maximum, there exists a binary word with that number of unbordered conjugates.
We also give results on pairs of words that almost commute and anti-commute. Two words $x$ and $y$ almost commute if $xy$ and $yx$ differ in exactly two places, and they anti-commute if $xy$ and $yx$ differ in all places. We characterize and count the number of pairs of words that almost and anti-commute. We also characterize and count variations of almost-commuting words. We conclude with some asymptotic results related to the number of almost-commuting pairs of words.
We count the number of length-$n$ bordered words with a unique border. We also show that the probability a length-$n$ word has a unique border tends to a constant.
We present results on factorizations of words related to borders, called \emph{block palindromes}. A block palindrome is a factorization of a word into blocks that turns into a palindrome if each identical block is replaced by a distinct character. So each block is a border of a central block. We call the number of blocks in a block palindrome the \emph{width} of the block palindrome. The \emph{largest block palindrome} of a word is the block palindrome of the word with the maximum width. We count all length-$n$ words that have a width-$t$ \emph{largest block palindrome}. We also show that the expected width of a largest block palindrome tends to a constant. We conclude with some results on another extremal variation of block palindromes, the \emph{smallest block palindrome}.
Finally we work with a generalization of bordered words to pairs of words. We obtain a characterization and enumeration result for this generalization of bordered words to multiple dimensions. We also show that the number of such pairs of length-$n$ words approaches $c_k\cdot k^{2n}$ for some constant $c_k>0$ as $n$ goes to infinity.