MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as: $$G=\langle A: L\rangle ?$$ Is there a reference text or article on this type of groups?

share|cite|improve this question
up vote 10 down vote accepted

Finitely presented group?

In a regular expression defining $L$, any starred term must represent the identity in $G$. For example if $uv*w$ defines a set of relators, then $v = v^2 = u^{-1}w^{-1}$. So we can remove any starred term from the regular expression and replace it by the term itself: i.e. replace $uv*w$ by $uw \vee v$. So we can get rid of all the stars in the regular expression and end up with an expression defining a finite set.

Added later: M. Shahyari has now shown that a group with a presentation $\langle X: L \rangle$ with $L$ context-free must also be finitely presentable. It might be of interest to note that the group ${\mathbb Z} \wr {\mathbb Z}$, which is a standard example of a group that is not finitely presentable, has a presentation in which $X = \{ x,y \}$ and $L = \{ y^{-n}xy^nxy^{-n}x^{-1}y^nx^{-1} : n \in {\mathbb Z}\}$, which is of course not context-free.

share|cite|improve this answer
$u^{-1}w^{-1}$, you mean? – The Masked Avenger Mar 1 '14 at 20:37
thank you for this beautiful answer. is there a similar argument for context-free case? – M. Shahryari Mar 1 '14 at 20:40
this can be a good question for the combinatorial group theory exam. – M. Shahryari Mar 1 '14 at 20:53
@TheMaskedAvenger thanks - I've corrected it. – Derek Holt Mar 1 '14 at 20:53
I am not sure about a context-free set of defining relators. The Pumping Lemma for context-free languages seems to imply that long relators would lead to simplification, but I am too tired to think about it now! – Derek Holt Mar 1 '14 at 21:18

By the comment of Derek Holt we can argue for the context-free case as follows:

For any $s\in \Sigma^{\ast}$, let $|s|$ denotes the length of $s$ in the monoid $\Sigma^{\ast}$. By the pumping lemma, there exists a $p\geq 1$ such that for any $s\in L$ with $|s|\geq p$ we have $s=uvxyz$, $u, y\neq 1$ and $|vxy|\leq p$ and for all $i\geq 0$, $uv^ixy^iz\in L$. If we let $i=0$, then in $G$, we have $uxz=1$, and hence for any $i\geq 0$, $$ z^{-1}x^{-1}v^ixy^iz=1$$ which is equivalent to $x^{-1}vxy=1$. Hence every relation $s=1$ with $|s|\geq p$ can be replaced by a relation of the form $x^{-1}vxy=1$. Note that $|x^{-1}vxy|\leq p+1$ and hence $$G=\langle A: s\in L, |s|\leq p+1\rangle$$ so $G$ is f.p.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.