On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond

DOI10.1016/j.ic.2021.104736OpenAlexW3129328269MaRDI QIDQ2051775

Pavel Semukhin, Paul C. Bell, Igor Potapov

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.10188

zbMATH Keywords

matrix equationsBaker's theoremlinear recurrence sequencesmortality problemprimary decomposition theoremSkolem's problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

On eventual non-negativity and positivity for the weighted sum of powers of matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Products of matrices and recursively enumerable sets
• On NFAs where all states are final, initial, or both
• Occurrence of zero in a linear recursive sequence
• A simple proof of the Skolem-Mahler-Lech theorem
• Factoring polynomials with rational coefficients
• Complexity of stability and controllability of elementary hybrid systems
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• A note on recurring series
• Mortality for 2 ×2 Matrices Is NP-Hard
• On the Complexity of the Orbit Problem
• On the abc conjecture in algebraic number fields
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• An Exact Method for Finding the Roots of a Complex Polynomial
• Decidability of the Membership Problem for 2 × 2 integer matrices
• The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete
• Markov Chains and Unambiguous Büchi Automata
• Solvability of Matrix-Exponential Equations
• Decision Problems for Linear Recurrence Sequences
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• On the Positivity Problem for Simple Linear Recurrence Sequences,
• Rational subsets of unitriangular groups
• Mathematical Foundations of Computer Science 2004
• Decidable and Undecidable Problems about Quantum Automata
• On Termination of Integer Linear Loops
• Positivity Problems for Low-Order Linear Recurrence Sequences
• Mortality Problem for 2×2 Integer Matrices
• Unsolvability in 3 × 3 Matrices
• Algorithms in real algebraic geometry
• Deciding stability and mortality of piecewise affine dynamical systems