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 $W\!P(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 $W\!P(G)$ is context-free if and only if $G$ is virtually free.

It is also known that if $W\!P(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?

  • 1
    $\begingroup$ Are you just asking whether there exists a DCFL that is not the WP of some group? Or something more general? $\endgroup$ Commented Jan 11, 2018 at 16:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – dtell
    Commented Jan 11, 2018 at 17:16
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Jan 12, 2018 at 9:45
  • 1
    $\begingroup$ Maybe the class of languages DLOGTIME-reducible to some WP(G) would be more robust. $\endgroup$ Commented Jan 12, 2018 at 10:47
  • 1
    $\begingroup$ @MichaëlCadilhac Thank you. This answer of yours is also very interesting. $\endgroup$
    – dtell
    Commented Jan 12, 2018 at 10:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.