The ACO Seminar (2023–2024)

Given a finite alphabet $A$ and fixed word length $n$, a universal word (or uword, also known as a De Bruijn sequence) for $A^n$ is a sequence in which every length-$n$ word from $A$ appears exactly once. A universal partial word (or upword) is similar but introduces $\diamond$ characters which are `wildcards' that stand in for any letter from $A$. In contrast to uwords, which have been studied extensively for decades, upwords have only attracted interest in the last few years. In this talk, we will investigate the similarities and differences between uwords and upwords. Over non-binary alphabets, these objects share many of the same characteristics, but in general there are many more constraints on the existence of upwords. We will provide new constructions of upwords and will highlight several open questions.