Abstract | ||
---|---|---|
Chen, Kitaev, Mütze, and Sun recently introduced the notion of universal partial words, a generalization of universal words and de Bruijn sequences. Universal partial words allow for a wild-card character ⋄, which is a placeholder for any letter in the alphabet. We extend results from the original paper and develop additional proof techniques to study these objects. 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 an infinite family of universal partial words over non-binary alphabets. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.tcs.2017.12.022 | Theoretical Computer Science |
Keywords | Field | DocType |
Combinatorics on words,Universal cycles | Discrete mathematics,Combinatorics,Chen,De Bruijn sequence,Periodic graph (geometry),Mathematics,Binary number,Alphabet | Journal |
Volume | ISSN | Citations |
713 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 5 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bennet Goeckner | 1 | 0 | 0.34 |
Corbin Groothuis | 2 | 0 | 0.68 |
Cyrus Hettle | 3 | 0 | 0.34 |
Brian Kell | 4 | 0 | 0.34 |
Pamela Kirkpatrick | 5 | 0 | 0.34 |
Rachel Kirsch | 6 | 1 | 1.07 |
Ryan W. Solava | 7 | 0 | 0.34 |