Decidability of the membership problem for 2 2 integer matrices

DOI10.1137/1.9781611974782.12MaRDI QIDQ4575747zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(32)

• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• On undecidability bounds for matrix decision problems
• Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
• Reachability problems for one-dimensional piecewise affine maps
• scientific article; zbMATH DE number 1089735 (Why is no real title available?)
• Some decision problems on integer matrices
• On the correlation of symmetric functions
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices
• On Nonnegative Integer Matrices and Short Killing Words
• Generic complexity of the membership problem for semigroups of integer matrices
• On Affine Reachability Problems
• On finite monoids over nonnegative integer matrices and short killing words
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• scientific article; zbMATH DE number 7204378 (Why is no real title available?)
• A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices
• On the decidability of membership in matrix-exponential semigroups
• Developments in Language Theory
• The Synchronizing Probability Function for Primitive Sets of Matrices
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• Quantum temporal logic and reachability problems of matrix semigroups
• Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2,\mathbb{Q})\) and singular matrices
• Semigroup intersection problems in the Heisenberg groups
• On the intersection problem for quantum finite automata
• Membership problems in infinite groups
• On strongest algebraic program invariants
• Subgroup membership in GL\((2,\mathbb{Z})\)
• Monoids of upper triangular matrices over the Boolean semiring
• On some decision problems on quantum automata
• On the membership of invertible diagonal and scalar matrices

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)