133 problems

A group is poly-context-free if its word problem is a finite intersection of context-free languages. A group has arbitrarily large finite subgroups if it contains finite subgroups…

A group is product separable if, for every finite collection of finitely generated subgroups $H_1,\ldots,H_k$, the product $H_1\cdots H_k$ is closed in the profinite topology. Pin–…

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

Let $cmathcal{L}$ be a language over an alphabet $cmathcal{A}$, and let … be the set of words infinitely extendable in both directions. A language has the Restivo--Salemi property…

Let $F_m$ be a free group of rank $m$, let $H<F_m$ be a subgroup, and let $\Gamma_H(z)$ denote its cogrowth series for $z\in\mathbb{C}$. The rational cogrowth series conjecture. Th…

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…

Holt–Rees–Röver–Thomas conjecture. The class $co\mathcal{CF}$ is not closed under taking free products; specifically,

Soluble poly-context-free group conjecture. Every finitely generated soluble group is poly-context-free if and only if it is virtually abelian.

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…

Let $P$ denote the set of ${\cal P}$-positions in single-hop Peg Duotaire. A language is context-free if it is generated by a context-free grammar. Single-hop context-freeness conj…

A position in single-hop Peg Duotaire has a nim-value, namely the Grundy value of the associated impartial game position. Unbounded-nim-value conjecture. There are positions in sin…

Let $P$ and $N$ denote the sets of ${\cal P}$-positions and ${\cal N}$-positions, respectively, in single-hop Peg Duotaire. A language is regular if it is recognized by a finite-st…

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…

In duotaire, an impartial two-player peg-solitaire game, players take turns jumping pegs, and the winner is determined by normal play. The source states that the complexity of this…

P versus PSPACE conjecture. It is widely conjectured that

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 $F$ be a free group with a generating set $4\Sigma4$ partitioned into a visibly pushdown alphabet. The $4\mathbf{VPL}^\exists4$ membership problem asks whether a given element…

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.

Openness-linearity conjecture. The notion of openness may be related to linearity.

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…