Shortest repetition-free words accepted by automata

From MaRDI portal
Publication:2843095




Abstract: We consider the following problem: given that a finite automaton M of N states accepts at least one k-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.









This page was built for publication: Shortest repetition-free words accepted by automata

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