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.

Anselmo M., Flores M., Madonia M. (2022). Fun Slot Machines and Transformations of Words Avoiding Factors. In P. Fraigniaud, Y. Uno (a cura di), 11th International Conference on Fun with Algorithms (FUN 2022). Schloss-Dagstuhl - Leibniz Zentrum für Informatik [10.4230/LIPIcs.FUN.2022.4].

Fun Slot Machines and Transformations of Words Avoiding Factors

Flores M.;
2022-05-23

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.
23-mag-2022
Settore INF/01 - Informatica
978-3-95977-232-7
Anselmo M., Flores M., Madonia M. (2022). Fun Slot Machines and Transformations of Words Avoiding Factors. In P. Fraigniaud, Y. Uno (a cura di), 11th International Conference on Fun with Algorithms (FUN 2022). Schloss-Dagstuhl - Leibniz Zentrum für Informatik [10.4230/LIPIcs.FUN.2022.4].
File in questo prodotto:
File Dimensione Formato  
LIPIcs.FUN.2022.4.pdf

accesso aperto

Tipologia: Versione Editoriale
Dimensione 758.11 kB
Formato Adobe PDF
758.11 kB Adobe PDF Visualizza/Apri

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/10447/619117
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact