17 problems

Normal-set representation conjecture. If $S$ is a $p$-normal set, then there exists a field $K$ of characteristic $p$ and a $K$-recurrence sequence $a\in K^{\mathbb N}$ such that

Algebraicity criterion. The generalized double Laurent series is algebraic over $\mathbb{F}_q(t,u)$ if and only if: (a) for some positive integers $a$ and $b$,…

Let $T_n$ be the full transformation monoid on an $n$-element set, and let $U_{k,l}$ be the monoid defined above. For a language $L$ over an alphabet of size $2$, write…

For $n e 7$ be an integer, choose coprime integers $k,l e 2$ with $k+l=n$, and let $U{k,l}$ be the transformation monoid defined by the two-cycle permutation construction above. **…

Irvine's conjecture. For every $n\geq 0$,

Let a deterministic finite automaton have $N$ states, and call a finite sequence of actions a reset word if it sends every initial state to the same state. If reset words exist, le…

Let $p$ and $q$ be two multiplicatively independent natural numbers, and let automatic in base $b$ mean that the real number's expansion in base $b$ can be generated by a finite au…

Adaptation conjecture. Some techniques based on density arguments and relaxed finiteness conditions on the syntactic monoid of a selection strategy should be adaptable to positive…

Let $f$ be a rational function with coefficients in $\mathbb{Q}$, and let … be a fine and connected ladder. Consider the CFTP procedure designed to simulate this ladder. Finite-aut…

Long Short-Term Memory (LSTM) architectures are a variety of recurrent neural networks (RNNs). A probabilistic deterministic finite automaton (PDFA) is a finite-state automaton wit…

Fix $n,k\in\mathbb N$ and a pattern $v\in[k]^*$ using $d>1$ distinct letters. Let $M_r$ be the maximal number of states with $d-1$ loops in a simple path in the automaton…

vanishing-coefficient conjecture. There exist $k,r\in\mathbb N$ and a pattern $v\in[k]^*$ such that $d>1$ and $K_r=0$. In that case, there exist $L_r\in\mathbb N$, $L_r<M_r$, and…

Automaton-structure conjecture. The automaton $A_p$ is synchronizing and has the following structure: its initial state is $[c_n^{(p)}]$; it contains two disjoint $p$-cycles,

A critical DFA is a synchronizing deterministic finite automaton whose shortest synchronizing word has length $(n-1)^2$, where $n$ is the number of states. Apart from the basic Čer…

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 $h_x(m)$ be the minimum number of states of a nondeterministic finite automaton accepting $x$ and at most $b^m$ strings of length $\lvert x\rvert$, let…

Algorithm 4 minimality conjecture. Algorithm 4 computes the minimal transition automaton.