On the computational complexity of matrix semigroup problems
From MaRDI portal
Publication:2893294
zbMATH Open1242.68120MaRDI QIDQ2893294FDOQ2893294
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
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
Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05)
Cited In (21)
- Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
- On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
- Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
- Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
- Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
- 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
- Linear complexity algorithm for semiseparable matrices
- Weighted automata on infinite words in the context of attacker-defender games
- The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
- REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
- Complexity of the identity checking problem for finite semigroups.
- Reachability problems in quaternion matrix and rotation semigroups
- Relations in the semigroup of \(2\times 2\) upper-triangular matrices
- Reachability Problems in Quaternion Matrix and Rotation Semigroups
- On generic complexity of the subset sum problem for semigroups of integer matrices
- Weighted automata on infinite words in the context of attacker-defender games
- Semigroup intersection problems in the Heisenberg groups
- On Reachability Problems for Low-Dimensional Matrix Semigroups
- Title not available (Why is that?)
- On the decidability of membership in matrix-exponential 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)
