Thue_games_v2.pdf (223.1 kB)
Download fileA note on Thue games
journal contribution
posted on 2016-08-01, 14:54 authored by Robert MercasRobert Mercas, Dirk NowotkaIn this work we improve on a result from [1]. In particular,
we investigate the situation where a word is constructed jointly by two
players who alternately append letters to the end of an existing word.
One of the players (Ann) tries to avoid (non-trivial) repetitions, while
the other one (Ben) tries to enforce them. We show a construction that
is closer to the lower bound showed in [2] using entropy compression, and
building on the probabilistic arguments based on a version of the Lov´asz
Local Lemma from [3]. We provide an explicit strategy for Ann to avoid
(non-trivial) repetitions over a 7-letter alphabet.
History
School
- Science
Department
- Computer Science