License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.4
URN: urn:nbn:de:0030-drops-159743
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15974/
Go to the corresponding LIPIcs Volume Portal

Anselmo, Marcella ; Flores, Manuela ; Madonia, Maria

Fun Slot Machines and Transformations of Words Avoiding Factors

pdf-format:
LIPIcs-FUN-2022-4.pdf (0.7 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2022/15974},
  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}
}

Keywords: Isometric words, Words avoiding factors, Index of a word, Overlap, Lee distance
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI