When is a pair of matrices mortal?

DOI10.1016/S0020-0190(97)00123-3zbMATH Open1337.68123OpenAlexW2021238565MaRDI QIDQ290262FDOQ290262

Vincent D. Blondel, John N. Tsitsiklis

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 complexitydecidabilitytheory of computationmatrix theoryPost correspondence problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Markov Decision Processes
• The boundedness of all products of a pair of matrices is undecidable
• A note on Post's correspondence problem
• Recursive Solvability of Problems with Matrices
• Unsolvability in 3 × 3 Matrices

Cited In (34)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290262)