When is a pair of matrices mortal?

DOI10.1016/S0020-0190(97)00123-3zbMath1337.68123OpenAlexW2021238565MaRDI QIDQ290262

John N. Tsitsiklis, Blondel, Vincent D.

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00123-3

zbMATH Keywords

computational complexitydecidabilitymatrix theorytheory of computationPost correspondence problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Undecidability and degrees of sets of sentences (03D35) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matrices of integers (15B36)

Related Items (32)

Analytic expansions of max-plus Lyapunov exponents. ⋮ PERIODIC SEQUENCES OF ARBITRAGE: A TALE OF FOUR CURRENCIES ⋮ On the decidability of semigroup freeness ⋮ Improved matrix pair undecidability results ⋮ On the decidability and complexity of problems for restricted hierarchical hybrid systems ⋮ The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate ⋮ On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers ⋮ On Feedback Stabilization of Linear Switched Systems via Switching Signal Control ⋮ Optimization problems involving matrix multiplication with applications in materials science and biology ⋮ Some criteria for spectral finiteness of a finite subset of the real matrix space \(\mathbb R^{d\times d}\) ⋮ Optimal Switching Sequence for Switched Linear Systems ⋮ Lifespan in a primitive Boolean linear dynamical system ⋮ Set of possible values of maximal Lyapunov exponents of discrete time-varying linear system ⋮ A Collatz-type conjecture on the set of rational numbers ⋮ Polytopic uncertainty for linear systems: new and old complexity results ⋮ Flatness and structural analysis as a constructive framework for private communication ⋮ Uniformity of Lyapunov exponents for non-invertible matrices ⋮ Mortality problem and affine automata ⋮ On the Lyapunov exponents of a class of second-order discrete time linear systems with bounded perturbations ⋮ Cocyclic subshifts from Diophantine equations ⋮ On undecidability bounds for matrix decision problems ⋮ A survey of computational complexity results in systems and control ⋮ Monomial reachability and zero controllability of discrete-time positive switched systems ⋮ Continuity properties of the lower spectral radius ⋮ Chaotic behavior of discrete-time linear inclusion dynamical systems ⋮ UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES ⋮ Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability ⋮ Post Correspondence Problem and Small Dimensional Matrices ⋮ Examples of undecidable problems for 2-generator matrix semigroups ⋮ REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS ⋮ The boundedness of all products of a pair of matrices is undecidable ⋮ The ultimate rank of tropical matrices

Cites Work

• Unnamed Item
• Unnamed Item
• A note on Post's correspondence problem
• The boundedness of all products of a pair of matrices is undecidable
• The Complexity of Markov Decision Processes
• Recursive Solvability of Problems with Matrices
• Unsolvability in 3 × 3 Matrices

This page was built for publication: When is a pair of matrices mortal?