1 Search Results for "Flores, Manuela"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Anselmo, Marcella
  • 1 Flores, Manuela
  • 1 Madonia, Maria

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Index of a word
  • 1 Isometric words
  • 1 Lee distance
  • 1 Overlap
  • 1 Words avoiding factors

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail