A note on Thue games

详细信息    查看全文

• 作者：Robert Mercaş^a ; ¹ ; ^{R.G.Mercas@lboro.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Dirk Nowotka^b ; ^{dn@informatik.uni-kiel.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Avoidability ; Thue games ; Nonrepetitive games ; Algorithms ; Combinatorial problems
• 刊名：Information Processing Letters
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：118
• 期：Complete
• 页码：75-77
• 全文大小：196 K

文摘

In 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 same end of the construction. 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 of 6 showed in [2] using entropy compression while building on the probabilistic arguments based on a version of the Lovász Local Lemma from [4]. Our result provides an explicit strategy for Ann to avoid (non-trivial) repetitions over a 7-letter alphabet.