ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let A=(Q,Σ,δ)\mathcal{A}=(Q,\Sigma,\delta) be a synchronizing automaton with n=∣Q∣n=|Q|. Its rank is the cardinality of the image of the state set under a word, and it is extremal if its shortest reset word has length exactly (n−1)2(n-1)^2. An automaton is irreducible when it has no nontrivial invariant subspaces in the representation used in the paper. Conjecture on extremal automata. Every extremal synchronizing automaton is irreducible.

The conjecture would extend the known relationship between extremal synchronizing automata and irreducibility beyond the examples currently available. The source notes that every known extremal automaton is irreducible, but does not establish the assertion in general.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.