Extremality of the automata En\mathcal{E}_n, En′\mathcal{E}'_n, On\mathcal{O}_n and On′\mathcal{O}'_n in the family Aij\mathcal{A}_{ij}

About 8 years old · traced to

Let En\mathcal{E}_n, En′\mathcal{E}'_n, On\mathcal{O}_n and On′\mathcal{O}'_n be the explicitly constructed automata in the paper, and let {Aij}i≠j\{\mathcal{A}_{ij}\}_{i\neq j} be the indicated family of automata. Extremality conjecture. The automaton En\mathcal{E}_n has reset threshold (n2−2)/2(n^2-2)/2, En′\mathcal{E}'_n has reset threshold (n2−10)/2(n^2-10)/2, and On\mathcal{O}_n and On′\mathcal{O}'_n have reset threshold (n2−1)/2(n^2-1)/2. Furthermore, they represent the automata with the largest possible reset threshold among the family {Aij}i≠j\{\mathcal{A}_{ij}\}_{i\neq j} for, respectively, n=4kn=4k, n=4k+2n=4k+2, n=4k+1n=4k+1 and n=4k+3n=4k+3. The claim records the reset thresholds and extremal members of this constructed family; the supplied excerpt does not identify a resolution status or provide enough surrounding definitions to assess it independently.

References

Primary source

Costanza Catalano and Raphaël M. Jungers, “On random primitive sets, directable NDFAs and the generation of slowly synchronizing DFAs”, arXiv:1810.11323 (2018).

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.