On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

DOI10.4230/LIPIcs.MFCS.2019.83OpenAlexW2970521784MaRDI QIDQ5092447

Igor Potapov, Paul C. Bell, Pavel Semukhin

Publication date: 21 July 2022

Full work available at URL: http://doi.org/10.4230/LIPIcs.MFCS.2019.83

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Mortality and Edge-to-Edge Reachability are Decidable on Surfaces

Cites Work

• 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
• 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
• A note on recurring series
• Mortality for 2 ×2 Matrices Is NP-Hard
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• On the Complexity of the Orbit Problem
• On the abc conjecture in algebraic number fields
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• 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 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
• Deciding stability and mortality of piecewise affine dynamical systems