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

Herman Z. Q. Chen, Sergey Kitaev and Brian Y. Sun
Additional contact information
Herman Z. Q. Chen: School of Statistics and Data Science, Nankai University, Tianjin 300071, China
Sergey Kitaev: Department of Mathematics and Statistics, University of Strathclyde, Glasgow G1 1XH, UK
Brian Y. Sun: College of Mathematics and System Science, Xinjiang University, Urumqi, Xinjiang 830046, China

Mathematics, 2020, vol. 8, issue 5, 1-11

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 the 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 .

Keywords: universal cycle; u-cycle; universal word; u-word; de Bruijn sequence (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/5/778/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/5/778/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:5:p:778-:d:357245

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().