Diekert, Volker, Potapov, Igor and Semukhin, Pavel
(2019)
Decidability of membership problems for flat rational subsets of
$\mathrm{GL}(2,\mathbb{Q})$ and singular matrices.
In: ISSAC '20: International Symposium on Symbolic and Algebraic Computation.
|
Text
1910.02302v1.pdf - Submitted version Download (548kB) | Preview |
Abstract
We consider membership problems for rational sets in matrix semigroups. For a semigroup $M$, the rational sets $\mathrm{Rat}(M)$ are defined as sets accepted by NFA whose transitions are labeled by elements of $M$. The membership problem asks whether $g\in R$, where $g\in M$ and $R\in \mathrm{Rat}(M)$. In this work, we introduce the notion of flat rational sets: if $M$ is a semigroup and $N$ is its subsemigroup, then flat rational sets of $M$ over $N$ are finite unions of the form $L_0g_1L_1 \cdots g_t L_t$ where all $L_i\in \mathrm{Rat}(N)$ and $g_i\in M$. We show that the emptiness problem for Boolean combinations of flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ over $\mathrm{GL}(2,\mathbb{Z})$ is decidable. It is possible that the above result cannot be pushed any further due to the following dichotomy: if $G$ is a f.g. group such that $\mathrm{GL}(2,\mathbb{Z}) <G\leq\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 of infinite index. In the first case, the membership problem for rational subsets of $G$ is decidable. However, in the second case, the decidability of the membership problem has been open for many years. The latter fact has been the driving force to focus on the class of flat rational sets. It appears as a natural restriction that allowed us to prove new decidability results for $2\times 2$ matrices with rational entries. For example, we prove that the membership problem is decidable in exponential time for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ over $\mathrm{GL}(2,\mathbb{Z})$ but becomes decidable in doubly exponential time if we extend $\mathrm{GL}(2,\mathbb{Z})$ by matrices with determinant greater than $1$. We also show doubly exponential time bound for the membership problem for flat rational subsets that include singular matrices.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | 44 pages |
| Uncontrolled Keywords: | cs.FL, cs.FL, 68Q45, 68Q25, 68W30, F.4.3; F.2.1; F.1.1 |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Oct 2019 14:15 |
| Last Modified: | 28 Aug 2023 12:16 |
| DOI: | 10.1145/3373207.3404038 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3058258 |
Dimensions
Dimensions
