### Abstract

*A*and some integer

*n*≥1 is a word over

*A*such that every word of length n appears exactly once as a (consecutive) subword. It is well-known and easy to prove that universal words exist for any

*A*and

*n*. In this work we initiate the systematic study of universal

*partial*words. These are words that in addition to the letters from

*A*may contain an arbitrary number of occurrences of a special ‘joker’ symbol ◊

*A*, which can be substituted by any symbol from

*A*. For example,

*u*= 0◊011100 is a universal partial word for the binary alphabet

*A*= {0,1} and for

*n*= 3 (e.g., the first three letters of

*u*yield the subwords 000 and 010). We present several result on the existence and non-existence of universal partial words in different situations (depending on the number of ◊s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.

Original language | English |
---|---|

Journal | Electronic Notes in Discrete Mathematics |

Publication status | Accepted/In press - 29 Apr 2017 |

Event | European Conference on Combinatorics, Graph Theory and Applications - Freihaus, Vienna, Austria Duration: 28 Aug 2017 → 1 Sep 2017 http://www.dmg.tuwien.ac.at/eurocomb2017/ |

### Fingerprint

### Keywords

- universal words
- joker symbol
- binary alphabet

### Cite this

*Electronic Notes in Discrete Mathematics*.

}

*Electronic Notes in Discrete Mathematics*.

**On universal partial words.** / Chen, Herman Z.Q.; Kitaev, Sergey; Mutze, Torsten; Sun, Brian Y.

Research output: Contribution to journal › Conference Contribution

TY - JOUR

T1 - On universal partial words

AU - Chen, Herman Z.Q.

AU - Kitaev, Sergey

AU - Mutze, Torsten

AU - Sun, Brian Y.

PY - 2017/4/29

Y1 - 2017/4/29

N2 - A universal word for a finite alphabet A and some integer n≥1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. It is well-known and easy to prove that universal words exist for any A and n. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from A may contain an arbitrary number of occurrences of a special ‘joker’ symbol ◊ A, which can be substituted by any symbol from A. For example, u = 0◊011100 is a universal partial word for the binary alphabet A = {0,1} and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present several result on the existence and non-existence of universal partial words in different situations (depending on the number of ◊s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.

AB - A universal word for a finite alphabet A and some integer n≥1 is a word over A such that every word of length n appears exactly once as a (consecutive) subword. It is well-known and easy to prove that universal words exist for any A and n. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from A may contain an arbitrary number of occurrences of a special ‘joker’ symbol ◊ A, which can be substituted by any symbol from A. For example, u = 0◊011100 is a universal partial word for the binary alphabet A = {0,1} and for n = 3 (e.g., the first three letters of u yield the subwords 000 and 010). We present several result on the existence and non-existence of universal partial words in different situations (depending on the number of ◊s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.

KW - universal words

KW - joker symbol

KW - binary alphabet

UR - http://www.dmg.tuwien.ac.at/eurocomb2017/

UR - http://www.sciencedirect.com/science/journal/15710653

M3 - Conference Contribution

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -