A note on Thue games
journal contributionposted on 01.08.2016, 14:54 authored by Robert MercasRobert Mercas, Dirk Nowotka
In this work we improve on a result from . 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  using entropy compression, and building on the probabilistic arguments based on a version of the Lov´asz Local Lemma from . We provide an explicit strategy for Ann to avoid (non-trivial) repetitions over a 7-letter alphabet.
- Computer Science