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.
[1] Let G be a finitely generated group with a finite marked generating set X, that is a set X together with the map
extends to a surjective monoid homomorphism, still denoted by
is the identity element of G. That is, if G is given by a presentation
consists of all words over the alphabet
in G. A group G is said to be virtually free if there exists a subgroup of finite index H in G such that H is isomorphic to a free group.
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.
[2] The modern formulation of the Muller–Schupp theorem is as follows:[3] Let G be a finitely generated group with a finite marked generating set X.
The exposition in this section follows the original 1983 proof of Muller and Schupp.
[1] Suppose G is a finitely generated group with a finite generating set X such that the word problem
One first observes that for every finitely generated subgroup H of G is finitely presentable and that for every finite marked generating set Y of H the word problem
In particular, for a finitely generated group the property of having context word problem does not depend on the choice of a finite marked generating set for the group, and such a group is finitely presentable.
Muller and Schupp then show, using the context-free grammar for the language
of G with respect to X is K-triangulable for some integer K>0.
This means that every closed path in
can be, by adding several ``diagonals", decomposed into triangles in such a way that the label of every triangle is a relation in G of length at most K over X.
They then use this triangulability property of the Cayley graph to show that either G is a finite group, or G has more than one end.
Hence, by a theorem of Stallings, either G is finite or G splits nontrivially as an amalgamated free product
are again finitely generated groups with context-free word-problem, and one can apply the entire preceding argument to them.
Since G is finitely presentable and therefore accessible,[4] the process of iterating this argument eventually terminates with finite groups, and produces a decomposition of G as the fundamental group of a finite graph-of-groups with finite vertex and edge groups.
By a basic result of Bass–Serre theory it then follows that G is virtually free.
The converse direction of the Muller–Schupp theorem is more straightforward.
If G is a finitely generated virtually free group, then G admits a finite index normal subgroup N such that N is a finite rank free group.
Muller and Schupp use this fact to directly verify that G has context-free word problem.