73 problems

Černý's conjecture. Every synchronizing automaton with $n$ states admits a reset word of length at most …

Bunchy factor conjecture. Every strongly connected graph has a bunchy synchronizing factor.

Rank conjecture. If the word problem of $H$ is accepted by a $2k$-counter or $(2k+1)$-counter Cho automaton, then $H$ is virtually free abelian of rank $k$.

Counter-bound conjecture. The former bound is tight, while the latter bound can be strengthened.

Let $\mathbb Z^2$ be the free abelian group of rank $2$, and let its word problem be the language of words over a finite generating set that represent the identity element of…

Fixed-degree counting conjecture. The counting problem … is $\#P$-complete on the class of primitive $k$-out graphs, and remains $\#P$-complete for fixed out-degree $k$, already fo…

P versus PSPACE conjecture. It is widely conjectured that

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.

Let $P$ be a univariate Laurent polynomial and let $p$ be prime. For the constant term sequence $A_p(n)=\operatorname{ct}[P^n]\bmod p$, suppose there exists some $n\in\mathbb{N}$ s…

Transducer measurability conjecture. There is a $\sigma$-algebra on $I \mathrel{\triangleright} O$ that, among other things, would allow one to define maps in the other direction,…

Let $\mathbf{mt}_{\mathrm{d}}(n,m)$ denote the maximum, over deterministic finite automata with $n$ states and an alphabet of size $m$, of the length of their shortest mortal word.…

Let a string machine be composed only of finite-state transducers, with the input and output categories of each transducer being tape categories. Suppose it has one free input…

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…

Fix an integer base $b\geq 2$. A real number is generated by a finite automaton if its $b$-ary expansion is produced by a finite automaton. The Cobham–Loxton–van der Poorten conjec…

Let $\mathcal{A}$ be an $\omega$-categorical structure. A definable ultra-automaton is an ultra-automaton whose transition data are definable in the associated theory. For a langua…

Let $\bbB$ be a bicategory. Recall that automata in the Kleisli category of the powerset monad model nondeterministic automata in $\operatorname{Set}$, and that the presheaf constr…

Let $T$ be a monad on $\operatorname{Set}$ and let $\mathcal{V}$ be a quantale. Write $T\mathcal{V}\operatorname{Prof}$ for the locally thin bicategory associated with…