# Deterministic context-free languages that can be represented as the word problem of a group

Consider a group $G$. We call $G$ virtually free is it contains a free subgroup of finite index.

If $G$ is finitely generated by some set $X \subseteq G$ one can consider the word problem $WP(G)$ that is the formal language consisting of all words over the alphabet $X \cup X^{-1}$ that evaluate to the unit in $G$.

It is a famous result by Mueller and Schupp that the $WP(G)$ is context-free if and only if $G$ is virtually free.

It is also known that if $WP(G)$ is context-free, it is deterministic context-free.

My question is: Do we know more about how the class of deterministic context-free languages that can be represented as the word problem of some group, is contained in the class of all (deterministic) context-free languages?

• Are you just asking whether there exists a DCFL that is not the WP of some group? Or something more general? – Joshua Grochow Jan 11 '18 at 16:35
• No not in particular; but do you have a DCFL in mind that is not the WP of some group? For example: The WP of any free group is a DCFL and is solvable in logspace (Lipton, Zalcstein, 1977). Maybe there are more connections between WP of groups and DCFL solvable in logspace. But again, nothing in particular. – dtell Jan 11 '18 at 17:16
• For that above question, I believe $\{a^nb^m \mid m < n\}$ is not the WP of some group. I guess you'd be quite interested in Greibach's hardest language, and her notion of jump PDAs. – Michaël Cadilhac Jan 12 '18 at 9:45
• Maybe the class of languages DLOGTIME-reducible to some WP(G) would be more robust. – Emil Jeřábek supports Monica Jan 12 '18 at 10:47
• @MichaëlCadilhac Thank you. This answer of yours is also very interesting. – dtell Jan 12 '18 at 10:58