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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Words Avoiding Half-Flips

  • James Currie,
  • Narad Rampersad

摘要

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.