<p>Consider a group <span class="math-container">$G$</span>. We call <span class="math-container">$G$</span> virtually free is it contains a free subgroup of finite index.</p>
<p>If <span class="math-container">$G$</span> is finitely generated by some set <span class="math-container">$X \subseteq G$</span> one can consider the <em>word problem</em> <span class="math-container">$W\!P(G)$</span> that is the formal language consisting of all words over the alphabet <span class="math-container">$X \cup X^{-1}$</span> that evaluate to the unit in <span class="math-container">$G$</span>.</p>
<p>It is a famous result by Mueller and Schupp that the <span class="math-container">$W\!P(G)$</span> is context-free if and only if <span class="math-container">$G$</span> is virtually free.</p>
<p>It is also known that if <span class="math-container">$W\!P(G)$</span> is context-free, it is deterministic context-free.</p>
<p>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?</p>

CC BY-SA 3.0
2018-01-11T16:35:23.300Z
Are you just asking whether there exists a DCFL that is *not* the WP of some group? Or something more general?
Joshua Grochow
CC BY-SA 3.0
2018-01-11T17:16:06.617Z
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
CC BY-SA 3.0
2018-01-12T09:45:15.793Z
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
CC BY-SA 3.0
2018-01-12T10:47:48.773Z
Maybe the class of languages DLOGTIME-reducible to some WP(*G*) would be more robust.
Emil Jeřábek
CC BY-SA 3.0
2018-01-12T10:58:07.880Z
@MichaëlCadilhac Thank you. [This answer](https://cstheory.stackexchange.com/a/33887/47835) of yours is also very interesting.
dtell
CC BY-SA 4.0
2019-04-01T20:25:21.277Z
I'm not sure if you're still interested in this, but it is known that such languages are closed under deletion and have universal prefix. This is true for all word problems, not just DCFL. There's a proof here: D. W. Parkes and R. M. Thomas. Groups with context-free reduced word
problem. Communications in Algebra, 30:3143–3156, 2002.
Sam Jones
<fl.formal-languages><gr.group-theory>
Deterministic context-free languages that can be represented as the word problem of a group
dtell
# Deterministic context-free languages that can be represented as the word problem of a group

(Asked by: username_0 on 2018-01-11)

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?

**Tags:** fl.formal-languages, gr.group-theory
> **Comments:**
> **username_1**: Are you just asking whether there exists a DCFL that is *not* the WP of some group? Or something more general?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: Maybe the class of languages DLOGTIME-reducible to some WP(*G*) would be more robust.  
> **username_0**: @MichaëlCadilhac Thank you. [This answer](https://cstheory.stackexchange.com/a/33887/47835) of yours is also very interesting.  
> **username_4**: I'm not sure if you're still interested in this, but it is known that such languages are closed under deletion and have universal prefix. This is true for all word problems, not just DCFL. There's a proof here: D. W. Parkes and R. M. Thomas. Groups with context-free reduced word problem. Communications in Algebra, 30:3143–3156, 2002.  

---

## 0 answers

