Linear growth and repeated values of the automaton exponent MrM_r

About 7 years old · traced to

Fix n,k∈Nn,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 d−1d-1 loops in a simple path in the automaton Au(v,r,k)Au(v,r,k). Conjecture on MrM_r. (a) The limit

lim⁡r→∞Mrr\lim_{r\to\infty}\frac{M_r}{r}

exists and belongs to (0,∞)(0,\infty). (b) There exist k∈Nk\in\mathbb N, a pattern v∈[k]∗v\in[k]^* with d>1d>1, and an increasing sequence of integers (rn)n∈N(r_n)_{n\in\mathbb N} such that Mrn=Mrn−1M_{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.

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

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.