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.

### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2022
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11386/4796809`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 3
• ND