Shortest Repetition-Free Words Accepted by Automata
arXiv:1304.2959
Abstract
We consider the following problem: given that a finite automaton of states accepts at least one -power-free (resp., overlap-free) word, what is the length of the shortest such word accepted? We give upper and lower bounds which, unfortunately, are widely separated.
12 pages, conference paper