TY - JOUR

T1 - Lower bounds, and exact enumeration in particular cases, for the probability of existence of a universal cycle or a universal word for a set of words

AU - Chen, Herman Z.Q.

AU - Kitaev, Sergey

AU - Sun, Brian Y.

PY - 2020/5/12

Y1 - 2020/5/12

N2 - A universal cycle, or u-cycle, for a given set of words is a circular word that contains each word from the set exactly once as a contiguous subword. The celebrated de Bruijn sequences are a particular case of such a u-cycle, where a set in question is the set A^n of all words of length n over a k-letter alphabet A. A universal word, or u-word, is a linear, i.e., non-circular, version of thuniversal cycle; u-cycle; universal word; u-word; de Bruijn sequencee notion of a u-cycle, and it is defined similarly. Removing some words in A^n may, or may not, result in a set of words for which u-cycle, or u-word, exists. The goal of this paper is to study the probability of existence of the universal objects in such a situation. We give lower bounds for the probability in general cases, and also derive explicit answers for the case of removing up to two words in A^n, or the case when k = 2 and n ≤ 4.

AB - A universal cycle, or u-cycle, for a given set of words is a circular word that contains each word from the set exactly once as a contiguous subword. The celebrated de Bruijn sequences are a particular case of such a u-cycle, where a set in question is the set A^n of all words of length n over a k-letter alphabet A. A universal word, or u-word, is a linear, i.e., non-circular, version of thuniversal cycle; u-cycle; universal word; u-word; de Bruijn sequencee notion of a u-cycle, and it is defined similarly. Removing some words in A^n may, or may not, result in a set of words for which u-cycle, or u-word, exists. The goal of this paper is to study the probability of existence of the universal objects in such a situation. We give lower bounds for the probability in general cases, and also derive explicit answers for the case of removing up to two words in A^n, or the case when k = 2 and n ≤ 4.

KW - universal cycle

KW - u-cycle

KW - universal word

KW - u-word

KW - de Bruijn sequence

UR - https://www.mdpi.com/2227-7390/8/5/778#cite

U2 - 10.3390/math8050778

DO - 10.3390/math8050778

M3 - Article

VL - 8

JO - Mathematics

JF - Mathematics

IS - 5

M1 - 778

ER -