Tilings and submonoids of metabelian groups. (Q633769)

This excellent paper starts with a detailed motivation by considering the definitions of \textit{word problems, (uniform) generalized word problem, (uniform) submonoid membership problem, rational subset membership problem} over a group \(G\). In the first section, the authors also present some examples and the connections on known groups with references. As the authors depict in this paper, N. S. Romanovskii (1974, 1980) showed that all finitely generated metabelian groups have a decidable generalized word problem. This result is the starting point of the theory of this paper since, after that, it is natural to ask whether all (finitely generated) metabelian groups have decidable submonoid and rational subset membership problems. Therefore the authors establish that the membership problem is undecidable for a fixed finitely generated submonoid of the free metabelian group of rank 2 and for the wreath product of \(\mathbb Z\) by \(\mathbb Z\times\mathbb Z\). The proof of the second part contains a reduction of the problem via a direct encoding of a Turing machine. Finally they show that membership in rational subsets of the wreath product of \(\mathbb Z/n\mathbb Z\) by \(\mathbb Z\times\mathbb Z\) (which is a metabelian group) is undecidable. As a reader, I must confess that this paper gave me so much new material that can be studied as a future project.