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.David E. Muller, and Paul E. Schupp
''Groups, the theory of ends, and context-free languages''.

Journal of Computer and System Sciences 26 (1983), no. 3, 295–310

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 $\pi:X\to G$ such that the subset $\pi(X)\subseteq G$ generates ''G''. Let $\Sigma_X:=X\sqcup X^$ be the group alphabet and let $\Sigma_X^\ast$ be the free monoid on $\Sigma_X,$ that is $\Sigma_X^\ast$ is the set of all words (including the empty word) over the alphabet $\Sigma_X$.
The map $\pi: X\to G$ extends to a surjective monoid homomorphism, still denoted by $\pi$, $\pi: \Sigma_X^\ast\to G$.
The ''word problem'' $\mathcal W(G,X)$ of ''G'' with respect to ''X'' is defined as
:$\mathcal W(G,X):= \,$
where $e\in G$ is the identity element of ''G''.

That is, if ''G'' is given by a presentation $G=\langle X\mid R\rangle$ with ''X'' finite, then $\mathcal W(G,X)$ consists of all words over the alphabet $X\sqcup X^$ that are equal to $e$ in ''G''.

Virtually free groups

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. If ''G'' is a finitely generated virtually free group and ''H'' is a free subgroup of finite index in ''G'' then ''H'' itself is finitely generated, so that ''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 $\mathcal W(G,X)$ is a context-free language.

Sketch of the proof

The exposition in this section follows the original 1983 proof of Muller and Schupp.

Suppose ''G'' is a finitely generated group with a finite generating set ''X'' such that the word problem $\mathcal W(G,X)$ is a context-free language. 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 $\mathcal W(H,Y)$ is also context-free. 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 $\mathcal W(G,X)$, that the Cayley graph $\Gamma(G,X)$ of ''G'' with respect to ''X'' is ''K-triangulable'' for some integer ''K''>0. This means that every closed path in $\Gamma(G,X)$ 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 $G=A\ast_C B$ or an HNN-extension $G=A\ast_C$ where ''C'' is a finite group. Then $A,B$ 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, 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.

Remarks and further developments

*The Muller–Schupp theorem is a far-reaching generalization of a 1971 theorem of Anisimov which states that for a finitely generated group ''G'' with a finite marked generating set ''X'' the word problem $\mathcal W(G,X)$ is a regular language if and only if the group ''G'' is finite.
*At the time the 1983 paper of Muller and Schupp was published, accessibility of finitely presented groups has not yet been established. Therefore, the original formulation of the Muller–Schupp theorem said that a finitely generated group is virtually free if and only if this group is accessible and has context-free word problem. A 1985 paper of Dunwoody proved that all finitely presented groups are accessible.M. J. Dunwoody
''The accessibility of finitely presented groups''.
Inventiones Mathematicae 81 (1985), no. 3, 449–457 Since finitely generated groups with context-free word problem are finitely presentable, Dunwoody's result together with the original Muller–Schupp theorem imply that a finitely generated group is virtually free if and only if it has context-free word problem (which is the modern formulation of the Muller–Schupp theorem).
* A 1983 paper of Linnell established accessibility of finitely generated groups where the orders of finite subgroups are bounded. It was later observed (see ) that Linnell's result together with the original Muller–Schupp theorem were sufficient to derive the modern statement of the Muller–Schupp theorem, without having to use Dunwoody's result.
* In the case of torsion-free groups, the situation is simplified as the accessibility results are not needed and one instead uses Grushko theorem about the rank of a free product. In this setting, as noted in the original Muller and Schupp paper, the Muller–Schupp theorem says that a finitely generated torsion-free group has context-free word problem if and only if this group is free.
* In a subsequent related paper, Muller and Schupp proved that a ``finitely generated" graph Γ has finitely many end isomorphism types if and only if Γ is the transition graph of a push-down automaton. As a consequence, they show that the monadic theory of a ``context-free" graph (such as the Cayley graph of a virtually free group) is decidable, generalizing a classic result of Rabin for binary trees. Later Kuske and Lohrey proved that virtually free groups are the only finitely generated groups whose Cayley graphs have decidable monadic theory.
* Bridson and Gilman applied the Muller–Schupp theorem to show that a finitely generated group admits a ``broom-like" combing if and only if that group is virtually free.

* Sénizergues used the Muller–Schupp theorem to show that the isomorphism problem for finitely generated virtually free group is primitive recursive.
*Gilman, Hermiller, Holt and Rees used the Muller–Schupp theorem to prove that a finitely generated group ''G'' is virtually free if and only if there exist a finite generating set ''X'' for ''G'' and a finite set of length-reducing rewrite rules over ''X'' whose application reduces any word to a geodesic word.
*Ceccherini-Silberstein and Woess consider the setting of a finitely generated group ''G'' with a finite generating set ''X'', and a subgroup ''K'' of ''G'' such that the set of all words over the alphabet $\Sigma_X$ representing elements of ''H'' is a context-free language.T. Ceccherini-Silberstein, and W. Woess, ''Context-free pairs of groups I: Context-free pairs and graphs''. European Journal of Combinatorics 33 (2012), no. 7, 1449–1466
*Generalizing the setting of the Muller–Schupp theorem, Brough studied groups with poly-context-free word problem, that is where the word problem is the intersection of finitely many context-free languages. Poly-context-free groups include all finitely generated groups commensurable with groups embeddable in a direct product of finitely many free groups, and Brough conjectured that every poly-context-free group arises in this way. Ceccherini-Silberstein, Coornaert, Fiorenzi, Schupp, and Touikan introduced the notion of a multipass automaton, which are nondeterministic automata accepting precisely all the finite intersections of context-free languages. They also obtained results providing significant evidence in favor of the above conjecture of Brough.
*Nyberg-Brodda generalised the Muller-Schupp theorem from groups to ``special monoids", a class of semigroups containing, but strictly larger than, the class of groups, characterising such semigroups with a context-free word problem as being precisely those with a virtually free maximal subgroup.
*Subsequent to the 1983 paper of Muller and Schupp, several authors obtained alternate or simplified proofs of the Muller–Schupp theorem.Y. Antolin, ''On Cayley graphs of virtually free groups'', Groups, Complexity, Cryptology 3 (2011), 301–327V. Diekert, and A. Weiß,
''Context-free groups and their structure trees''. International Journal of Algebra and Computation 23 (2013), no. 3, 611–642

See also

*Infinite tree automaton
*Word problem (mathematics)
*Formal language

References

External links

Context-free groups and their structure trees
expository talk by Armin Weiß

{{DEFAULTSORT:Muller-Schupp theorem
Geometric group theory
Formal languages