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}

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}ij\{\mathcal{A}_{ij}\}_{i\neq j} be the indicated family of automata. Extremality conjecture. The automaton En\mathcal{E}_n has reset threshold (n22)/2(n^2-2)/2, En\mathcal{E}'_n has reset threshold (n210)/2(n^2-10)/2, and On\mathcal{O}_n and On\mathcal{O}'_n have reset threshold (n21)/2(n^2-1)/2. Furthermore, they represent the automata with the largest possible reset threshold among the family {Aij}ij\{\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.

Sources & referencesView supporting material

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.