Tilings and Submonoids of Metabelian Groups

Abstract

In this paper we show that membership in finitely generated submonoids is undecidable for the free metabelian group of rank 2 and for the wreath product $\mathbb{Z}\wr (\mathbb{Z}\times \mathbb{Z})$. We also show that subsemimodule membership is undecidable for finite rank free $(\mathbb{Z}\times \mathbb{Z})$-modules. The proof involves an encoding of Turing machines via tilings. We also show that rational subset membership is undecidable for two-dimensional lamplighter groups.