# 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

Chen, Herman Z.Q. and Kitaev, Sergey and Sun, Brian Y.
(2020)
*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.*
Mathematics, 8 (5).
778.

Preview |
Text (Chen-etal-Mathematics-2020-Lower-bounds-and-exact-enumeration-in-particular-cases)
Chen_etal_Mathematics_2020_Lower_bounds_and_exact_enumeration_in_particular_cases.pdf Final Published Version License: Download (272kB)| Preview |

## Abstract

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.

#### ORCID iDs

Chen, Herman Z.Q., Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647 and Sun, Brian Y.;Item type: Article ID code: 72338 Dates: DateEvent12 May 2020Published9 May 2020AcceptedKeywords: universal cycle, u-cycle, universal word, u-word, de Bruijn sequence, Electronic computers. Computer science, Computer Science(all) Subjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Mathematics and Statistics Depositing user: Pure Administrator Date deposited: 13 May 2020 10:00 Last modified: 31 Mar 2021 00:48 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/72338