Muller–Schupp theorem

In mathematics, the Muller–Schupp theorem states that a finitely generated group G has context-free word problem if and only if G is virtually free. The theorem was proved by David Muller and Paul Schupp in 1983.

Word problem for groups

Let G be a finitely generated group with a finite marked generating set X, that is a set X together with the map

π

:

X

→

G

{\displaystyle \pi :X\to G}

such that the subset

π

(

X

)

⊆

G

{\displaystyle \pi (X)\subseteq G}

generates G. Let

Σ

X

:=

X

⊔

X

−

1

{\displaystyle \Sigma _{X}:=X\sqcup X^{-1}}

be the group alphabet and let

Σ

X

∗

{\displaystyle \Sigma _{X}^{\ast }}

be the free monoid on

Σ

X

,

{\displaystyle \Sigma _{X},}

that is

Σ

X

∗

{\displaystyle \Sigma _{X}^{\ast }}

is the set of all words (including the empty word) over the alphabet

Σ

X

{\displaystyle \Sigma _{X}}

.

The map

π

:

X

→

G

{\displaystyle \pi :X\to G}

extends to a surjective monoid homomorphism, still denoted by

π

{\displaystyle \pi }

,

π

:

Σ

X

∗

→

G

{\displaystyle \pi :\Sigma _{X}^{\ast }\to G}

.

The word problem

W

(

G

,

X

)

{\displaystyle {\mathcal {W}}(G,X)}

of G with respect to X is defined as

W

(

G

,

X

)

:=

{

w

∈

Σ

X

∗

∣

π

(

w

)

=

e

in

G

}

,

{\displaystyle {\mathcal {W}}(G,X):=\{w\in \Sigma _{X}^{\ast }\mid \pi (w)=e{\text{ in }}G\},}

where

e

∈

G

{\displaystyle e\in G}

is the identity element of G.

That is, if G is given by a presentation

G

=

⟨

X

∣

R

⟩

{\displaystyle G=\langle X\mid R\rangle }

with X finite, then

W

(

G

,

X

)

{\displaystyle {\mathcal {W}}(G,X)}

consists of all words over the alphabet

X

⊔

X

−

1

{\displaystyle X\sqcup X^{-1}}

that are equal to

e

{\displaystyle e}

in G.

Virtually free groups

A group G is said to be virtually free if there exists a subgroup of finite index which is free. If G is a finitely generated virtually free group then if H is a free subgroup of finite index in G, H itself is finitely generated. Thus H is free of finite rank. The trivial group is viewed as the free group of rank 0, and thus all finite groups are virtually free.

A basic result in Bass–Serre theory says that a finitely generated group G is virtually free if and only if G splits as the fundamental group of a finite graph of finite groups.

Precise statement of the Muller–Schupp theorem

The modern formulation of the Muller–Schupp theorem is as follows:

Let G be a finitely generated group with a finite marked generating set X. Then G is virtually free if and only if

W

(

G

,

X

)

{\displaystyle {\mathcal {W}}(G,X)}

is a context-free language.