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
- 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
Never refreshed
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.