Name
Abstract | ||
|---|---|---|
A set of matrices over the integers is said to be k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be mortal if it is k-mortal for some flnite k. We show that the problem of deciding whether a pair of 48£ 48 integer matrices is mortal is undecidable, and that the problem of deciding, for a given k, whether a pair of matrices is k-mortal is NP -complete. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0020-0190(97)00123-3 | Inf. Process. Lett. |
Keywords | Field | DocType |
post's correspondence problem.,decidability,theory of computation,matrix theory,computational complexity,matrices mortal,correspondence problem | Integer,Discrete mathematics,Combinatorics,Matrix calculus,Zero matrix,Matrix (mathematics),Decidability,Integer matrix,Matrix multiplication,Mathematics,Undecidable problem | Journal |
Volume | Issue | ISSN |
63 | 5 | 0020-0190 |
Citations | PageRank | References |
33 | 6.13 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent D. Blondel | 1 | 1880 | 184.86 |
| John N. Tsitsiklis | 2 | 5300 | 621.34 |
| decision systems | 3 | 159 | 34.45 |