Find in Library

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 <inline-formula> <math display="inline"> <semantics> <msup> <mi>A</mi> <mi>n</mi> </msup> </semantics> </math> </inline-formula> of all words of length <i>n</i> over a <i>k</i>-letter alphabet <i>A</i>. 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 <inline-formula> <math display="inline"> <semantics> <msup> <mi>A</mi> <mi>n</mi> </msup> </semantics> </math> </inline-formula> 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 <inline-formula> <math display="inline"> <semantics> <msup> <mi>A</mi> <mi>n</mi> </msup> </semantics> </math> </inline-formula>, or the case when <inline-formula> <math display="inline"> <semantics> <mrow> <mi>k</mi> <mo>=</mo> <mn>2</mn> </mrow> </semantics> </math> </inline-formula> and <inline-formula> <math display="inline"> <semantics> <mrow> <mi>n</mi> <mo>≤</mo> <mn>4</mn> </mrow> </semantics> </math> </inline-formula>.