Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777077 | Electronic Notes in Discrete Mathematics | 2017 | 7 Pages |
Abstract
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 results 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Herman Z.Q. Chen, Sergey Kitaev, Torsten Mütze, Brian Y. Sun,