Algorithmic problems for subsemigroups of infinite groups - Dong, R (2023)
This thesis is concerned with several algorithmic problems for subsemigroups of infinite groups. The main objective is to construct algorithms that decide various properties of finitely generated subsemigroups of a given infinite group G (for example, a matrix group). Such problems might not be decidable in general. In fact, they gave rise to some of the earliest undecidability results in algorithmic theory. Nevertheless, when the group G admits additional structures, many algorithmic problems become decidable for its subsemigroups. In this thesis, we study the decidability and the complexity of these algorithmic problems in the cases where G is nilpotent, metabelian, or represented as a low-dimensional matrix group.