Groups with multiple context-free word problems
The paper under review provides a self-contained introduction to multiple context-free languages and their applications to group theory.\N\NThis contribution is devoted to the study of a class of groups whose word problems lie in the realm of multiple context-free languages (MCFLs). The investigation builds upon a fundamental observation: different presentations of the same group define different group languages, which are related to each other by rational transductions. A general problem is to understand how algebraic properties of finitely presented or finitely generated groups relate to the language-theoretic properties of their group languages. This question can be addressed by identifying classes of formal languages closed under rational transduction and characterizing the groups whose group languages fall within those classes.\N\NThe class of groups whose group languages are regular coincides with the class of finite groups, while groups whose group languages are context-free correspond to the class of virtually free groups [\textit{D. E. Muller} and \textit{P. E. Schupp}, J. Comput. Syst. Sci. 26 295--310 (1983; Zbl 0537.20011)]. However, the group language of a simple presentation of the free abelian group \(\mathbb{Z}^2\) is not context-free. By \textit{S. Salviati} [J. Comput. Syst. Sci. 81, No. 7, 1252--1277 (2015; Zbl 1325.68133)] it is proved that the word problem of \(\mathbb{Z}^2\) belongs to the class of \(2\)-multiple context-free languages, thus providing a natural example of a non-context-free group language situated within the MCFL hierarchy.\N\NThis chapter surveys such developments and related results and provides a clear and structured exposition of the connections between group theory and formal language theory.\N\NFor the entire collection see [Zbl 1551.20003].
This page was built for publication: Groups with multiple context-free word problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6978672)
