On universal partial words

Chen, Herman Z.Q. and Kitaev, Sergey and Mütze, Torsten and Sun, Brian Y. (2017) On universal partial words. Discrete Mathematics and Theoretical Computer Science, 19 (1). 16. ISSN 1365-8050 (In Press)

[thumbnail of chen-etal-DMTCS-2017-On-universal-partial]
Preview
 Text. Filename: chen_etal_DMTCS_2017_On_universal_partial.pdf
Accepted Author Manuscript
Download (486kB)| Preview

Abstract

A universal word for a finite alphabet A and some integer n ≥ 1 is a word over A such that every word in A n appears exactly once as a subword (cyclically or linearly). 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 3 / ∈ A , which can be substituted by any symbol from A. For example, u = 0 3 011100 is a linear 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 linear and cyclic universal partial words in different situations (depending on the number of 3 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.

ORCID iDs

Chen, Herman Z.Q., Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Mütze, Torsten and Sun, Brian Y.;
CORE (COnnecting REpositories)