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 complexitydecidabilityNP-hardmatrix semigroupssubset sum problemidentity problem

Mathematics Subject Classification ID

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

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

(21)

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

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)