Thue_games_v2.pdf (223.1 kB)
Download file

A note on Thue games

Download (223.1 kB)
journal contribution
posted on 01.08.2016, 14:54 by Robert MercasRobert Mercas, Dirk Nowotka
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 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

Citation

MERCAS, R. and NOWOTKA, D., 2017. A note on Thue games. Information Processing Letters, 118 (February), pp. 75–77.

Publisher

© Elsevier

Version

AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Acceptance date

20/10/2016

Publication date

2017

Notes

This paper was accepted for publication in the journal Information Processing Letters and the definitive published version is available at http://dx.doi.org/10.1016/j.ipl.2016.10.004

ISSN

0020-0190

eISSN

1872-6119

Language

en

Usage metrics

Keywords

Exports