A note on Thue games

DOI10.1016/J.IPL.2016.10.004zbMATH Open1393.68144arXiv1601.02453OpenAlexW2963380556MaRDI QIDQ344549FDOQ344549

Publication date: 23 November 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: In this work we improve on a result from~cite{GryKosZma15}. 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~cite{GryKozMic13} using entropy compression, and building on the probabilistic arguments based on a version of the Lov'asz Local Lemma from~cite{Peg11}. We provide an explicit strategy for Ann to avoid (non-trivial) repetitions over a

7

-letter alphabet.

Full work available at URL: https://arxiv.org/abs/1601.02453

Recommendations

zbMATH Keywords

algorithms combinatorial problems avoidability nonrepetitive games Thue games

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) 2-person games (91A05) Combinatorics on words (68R15)

Cites Work

Cited In (6)

This page was built for publication: A note on Thue games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344549)