Rank-two word conjecture for irreducible automata

Let A=(Q,Σ,δ)\mathcal{A}=(Q,\Sigma,\delta) be an irreducible automaton. For a word uΣu\in\Sigma^*, let rk(u)\operatorname{rk}(u) denote the cardinality of the image of QQ under uu. Rank-two word conjecture. There exists a word uΣu\in\Sigma^* such that

rk(u)=2.\operatorname{rk}(u)=2.

All irreducible examples constructed in the paper have former-rank two, which motivates the conjecture. The source presents it as unresolved and notes that simple, non-irreducible automata of former-rank two also exist, so rank two alone cannot characterize irreducibility.

Sources & referencesView supporting material

Primary source

Riccardo Venturi, “Simplicity and irreducibility in circular automata”, arXiv:2511.16611 (2026).

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.