2026-07-24T05:47:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15974 2024-03-06T10:56:59Z ddc:004 open_access

Fun Slot Machines and Transformations of Words Avoiding Factors Anselmo, Marcella Flores, Manuela Madonia, Maria Isometric words Words avoiding factors Index of a word Overlap Lee distance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marcella Anselmo and Manuela Flores and Maria Madonia 2022 Is Part Of LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2022.4 urn:nbn:de:0030-drops-159743 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.4 eng https://creativecommons.org/licenses/by/4.0/legalcode