Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices
Volker Diekert, Igor Potapov, Pavel Semukhin · SIAM Journal on Computing · 2024
Abstract. We consider membership problems for rational subsets of the semigroup of [Formula: see text] matrices over [Formula: see text]. For a semigroup [Formula: see text], the rational subsets [Formula: see text] are defined as the sets accepted by nondeterministic finite automatons whose transitions are labeled by elements of [Formula: see text]. In general, it is undecidable on inputs [Formula: see text] and [Formula: see text] whether [Formula: see text] belongs to [Formula: see text]. Therefore, we restrict our attention to the family [Formula: see text] of flat rational subsets of [Formula: see text] over [Formula: see text], where [Formula: see text] is a subsemigroup of [Formula: see text]. It consists of finite unions of the form [Formula: see text], where [Formula: see text] and [Formula: see text]. Assuming that the membership for [Formula: see text] is decidable, we prove various results when the membership for [Formula: see text] is decidable. If [Formula: see text] is a subgroup of a group [Formula: see text], then we provide a rather general condition when [Formula: see text] is an (effective) relative Boolean algebra. This leads to one of our main results that the emptiness problem for Boolean combinations of sets in [Formula: see text] is decidable. It is possible that such a strong decidability result cannot be pushed any further for groups sitting between [Formula: see text] and [Formula: see text]. To support this possibility, we prove the following dichotomy: If [Formula: see text] is a finitely generated group such that [Formula: see text], then either [Formula: see text] or [Formula: see text] contains an extension of the Baumslag–Solitar group [Formula: see text] 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 [Formula: see text] is decidable in doubly exponential time, where [Formula: see text] is the monoid generated by [Formula: see text].