59 problems

Denominator conjecture. For all $k$, the rational generating function $F_k(x)$ can be written as

For every finite alphabet $\Sigma$ and all context-free languages $L,U\subseteq\Sigma^*$, if $L\subseteq U$ and $U\setminus L$ is infinite, then there exists a context-free languag…

Determine asymptotically tight worst-case sample-size bounds for length generalization by transformers whose solutions are expressible in the fragments $\mathsf{C\text{-}RASP}_{+}$…

For every finitely generated group $G$, $G$ has co-context-free word problem if and only if $G$ embeds into Thompson's group $V$. Explicitly, for a finite generating set $X$ of $G$…

Let $V$ be R. Thompson's group, and call a group a $co\mathcal{CF}$ group if and only if it embeds as a finitely generated subgroup of $QAut(\mathscr{T}_{2,c})$. Lehnert's conjectu…

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…

Let $v$ be a string, let $L^m(v)$ denote the length of its shortest grammar, and let $\boldsymbol{\operatorname{MDL}}(v)$ denote the MDL code for $v$. Let $\gamma(n):=n f_1(n)$. Sy…

Let $\Gamma=\langle S\mid R\rangle$ be a group with finite generating set $S$, and let … be its cogrowth series, where $\psi_n$ counts words of length $n$ in the alphabet…

Let $G$ be a group. A set is universally quantified visibly pushdown, written $4\mathbf{VPL}^\forall4$, if it is defined by the corresponding universal visibly pushdown language co…

Schützenberger's conjecture. Every maximal code is commutatively equivalent to a prefix-free code.

A finitely generated group $G$ is co-context-free if its co-word problem is context-free. Thompson's group $V$ is the group of homeomorphisms represented by finite binary tree-pair…

Let $G$ be a non-hyperbolic finitely generated group with generating set $S$, and let $\Gamma(G,S)$ be its Cayley graph. A word is a $(\lambda,\epsilon)$-quasigeodesic when it sati…

Let $G$ be a finitely generated group. For rational $\lambda\geq 1$, real $\epsilon\geq 0$, and a finite generating set $S$, consider the language of $(\lambda,\epsilon)$-quasigeode…

For each integer $n\ge 5$, let ${\bf A}_n$ be the $n$-letter alphabet, ${\bf A}_n^{\omega}$ the set of infinite words over it, ${\bf T}_n$ the class of boundary words, and let…

Hollander's conjecture. If $L$ is regular, there exists $p$ such that the limit

Flatness–word-problem conjecture. $G$ is $\mathbf{C}^\forall$-flat if and only if the word problem of $G$ lies in $\mathbf{C}$.

Let $\Sigma$ be an ordered alphabet and let $w\in\Sigma^*$ be $M$-ambiguous. Write $[w]$ for the $M$-class of $w$. A class is trivially $\mathbb{P}$-distinguishable when it is a si…

A group is poly-context-free if its word problem is a finite intersection of context-free languages. A group is virtually a property if it has a finite-index subgroup with that pro…

A finitely generated group is co-context-free if its word problem's complement is context-free. The co-context-free embedding conjecture. A finitely generated group is co-context-f…

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…

Poly-context-free lattice conjecture. A lattice in the product of trees is poly-context-free if and only if it is reducible.

Constructive automata conjecture. For every context free ${\sf L}_{\mathcal{M}}$ there exists a constructive PDA that decides it. For every context sensitive…

Let $x$ be an irrational real number. Let $G_x$ be a context-free grammar that generates an infinite sequence of Dyck rationals $(s_i)_{i\in\mathbb{N}_{+}}$, and let…

Let $\mathcal{D}_{r_{\text{min}}}$ be the language of minimal Dyck-word representations, and consider augmenting its words with additional notation or productions. Finite-length re…