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

DOI10.1016/J.IC.2021.104736MaRDI QIDQ2051775zbMATH OpenOpenAlexFDO

Authors Paul C. Bell, Pavel Semukhin, 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, https://drops.dagstuhl.de/opus/volltexte/2019/11027/

zbMATH Keywords

Baker's theoremlinear recurrence sequencesmatrix equationsmortality problemprimary decomposition theoremSkolem's problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• The mortality problem for matrices of low dimensions
• Mortality in Matrix Semigroups
• Mortality Problem for 2×2 Integer Matrices
• More on Mortality

Cites work

• A note on recurring series
• A simple proof of the Skolem-Mahler-Lech theorem
• Algorithms in real algebraic geometry
• An Exact Method for Finding the Roots of a Complex Polynomial
• Complexity of stability and controllability of elementary hybrid systems
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Decidable and Undecidable Problems about Quantum Automata
• Deciding stability and mortality of piecewise affine dynamical systems
• Decision problems for linear recurrence sequences
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 6677405 (Why is no real title available?)
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 3823893 (Why is no real title available?)
• scientific article; zbMATH DE number 4075172 (Why is no real title available?)
• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• scientific article; zbMATH DE number 871949 (Why is no real title available?)
• scientific article; zbMATH DE number 7204378 (Why is no real title available?)
• scientific article; zbMATH DE number 3336831 (Why is no real title available?)
• scientific article; zbMATH DE number 3336895 (Why is no real title available?)
• Markov chains and unambiguous Büchi automata
• Mathematical Foundations of Computer Science 2004
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• Mortality for 2 2 matrices is NP-hard
• Mortality Problem for 2×2 Integer Matrices
• Occurrence of zero in a linear recursive sequence
• On NFAs where all states are final, initial, or both
• On termination of integer linear loops
• On the abc conjecture in algebraic number fields
• On the complexity of the orbit problem
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• On the positivity problem for simple linear recurrence sequences
• On the Skolem problem for continuous linear dynamical systems
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Positivity problems for low-order linear recurrence sequences
• Products of matrices and recursively enumerable sets
• Rational subsets of unitriangular groups.
• Solvability of Matrix-Exponential Equations
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Unsolvability in 3 × 3 Matrices

Cited in

(8)

• On eventual non-negativity and positivity for the weighted sum of powers of matrices
• Mortality in Matrix Semigroups
• Recursive Solvability of Problems with Matrices
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• Completing the picture for the Skolem problem on order-4 linear recurrence sequences
• Decidability of multiplicative matrix equations and related Diophantine problems
• Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices
• The complexity of reachability problems in strongly connected finite automata

This page was built for publication: On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond

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