Decidability of the Membership Problem for 2 × 2 integer matrices
From MaRDI portal
Publication:4575747
DOI10.1137/1.9781611974782.12zbMath1410.68245arXiv1604.02303OpenAlexW4253531212MaRDI QIDQ4575747
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
Combinatorics on words (68R15) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Matrices of integers (15B36)
Related Items (13)
Reachability Problems for One-Dimensional Piecewise Affine Maps ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ Unnamed Item ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond ⋮ On finite monoids over nonnegative integer matrices and short killing words ⋮ On Affine Reachability Problems ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond ⋮ On Nonnegative Integer Matrices and Short Killing Words ⋮ The Synchronizing Probability Function for Primitive Sets of Matrices
This page was built for publication: Decidability of the Membership Problem for 2 × 2 integer matrices
