24 problems

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…

Steinberg's conjecture. There is an automaton group whose word problem is ${\mathsf{PSPACE}}$-complete.

Semi-convergence conjecture. Reduction is semi-convergent for every Artin–Tits monoid $M$.

A 3-manifold is a topological manifold of dimension three, and its fundamental group is the group of homotopy classes of based loops in the manifold. Solvable word problem conjectu…

Let $w$ and $w'$ be braid words, and let $l$ denote the length of the longer of the two braid words. Dehornoy's algorithm transforms braid words into reduced forms and decides equa…

Relative permutational Boone--Higman conjecture. Let $\Gamma$ be a finitely generated group with solvable word problem. Then there exists a group $G$ with a type…

Relative Boone--Higman conjecture. Let $\Gamma$ be a finitely generated group with solvable word problem. Then $\Gamma$ sharply embeds in a finitely presented relatively simple gro…

Permutational Boone--Higman conjecture. Every finitely generated group with solvable word problem embeds in a group admitting an action of type $(\operatorname{A}_2)$; equivalently…

Boone--Higman conjecture. Every finitely generated group with solvable word problem embeds in a finitely presented simple group.

Finiteness conjecture. If $G$ has an EDT0L word problem, then $G$ is finite.

Let … Here $I_N$ is the special one-relation inverse monoid associated with the monoid $\Pi_N$. Conjecture on $I_N$. The Dehn function of $I_N$ is at least exponential, and the wor…

Non-positive surface curvature implies solvable word problem. If $\sigma_+(X)\leq 0$ then the word problem is solvable in $\pi_1(X)$.

Dehornoy's Property H conjecture. Every Artin group satisfies Property H.

Let $\mathfrak{A}$ be Adian's procedure, whose indefinite looping is the unresolved case in deciding left divisibility by a letter. An algorithm $\mathfrak{B}$ is the algorithm Adi…

The procedure $\mathfrak{A}$ is Adian's procedure for addressing left divisibility in one-relation monoids; an algorithm is a procedure that always terminates after finitely many s…

Let $\mathcal{C}$ be a class of super-AFL languages closed under reversal. Let $M$ be a finitely presented special monoid generated by $A$, and let $U(M)$ be its group of units wit…

Let $M$ be a finitely presented special monoid, generated by $A$, with virtually free group of units. For inputs $u,v\in A^*$, write $n=|u|+|v|$. Quadratic-time word problem conjec…

Let $G_{k+1}^k$ be one of the groups under consideration, and let $H_k$ be its subgroup generated by $b_1,\dots,b_k$. For distinct indices $i,j,m,l\in\{1,\dots,k\}$, consider the r…

Power word problem reduction conjecture. The method used for free groups should generalize to these groups, and the power word problem for $G$ should be ${\mathsf{AC}}^0$-Turing-re…

EDT0L and ET0L word-problem conjecture. A group has EDT0L word problem if and only if it is finite, and a group has ET0L word problem if and only if it is virtually free.

Let $M$ be an Artin–Tits monoid. A padding of a multifraction is obtained by inserting an even number of trivial components at its beginning; semi-convergence up to $f$-padding mea…

Let $M$ be an Artin–Tits monoid, and let $\mathcal{R}$-reduction be the reduction system on multifractions associated with $M$. Conjecture A. $\mathcal{R}$-reduction is semi-conver…

Let $M$ be an Artin–Tits monoid and let $\mathcal{R}_{M}$ be its reduction system on multifractions. Two multifractions are right reducts of the same multifraction if they are obta…

Let $\langle S,R\rangle$ be an Artin–Tits presentation, let $w\in S\cup S^{-1}$ be a word, and write $\overline{w}$ for the group element represented by $w$. Let…