Mortality in Matrix Semigroups
Let \(S\) be a finitely generated semigroup of \(3 \times 3\) integer matrices. A semigroup is called mortal if it contains the zero matrix. The problem asking whether the zero matrix is in the semigroup \(S\) is called the mortality problem. The original proof of the undecidablity of the mortality problem of \(3 \times 3\) integer matrices was given by \textit{M. S. Paterson} in Stud. Appl. Math. 49, 105-107 (1970; Zbl 0186.01103). In their note, the authors give a simple proof of this fact, which is derived from the undecidablity of the Post Correspondence Problem.
- Mortality Problem for 2×2 Integer Matrices
- Mortality for 2 2 matrices is NP-hard
- Freeness problem for matrix semigroups of Parikh matrices
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- On undecidability bounds for matrix decision problems
- Positivity of second order linear recurrent sequences
- On the decidability of semigroup freeness.
- Mortality for 2 2 matrices is NP-hard
- Incompleteness theorems, large cardinals, and automata over finite words
- Undecidability bounds for integer matrices using Claus instances
- Recursive Solvability of Problems with Matrices
- Generic complexity of the membership problem for semigroups of integer matrices
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words
- Cocyclic subshifts from Diophantine equations
- Mortality Problem for 2×2 Integer Matrices
- REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
- Many bounded versions of undecidable problems are \textsf{NP}-hard
- Undecidability of the stabilizer and zero-in-the-corner problems for matrix groups
- On the membership of invertible diagonal and scalar matrices
- Positivity of third order linear recurrence sequences
This page was built for publication: Mortality in Matrix Semigroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2764742)