Shortest Repetition-Free Words Accepted by Automata
classification
💻 cs.FL
cs.DMmath.CO
keywords
acceptedshortestwordacceptsautomataautomatonboundsconsider
read the original 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 paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.