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.

Text (ChenetalMathematics2020Lowerboundsandexactenumerationinparticularcases)
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 ucycle, 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 ucycle, where a set in question is the set A^n of all words of length n over a kletter alphabet A. A universal word, or uword, is a linear, i.e., noncircular, version of thuniversal cycle; ucycle; universal word; uword; de Bruijn sequencee notion of a ucycle, and it is defined similarly. Removing some words in A^n may, or may not, result in a set of words for which ucycle, or uword, 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.
Creators(s):  Chen, Herman Z.Q., Kitaev, Sergey ORCID: https://orcid.org/0000000333241647 and Sun, Brian Y.; 

Item type:  Article 
ID code:  72338 
Keywords:  universal cycle, ucycle, universal word, uword, 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:  04 Sep 2020 04:51 
Related URLs:  
URI:  https://strathprints.strath.ac.uk/id/eprint/72338 
Export data: 