Context-Free Groups and Bass-Serre Theory
Authors:
Preprint
Abstract
The word problem of a finitely generated group is the formal language of words over the generators which are equal to the identity in the group. If this language happens to be context-free, then the group is called context-free. Finitely generated virtually free groups are context-free. In a seminal paper Muller and Schupp showed the converse: A context-free group is virtually free. Over the past decades a wide range of other characterizations of context-free groups have been found. The present notes survey most of these characterizations. Our aim is to show how the different characterizations of context-free groups are interconnected. Moreover, we present a self-contained access to the Muller-Schupp theorem without using Stallings' structure theorem or a separate accessibility result. We also give an introduction to some classical results linking groups with formal language theory.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- A characterisation of virtually free groupsArchiv der Mathematik, 2007
- The monadic second order logic of graphs VI: on several representations of graphs by relational structuresDiscrete Applied Mathematics, 1994
- Vertex-Transitive Graphs and AccessibilityJournal of Combinatorial Theory, Series B, 1993
- Confluent String Rewriting1988
- Investigations on Hotz groups for arbitrary grammarsActa Informatica, 1986
- The accessibility of finitely presented groupsInventiones Mathematicae, 1985
- Groups, the Theory of ends, and context-free languagesJournal of Computer and System Sciences, 1983
- On the Hotz group of a context-free grammarActa Informatica, 1982
- Some algorithmic problems for groups and context-free languagesCybernetics and Systems Analysis, 1974
- Ueber Aufstellung und Untersuchung von Gruppe und Irrationalit t regul rer Riemann'scher Fl chenMathematische Annalen, 1880