Linear growth and repeated values of the automaton exponent
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.