×

Universal partial words over non-binary alphabets. (English) Zbl 1394.68271

A de Bruijn word of order \(n\) over an alphabet \(A\) is a cyclic word that contains each word of length \(n\) over \(A\) as a factor exactly once. Every de Bruijn word can be linearized by appending to the right its first \(n-1\) characters. The resulting word is called a universal word for \(A^n\). It is well known that de Bruijn words (and hence universal words) exist for every \(A\) and every \(n\). In this paper, the authors investigate the case of partial words. A partial word is a word over \(A\cup \{\diamond\}\), where \(\diamond\) is a wildcard that matches any symbol of \(A\). A partial word \(u\) is a factor of a partial word \(v\) if \(u\) is a factor of \(v\) in the classical sense, after possibly replacing some \(\diamond\) form \(v\) with letters of \(A\). For example, over \(A=\{0,1\}\), \(01\diamond 1\) is a factor of \(1\diamond 1\diamond 110\).
A universal partial word for \(A^n\) is a partial word that contains each word of \(A^n\) as a factor exactly once. For example, \(\diamond \diamond 0111\) is a universal partial word for \(\{0,1\}^3\). This notion has been introduced in a paper of H. Z. Q. Chen et al. [Electron. Notes Discrete Math. 61, 231–237 (2017; Zbl 1378.05112); Discrete Math. Theor. Comput. Sci. 19, No. 1, dmtcs:3690, 19 p. (2017; doi:10.23638/DMTCS-19-1-16)].
A universal partial word is called trivial if either all or none of its characters are \(\diamond\). The problem investigated in the paper is to determine the existence of non-trivial universal partial words for any \(n\). Chen et al. proved [loc. cit.] that non-trivial partial words exist for every \(n\) over a binary alphabet (containing a single \(\diamond\)).
The authors show that for \(|A|\geq 2\) and \(2\leq k\leq n/2\) no universal partial word exists for \(A^n\) having the form \(u\diamond^k v\), for (possibly empty) words \(u\) and \(v\).
A universal partial word for \(A^n\) is called cyclic if its first and last \(n-1\) characters are the same and non-overlapping. The authors prove that every non-trivial non-binary partial word is cyclic (while the aforementioned word \(\diamond \diamond 0111\) is an example of a non-trivial binary universal partial word that is not cyclic).
The last main result of the paper is that for any \(A\) of even size, there exists a non-trivial universal partial word for \(A^4\), and give an explicit construction of words of this type.
The paper ends with several open questions, the main of which concerns the existence of non-trivial universal partial words over a non-binary alphabet for \(n\geq 5\).

MSC:

68R15 Combinatorics on words

Citations:

Zbl 1378.05112
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allen, Emily; Blanchet-Sadri, Francine; Byrum, Cameron; Cucuringu, Mihai; Mercas, Robert, Counting bordered partial words by critical positions, Electron. J. Combin., 18, 1, Article P138 pp. (2011) · Zbl 1221.68174
[2] Blanchet-Sadri, Francine; Brownstein, Naomi C.; Kalcic, Andy; Palumbo, Justin; Weyand, Tracy, Unavoidable sets of partial words, Theory Comput. Syst., 45, 2, 381-406 (2009) · Zbl 1187.68358
[3] Blanchet-Sadri, Francine; Cordier, Michelle; Kirsch, Rachel, Border correlations, lattices, and the subgraph component polynomial, European J. Combin., 68, 2, 204-222 (2018) · Zbl 1373.05002
[4] Chen, Herman Z. Q.; Kitaev, Sergey; Mütze, Torsten; Sun, Brian Y., On universal partial words, Discrete Math. Theor. Comput. Sci., 19, 1 (May 2017) · Zbl 1408.68122
[5] Chung, Fan; Diaconis, Persi; Graham, Ron, Universal cycles for combinatorial structures, Discrete Math., 110, 1-3, 43-59 (1992) · Zbl 0776.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.