On the computational complexity of matrix semigroup problems

MaRDI QIDQ2893294zbMATH OpenFDO

Authors Paul C. Bell, Igor Potapov

Publication date 20 June 2012

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL http://iospress.metapress.com/content/012gv052505x858r/fulltext.html

zbMATH Keywords

computational complexitydecidabilityidentity problemmatrix semigroupsNP-hardsubset sum problem

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• Some decision problems on integer matrices
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• The Identity Correspondence Problem and Its Applications

Cited in

(22)

• Linear complexity algorithm for semiseparable matrices
• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• Weighted automata on infinite words in the context of attacker-defender games
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• Weighted automata on infinite words in the context of attacker-defender games
• Reachability Problems in Quaternion Matrix and Rotation Semigroups
• Decidability of the membership problem for \(2\times 2\) integer matrices
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices
• On generic complexity of the subset sum problem for semigroups of integer matrices
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• scientific article; zbMATH DE number 7204378 (Why is no real title available?)
• On the decidability of membership in matrix-exponential semigroups
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Semigroup intersection problems in the Heisenberg groups
• Decidability of multiplicative matrix equations and related Diophantine problems
• Complexity of the identity checking problem for finite semigroups.
• Reachability problems in quaternion matrix and rotation semigroups

This page was built for publication: On the computational complexity of matrix semigroup problems

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