57 problems

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

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

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…

Minimal-spelling grammar conjecture. The language underlying $\text{RPF}_{\mathbb{N}_{r_{\text{min}}}}$ is generated by this context-free grammar. The grammar is ambiguous, with tw…

Let $M=\operatorname{Mon}\langle A\mid w_i=1\ (1\leq i\leq p)\rangle$ be a finitely presented special monoid. A monoid has deterministic context-free word problem when its word pro…

For every $n\geq 2$, let $T_n$ be the threshold language of order $n$, and define its growth rate by … Since $T_n$ is factorial, this limsup can equivalently be replaced by a limit…