6
$\begingroup$

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?

$\endgroup$

2 Answers 2

10
$\begingroup$

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.

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .