Irreducibility of extremal synchronizing automata
Statement
Let be a synchronizing automaton with . 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 . 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.