35 problems

Černý's conjecture. Every synchronizing automaton with $n$ states admits a reset 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…

The paper studies a rank result for circular automata, concerning the ranks of letters in reducible automata and the resulting synchronization behavior. Non-circular rank conjectur…

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$…

Tightness conjecture. The matching lower bounds in these three instances are tight.

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…

Let $Q=[n]$, let the alphabet be $Σ=\{a,b\}$, and choose the transition function $\delta:Q\times Σ\to Q$ uniformly at random, so that each pair in $[n]\times\{a,b\}$ is mapped inde…

Consider a random automaton with $n$ states and two random mapping letters, and let its reset threshold be the length of its shortest synchronizing word. Kisielewicz et al.'s conje…

$O(G)$ conjecture. These equivalent statements hold when $\mathcal{F}$ is the class of all strongly connected graphs.

$O(G)$ conjecture. $O(G)$ is well-defined for every strongly connected graph, although the conjecture does not immediately provide a method for computing it.

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

Bunchy factor conjecture. The barrier to proving the $O(G)$ conjecture is our lack of a sufficiently general method of producing homomorphisms with nontrivial stability relation.

Let $\mathfrak{C}(n)$ be the maximum length of a shortest reset word among all $n$-state synchronizing complete automata, and let $\mathfrak{C}_\mathrm{P}(n)$ be the corresponding…

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…

Linear triple rendezvous-time conjecture. There exists a constant $c$ such that

Exponential core growth conjecture. The core growth rate of $A$ is exponential. Moreover, for every $i\in\mathbb{N}$,

Core growth conjecture. Any invertible strongly synchronizing automaton which generates an infinite group has exponential core growth rate; moreover, the size of the $i$th power of…

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…

For each positive integer $n$, let $\operatorname{sia}(n)$ denote the largest SIA-index among all SIA sets of $n \times n$ stochastic matrices. Linear-growth conjecture. The actual…