We consider membership problems for rational subsets of the semigroup of $2\times 2$ matrices over $\mathbb{ Q}$. For a semigroup $M$, the rational subsets $\mathrm{ Rat}(M)$ are defined as the sets accepted by NFAs whose transitions are labeled by elements of $M$. In general, it is undecidable on inputs $m\in M$ and $R\in \mathrm{ Rat}(M)$ whether $m$ belongs to $R$. Therefore, we restrict our attention to the family $\mathrm{ FRat}(M,S)$ of flat rational subsets of $M$ over $S$, where $S$ is a subsemigroup of $M$. It consists of finite unions of the form $g_0L_1g_1 \cdots L_tg_t$, where $L_i\in \mathrm{ Rat}(S)$ and $g_i\in M$. Assuming that the membership for $\mathrm{ Rat}(S)$ is decidable, we prove various results when the membership for $\mathrm{ FRat}(M,S)$ is decidable. If $H$ is a subgroup of a group $G$, then we provide a rather general condition when $\mathrm{ FRat}(G,H)$ is an (effective) relative Boolean algebra. This leads to one of our main results that the emptiness problem for Boolean combinations of sets in $\mathrm{ FRat}(\mathrm{ GL}(2,\mathbb{ Q}),\mathrm{ GL}(2,\mathbb{ Z}))$ is decidable. It is possible that this result cannot be pushed any further as indicated by the following dichotomy: if $G$ is a finitely generated group such that $\mathrm{ GL}(2,\mathbb{ Z}) < G < \mathrm{ GL}(2,\mathbb{ Q})$, then either $G\cong \mathrm{ GL}(2,\mathbb{ Z})\times \mathbb{ Z}^k$ or $G$ contains an extension of the Baumslag-Solitar group $\mathrm{ BS}(1,q)$ of infinite index. It is open whether the membership for rational subsets is decidable in the latter case. For singular matrices, we will show that the membership problem for $\mathrm{ FRat}(\mathbb{ Q}^{ 2\times 2},S)$ is decidable in doubly exponential time, where $S$ is the monoid generated by $\mathrm{ GL}(2,\mathbb{ Z})\cup \{ r\in \mathbb{ Q}\,\mid\,r>1\} \cup \{ 0,\left(\begin{ smallmatrix}1 & 0\\ 0 & 0\end{ smallmatrix}\right)\}$.
Categories: cs.FL