Words Avoiding Half-Flips
摘要
We say that a word w contains a half-flip if it contains non-empty factors u and vu where \(|u|=|v|\) . Fici reports a non-constructive proof of the existence of an infinite word over a finite alphabet avoiding half-flips and asks the size of the smallest alphabet over which half-flips may be avoided. Half-flips are unavoidable over a 4-letter alphabet. Over an 8-letter alphabet we conjecture a 3-uniform D0L avoiding half-flips; over a 5-letter alphabet we conjecture a messier HD0L construction.