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.[1]

Word problem for groups

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

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

where ${\displaystyle e\in G}$ is the identity element of G.

That is, if G is given by a presentation ${\displaystyle G=\langle X\mid R\rangle }$ with X finite, then ${\displaystyle {\mathcal {W}}(G,X)}$ consists of all words over the alphabet ${\displaystyle X\sqcup X^{-1}}$ that are equal to ${\displaystyle 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.[2]

Precise statement of the Muller–Schupp theorem

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. Then G is virtually free if and only if ${\displaystyle {\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.[1]

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

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 ${\displaystyle {\mathcal {W}}(G,X)}$ is a regular language if and only if the group G is finite.[5]
• 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.[4] 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 [6] established accessibility of finitely generated groups where the orders of finite subgroups are bounded. It was later observed (see [7]) 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,[1] 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.[1]
• 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.[8] 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.[9] Later Kuske and Lohrey[10] proved that virtually free groups are the only finitely generated groups whose Cayley graphs have decidable monadic theory.
• Bridson and Gilman[11] 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[12] 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.[13]
• 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 ${\displaystyle \Sigma _{X}}$ representing elements of H is a context-free language.[14]
• Generalizing the setting of the Muller–Schupp theorem, Brough [15] 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 [16] 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.
• Subsequent to the 1983 paper of Muller and Schupp, several authors obtained alternate or simplified proofs of the Muller–Schupp theorem.[17][14][3]

See also

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

References

1. 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
2. A. Karrass, A. Pietrowski, and D. Solitar, Finite and infinite cyclic extensions of free groups. Journal of the Australian Mathematical Society 16 (1973), 458–466
3. V. Diekert, and A. Weiß, Context-free groups and their structure trees. International Journal of Algebra and Computation 23 (2013), no. 3, 611–642
4. M. J. Dunwoody, The accessibility of finitely presented groups. Inventiones Mathematicae 81 (1985), no. 3, 449–457
5. A.V. Anisimov, Group languages (in Russian), Kibernetika, 4 (1971), pp. 18-24
6. P. A. Linnell, On accessibility of groups. Journal of Pure and Applied Algebra 30 (1983), no. 1, 39–46
7. T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenzi, and P.E. Schupp, Groups, graphs, languages, automata, games and second-order monadic logic. European Journal of Combinatorics 33 (2012), no. 7, 1330–1368
8. D. E. Muller, and P. E. Schupp, The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science 37 (1985), no. 1, 51–75
9. M. O. Rabin, Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society 141 (1969), 1–35
10. D. Kuske, M. Lohrey, Logical aspects of Cayley-graphs: the group case. Annals of Pure and Applied Logic 131 (2005), no. 1–3, 263–286
11. M. Bridson, and R. H. Gilman, A remark about combings of groups. International Journal of Algebra and Computation 3 (1993), no. 4, 575–581
12. G. Sénizergues, On the finite subgroups of a context-free group. Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), 201--212, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, American Mathematical Society, Providence, RI, 1996
13. R. H. Gilman, S. Hermiller, D. Holt, and S. Rees, A characterisation of virtually free groups. Archiv der Mathematik 89 (2007), no. 4, 289–295
14. 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
15. T. Brough, Groups with poly-context-free word problem. Groups, Complexity, Cryptology 6 (2014), no. 1, 9–29
16. T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenzi, P. E. Schupp, and N. Touikan, Multipass automata and group word problems. Theoretical Computer Science 600 (2015), 19-33
17. Y. Antolin, On Cayley graphs of virtually free groups, Groups, Complexity, Cryptology 3 (2011), 301–327

External links

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