When is a pair of matrices mortal?
From MaRDI portal
Publication:290262
DOI10.1016/S0020-0190(97)00123-3zbMath1337.68123MaRDI QIDQ290262
Blondel, Vincent D., John N. Tsitsiklis
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
computational complexity; decidability; matrix theory; theory of computation; Post correspondence problem
68Q25: Analysis of algorithms and problem complexity
03D35: Undecidability and degrees of sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
15B36: Matrices of integers
Related Items
REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS, A survey of computational complexity results in systems and control, A Collatz-type conjecture on the set of rational numbers, Mortality problem and affine automata, Examples of undecidable problems for 2-generator matrix semigroups, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate, The boundedness of all products of a pair of matrices is undecidable, Analytic expansions of max-plus Lyapunov exponents., On undecidability bounds for matrix decision problems, Monomial reachability and zero controllability of discrete-time positive switched systems, Improved matrix pair undecidability results, PERIODIC SEQUENCES OF ARBITRAGE: A TALE OF FOUR CURRENCIES, On the decidability of semigroup freeness, UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, Post Correspondence Problem and Small Dimensional Matrices
