Diekert, V, Potapov, I and Semukhin, P (2024) Decidability of membership problems for flat rational subsets of GL(2,Q) and singular matrices. SIAM Journal on Computing, 53 (6). pp. 1663-1708. ISSN 0097-5397

Preview

Text 2024SIAMfinal_submittion.pdf - Accepted Version Available under License Creative Commons Attribution. Download (893kB) | Preview

Abstract

We consider membership problems for rational subsets of the semigroup of 2×2 matrices over Q. For a semigroup M, the rational subsets 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∈M and R∈Rat(M) whether m belongs to R. Therefore, we restrict our attention to the family 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 g0L1g1⋯Ltgt, where Li∈Rat(S) and gi∈M. Assuming that the membership for Rat(S) is decidable, we prove various results when the membership for FRat(M,S) is decidable. If H is a subgroup of a group G, then we provide a rather general condition when 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 FRat(GL(2,Q),GL(2,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 GL(2,Z)<G<GL(2,Q), then either G≅GL(2,Z)×Zk or G contains an extension of the Baumslag-Solitar group 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 FRat(Q2×2,S) is decidable in doubly exponential time, where S is the monoid generated by GL(2,Z)∪{r∈Q∣r>1}∪{0,(1000)}.

Item Type:	Article
Additional Information:	Decidability of membership problems for flat rational subsets of GL(2,Q) and singular matrices Volker Diekert, Igor Potapov, and Pavel Semukhin SIAM Journal on Computing 2024 53:6, 1663-1708
Uncontrolled Keywords:	Membership problem; finite automata; (flat) rational set; special linear group; general linear group; 0101 Pure Mathematics; 0802 Computation Theory and Mathematics; Computation Theory & Mathematics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	Computer Science and Mathematics
Publisher:	Society for Industrial and Applied Mathematics
SWORD Depositor:	A Symplectic
Date Deposited:	17 Oct 2024 14:43
Last Modified:	12 Dec 2024 14:30
DOI or ID number:	10.1137/22M1512612
URI:	https://researchonline.ljmu.ac.uk/id/eprint/24543

View Item