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
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.M1972Commented Mar 1, 2014 at 20:40
-
$\begingroup$ this can be a good question for the combinatorial group theory exam. $\endgroup$– Sh.M1972Commented 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$ Commented 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.