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?


2 Answers 2


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.

  • 1
    $\begingroup$ thank you for this beautiful answer. is there a similar argument for context-free case? $\endgroup$
    – Sh.M1972
    Mar 1, 2014 at 20:40
  • $\begingroup$ this can be a good question for the combinatorial group theory exam. $\endgroup$
    – Sh.M1972
    Mar 1, 2014 at 20:53
  • $\begingroup$ 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! $\endgroup$
    – Derek Holt
    Mar 1, 2014 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.


Your Answer

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

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