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

Anselmo M.
;
Flores M.
;
Madonia M.
2022-01-01

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact