Linear growth and repeated values of the automaton exponent
Fix and a pattern using distinct letters. Let be the maximal number of states with loops in a simple path in the automaton . Conjecture on . (a) The limit
exists and belongs to . (b) There exist , a pattern with , and an increasing sequence of integers such that . The preceding asymptotic theorem shows that is non-decreasing in ; the conjecture predicts both a positive linear asymptotic rate and infinitely many possible repetitions, but the source provides no resolution.
References
Primary source
Toufik Mansour, Reza Rastegar and Alexander Roitershtein, “Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations”, arXiv:1905.05646 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.