22 problems

Černý's conjecture. If $M$ is synchronizable, then $M$ has a synchronizing word of length at most

Let $\mathcal{A}=(Q,\Sigma,\delta)$ be an extremal automaton, meaning an automaton whose shortest reset word reaches the relevant extremal bound. An automaton is weakly defective i…

Let $\mathcal{A}=(Q,\Sigma,\delta)$ be an irreducible automaton. For a word $u\in\Sigma^*$, let $\operatorname{rk}(u)$ denote the cardinality of the image of $Q$ under $u$. Rank-tw…

Let $\mathcal{A}=(Q,\Sigma,\delta)$ be a synchronizing automaton with $n=|Q|$. Its rank is the cardinality of the image of the state set under a word, and it is extremal if its sho…

Let an extremal automaton be a synchronizing automaton attaining equality in the Černý bound. Simplicity conjecture. Every extremal automaton is simple. The conjecture is motivated…

Let $\mathcal{A}$ be either a simple or quasi-simple automaton with $n$ states, and let $\mathcal{R}(\mathcal{A})$ be its associated synchronized $\mathbb{C}$-algebra. Matrix-algeb…

A semisimple automaton is an automaton in the class considered in the paper for which the semisimple reduction is defined. Semisimple conjecture. If the Černý conjecture is solved…

Let $\mathcal{A}$ be a synchronizing automaton, and let $\sigma\in\operatorname{Cong}(\mathcal{A})$ be a non-trivial congruence, so that the quotient automaton $\mathcal{A}/\sigma$…

Product-corner conjecture. If $M_1,\ldots,M_k$ are distinct and each contains an $f$-corner $z_i$, then $M$ is $(z_1,\ldots,z_k)$-synchronizable. The conjecture extends the paper's…

Difference-DFA Černý conjecture. The DFA $M$ has a synchronizing word of length at most

$O(G)$ conjecture. The set of graphs $H$ with $H\fold_S G$ has a unique $\fold_S$-minimal element $O(G)$.

Let $\mathrsfs{A}$ be an $n$-state complete automaton, and let $r$ be the minimal rank of any word, where the rank of a word is the cardinality of its image on the state set. Rank…

A synchronizing automaton is a finite automaton whose transition semigroup contains a word sending every state to the same state; its reset threshold $rt(\mathcal{A})$ is the lengt…

Let $\mathcal{E}_n$, $\mathcal{E}'_n$, $\mathcal{O}_n$ and $\mathcal{O}'_n$ be the explicitly constructed automata in the paper, and let $\{\mathcal{A}_{ij}\}_{i\neq j}$ be the ind…

Černý's conjecture for D3-directing CNFAs. Every D3-directing CNFA with $n$ states admits a D3-directing word of length at most

Don's reachable-subset length conjecture. There is a word $v$ such that $\delta(Q,v)=S$ and whose length is at most

Let $A=(Q,\Sigma)$ be a finite automaton with $n=|Q|$ states. Its rank $r$ is the minimum rank of its input words, where the rank of an input word is the cardinality of the image o…

Let ${\cal M}\subset\{0,1\}^{n\times n}$ be a synchronizing automaton, with synchronizing words defined by products of matrices from ${\cal M}$ that have the form $e e_i^T$. Quadra…

Let $G$ be a finite dihedral group. Call $G$ a Černý group if the relevant synchronizing automata containing its Cayley graph admit synchronizing words satisfying the Černý bound.…

Let $G$ be a finite abelian group. Call $G$ a Černý group if the relevant synchronizing automata containing its Cayley graph admit synchronizing words satisfying the Černý bound. Č…

Let $G$ be a finite cyclic group. Call $G$ a Černý group if the relevant synchronizing automata containing its Cayley graph admit synchronizing words satisfying the Černý bound. Če…

Let $G$ be a finite group and let $cDelta$ be a generating set. The automaton $(G,cDelta)$ is the Cayley graph of $G$ with respect to $cDelta$; call $G$ a Černý group if every sync…