44 problems

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

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…

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

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…

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…

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

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

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…

Bunchy factor conjecture. For every strongly connected graph $G$,

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

$O(G)$ conjecture. For every strongly connected graph $G$, there is a unique $\leq_S$-minimal graph $O(G)$ satisfying

Let $\beta\geq 2$ be a base. A pair $(a,b)$ is a reversed sum-product pair in base $\beta$ when the sum of $a$ and $b$, written in base $\beta$, is the reversal of the base-$\beta$…

Let $n$ be a positive integer, and consider the Collatz dynamic on odd positive integers. The Golden Automaton is the finite proof system described in the source for establishing C…

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…

Let $\mathcal{M}$ be a strongly pigeonhole class of matroids. Duality conjecture. The class $\{M^{*}\colon M\in\mathcal{M}\}$ is strongly pigeonhole. The preceding result establish…

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…