Vanishing leading asymptotic coefficient for fixed-occurrence word enumeration
Vanishing leading asymptotic coefficient for fixed-occurrence word enumeration
Let , let be a pattern using distinct letters, and let count words in containing exactly times. Let be the maximal number of states with loops in a simple path in the automaton . For constants determined by
vanishing-coefficient conjecture. There exist and a pattern such that and . In that case, there exist , , and such that
The authors report that they observed in many examples, so the conjecture predicts an exceptional pattern and a lower polynomial exponent in its asymptotics; no resolution is supplied.
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.