Can the context-sensitivity of word problem in group $G$ be equivalently characterised through some structural properties of $G$?

33 Views Asked by At

Suppose $G$ is a finitely generated group, $A$ is a finite set of generators of $G$. Define $\pi: (A \cup A^{-1})^* \to G$ using the following recurrence:

$$\pi(\Lambda) = e$$ $$\pi(a \alpha) = a\pi(\alpha)$$

Now define the language $L(G, A) := \{w \in (A \cup A^{-1})^*| \pi(w) = e\}$.

It seems, that position of $L$ in Chomsky hierarchy uniquely depends on some structural properties of $G$. There are the following three theorems about that:

Anisimov theorem

$L(A, G)$ is regular (type 3 in Chomsky hierarchy) iff $G$ is finite.

Muller-Shupp theorem

$L(A, G)$ is context-free (type 2 in Chomsky hierarchy) iff $G$ is virtually free.

Higman theorem

$L(A, G)$ is recursively enumerable (type 0 in Chomsky hierarchy) iff $G$ is isomorphic to a subgroup of a finitely presented group.

You may have already noticed that something (and, to be exact, context-sensitive languages - type 1 in Chomsky hierarchy) is missing from the list. My question is:

Can the condition of context-sensitivity of $L(G, A)$ also be equivalently characterised through some group-theoretic properties of $G$.