2016/01/11 by Mercaş, Robert, Nowotka, Dirk
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1601.02453
In this work we improve on a result from~\citeGryKosZma15. 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~\citeGryKozMic13 using entropy compression, and building on the probabilistic arguments based on a version of the Lovász Local Lemma from~\citePeg11. We provide an explicit strategy for Ann to avoid (non-trivial) repetitions over a 7-letter alphabet.