Symposium on Discrete Algorithms · 2017 · 15 citations · 15 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationGroup TheoryMatrix ComputationNumber-theoretic AlgorithmsRegular LanguagesComputational Matrix TheoryDecidability ProblemsEmptiness ProblemIntersection With Regular LanguagesMembership Problem
The main result of this paper is the decidability of the membership problem for 2 × 2 nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular 2 × 2 integer matrices M1, . . . , Mn and M decides whether M belongs to the semigroup generated by {M1, . . . , Mn}. Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words. It also makes use of some algebraic properties of well-known subgroups of GL(2, ℤ) and various new techniques and constructions that help to convert matrix equations into the emptiness problem for intersection of regular languages.
15
Unsolvability in 3 × 3 Matrices
Michael S. Paterson · Studies in Applied Mathematics · 1970 · 146 citations
Polynomial-time algorithm for the orbit problem
Ramachandran Kannan, R.J. Lipton · Journal of the ACM · 1986 · 94 citations · Full text
Decidable and Undecidable Problems about Quantum Automata
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran et al. · SIAM Journal on Computing · 2005 · 83 citations · Full text