Date:
-
Location:
CB 345
Speaker(s) / Presenter(s):
Cyrus Hettle
Discrete CATS Seminar
Monday, Feb 6
2pm
CB 345
Speaker: Cyrus Hettle
Title: Universal partial words
Abstract: A universal word for an alphabet A and a positive integer n is a word containing each of the words of length n over A as a substring exactly once. For instance, de Bruijn sequences are (cyclic) universal words. Universal partial words, introduced by Chen, Kitaev, Mutze, and Sun in 2016, allow for a wild-card character 
, which can stand for any letter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic structure and are cyclic, and we give number-theoretic conditions on the existence of universal partial words. In addition, we provide an explicit construction for a family of universal partial words over alphabets of even size. This talk is based on joint work with Bennet Goeckner, Corbin Groothius, Brian Kell, Pamela Kirkpatrick, Rachel Kirsch, and Ryan Solava.
, which can stand for any letter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic structure and are cyclic, and we give number-theoretic conditions on the existence of universal partial words. In addition, we provide an explicit construction for a family of universal partial words over alphabets of even size. This talk is based on joint work with Bennet Goeckner, Corbin Groothius, Brian Kell, Pamela Kirkpatrick, Rachel Kirsch, and Ryan Solava.
Event Series: