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$ Jan 11 '18 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
    Jan 11 '18 at 17:16
  • 2
    $\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$ Jan 12 '18 at 9:45
  • 1
    $\begingroup$ Maybe the class of languages DLOGTIME-reducible to some WP(G) would be more robust. $\endgroup$ Jan 12 '18 at 10:47
  • 1
    $\begingroup$ @MichaëlCadilhac Thank you. This answer of yours is also very interesting. $\endgroup$
    – dtell
    Jan 12 '18 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.