Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 26, 2015, 12:15 pm
Duration: 45 minutes
Location: CAB G51
Speaker: Raúl Penaguião
A non-repetitive sequence is a sequence of symbols in which no two consecutive blocks of the same size are equal. 123132123 is nonrepetitive. With two symbols it's impossible to write an infinite non-repetitive sequence, but a remarkable result due to Thue asserts that such is possible using only three distinct symbols. This paper introduces a more general problem, where one is only allowed to use a symbol from a previously given list L_i on the position i. It's always possible to construct in such settings a non-repetitive infinite sequence when the given lists are of size four, and it's still a conjecture weather for lists of size three still holds. This is proven using a randomized algorithm. In this context, a games is introduced. The erase-repetition game is a game played by two people where a sequence is constructed alternately according to the symbols in the lists L_i, and player A tries to build an arbitrary long nonrepetitive sequence, whereas player B tries to keep the sequence on a small size. We are able to prove that the player A has a strategy, provided that the lists are big enough.
Automatic MiSe System Software Version 1.4803M | admin login