Fun Slot Machines and Transformations of Words Avoiding Factors

Abstract

Fun Slot Machines are a variant of the classical ones. Pulling a lever, the player generates a sequence of symbols which are placed on the reels. The machine pays when a given pattern appears in the sequence. The variant consists in trying to transform a losing sequence of symbols in another one, in such a way that the winning pattern does not appear in any intermediate step. The choice of the winning pattern can be crucial; there are "good"and "bad"sequences. The game results in a combinatorial problem on transformations of words avoiding a given pattern as a factor. We investigate "good"and "bad"sequences on a k-ary alphabet and the pairs of words that witness that a word is "bad". A main result is an algorithm to decide whether a word is "bad"or not and to provide a pair of witnesses of minimal length when the word is "bad". It runs in O(n) time with a preprocessing of O(n) time and space to construct an enhanced suffix tree of the word.