Linear growth and repeated values of the automaton exponent MrM_r

From papers

Fix n,kNn,k\in\mathbb N and a pattern v[k]v\in[k]^* using d>1d>1 distinct letters. Let MrM_r be the maximal number of states with d1d-1 loops in a simple path in the automaton Au(v,r,k)Au(v,r,k). Conjecture on MrM_r. (a) The limit

limrMrr\lim_{r\to\infty}\frac{M_r}{r}

exists and belongs to (0,)(0,\infty). (b) There exist kNk\in\mathbb N, a pattern v[k]v\in[k]^* with d>1d>1, and an increasing sequence of integers (rn)nN(r_n)_{n\in\mathbb N} such that Mrn=Mrn1M_{r_n}=M_{r_n-1}. The preceding asymptotic theorem shows that MrM_r is non-decreasing in rr; 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

No solutions have been posted yet.