DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2022.4

Fun Slot Machines and Transformations of Words Avoiding Factors

Authors: Marcella Anselmo, Manuela Flores, and Maria Madonia

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

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.

Cite as

Marcella Anselmo, Manuela Flores, and Maria Madonia. Fun Slot Machines and Transformations of Words Avoiding Factors. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{anselmo_et_al:LIPIcs.FUN.2022.4,
  author =	{Anselmo, Marcella and Flores, Manuela and Madonia, Maria},
  title =	{{Fun Slot Machines and Transformations of Words Avoiding Factors}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.4},
  URN =		{urn:nbn:de:0030-drops-159743},
  doi =		{10.4230/LIPIcs.FUN.2022.4},
  annote =	{Keywords: Isometric words, Words avoiding factors, Index of a word, Overlap, Lee distance}
}

Search Results

Documents authored by Anselmo, Marcella

Fun Slot Machines and Transformations of Words Avoiding Factors

Abstract

Cite as

Thanks for your feedback!

Could not send message