2013/07/31 by Volker Diekert, A. Weiss, Diekert, Volker +1
Computer Science · Mathematics · #05C25 #20E08 #20F10 #20F65 #68Q42 #68Q45 #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1307.8297
openalex publication_date 2013/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.