Decidability of the membership problem for 2 2 integer matrices

DOI10.1137/1.9781611974782.12zbMATH Open1410.68245arXiv1604.02303OpenAlexW4253531212MaRDI QIDQ4575747FDOQ4575747

Authors: Igor Potapov, Pavel Semukhin 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: The main result of this paper is the decidability of the membership problem for $2imes2$ nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular $2imes2$ integer matrices $M_1,dots,M_n$ and $M$ decides whether $M$ belongs to the semigroup generated by $M_1,dots,M_n$. Our algorithm relies on a translation of the numerical problem on matrices into combinatorial problems on words. It also makes use of some algebraical properties of well-known subgroups of $mathrmGL(2,mathbbZ)$ and various new techniques and constructions that help to limit an infinite number of possibilities by reducing them to the membership problem for regular languages.

Full work available at URL: https://arxiv.org/abs/1604.02303

Recommendations

• scientific article; zbMATH DE number 7204378
• Some decision problems on integer matrices
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• On the computational complexity of matrix semigroup problems
• Mortality Problem for 2×2 Integer Matrices

Mathematics Subject Classification ID

Matrices of integers (15B36) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15) Free semigroups, generators and relations, word problems (20M05)

Cited In (24)

• Developments in Language Theory
• On Nonnegative Integer Matrices and Short Killing Words
• Some decision problems on integer matrices
• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
• On Affine Reachability Problems
• On finite monoids over nonnegative integer matrices and short killing words
• On undecidability bounds for matrix decision problems
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Title not available (Why is that?)
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• Quantum temporal logic and reachability problems of matrix semigroups
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• Reachability problems for one-dimensional piecewise affine maps
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• The Synchronizing Probability Function for Primitive Sets of Matrices
• On the membership of invertible diagonal and scalar matrices
• Semigroup intersection problems in the Heisenberg groups
• Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2,\mathbb{Q})\) and singular matrices
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• Title not available (Why is that?)
• A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices
• On the decidability of membership in matrix-exponential semigroups

This page was built for publication: Decidability of the membership problem for \(2\times 2\) integer matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575747)