2017/02/09 by Meng-Che Ho, Meng-Che "Turbo" Ho, Ho, Meng-Che "Turbo"
Computer Science · Mathematics · #20K15 (Secondary) #68Q45 (Primary) #Computability, Logic, AI Algorithms #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #Group Theory (math.GR) #acm:20K15 #acm:68Q45 #cs.FL #math.GR #msc:20K15 #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1702.02926
openalex publication_date 2017/02/09 · arxiv created 2017/09/01 · arxiv updated 2017/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The word problem of a group G = ⟨ Σ⟩ can be defined as the set of formal words in Σ^* that represent the identity in G. When viewed as formal languages, this gives a strong connection between classes of groups and classes of formal languages. For example, Anisimov showed that a group is finite if and only if its word problem is a regular language, and Muller and Schupp showed that a group is virtually-free if and only if its word problem is a context-free language. Above this, not much was known, until Salvati showed recently that the word problem of ℤ2 is a multiple context-free language, giving first such example. We generalize Salvati's result to show that the word problem of ℤn is a multiple context-free language for any n.