Shortest Repetition-Free Words Accepted by Automata

2013/04/10 by Hamoon Mousavi, Jeffrey Shallit, Mousavi, Hamoon +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.DM #cs.FL #math.CO

paper · pdf · doi:10.48550/arxiv.1304.2959

12 pages, conference paper

arxiv created 2013/04/10 · arxiv updated 2013/04/11

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.

Related

• Lengths of Words Accepted by Nondeterministic Finite Automata
• Modifying the upper bound on the length of minimal synchronizing word
• An improvement to a recent upper bound for synchronizing words of finite automata
• Detecting palindromes, patterns, and borders in regular languages
• Experimental Study of the Shortest Reset Word of Random Automata