Universal partial words over non-binary alphabets

Abstract: Chen, Kitaev, M"{u}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

d i a m o n d

, which is a placeholder for any letter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic

d i a m o n d

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 a family of universal partial words over alphabets of even size.

Review text

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 \textit{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 \textit{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 \textit{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; \url{doi:10.23638/DMTCS-19-1-16})]. A universal partial word is called \textit{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 \textit{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\).

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Universal partial words over non-binary alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1694683)