On the mortality problem for matrices of low dimensions

Olivier Bournez 1 Michael Branicky
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we discuss the existence of an algorithm to decide if a given set of $2 × 2$ matrices is mortal. A set $F=s ¼,A_ms>$ of square matrices is said to be \motnouv{mortal} if there exist an integer $k >³ 1$ and some integers $i_1,i_2,>¼,i_k >Î s <1, >¼, ms>$ with $A_{i_1} A_{i_2} s~ A_{i_k}=0$. We survey this problem and propose some new extensions. We prove the problem to be BSS-undecidable for real matrices and Turing-decidable for two rational matrices. We relate the problem for rational matrices to the entry-equivalence problem, to the zero-in-the-corner problem, and to the reachability problem for piecewise-affine functions. Finally, we state some NP-completeness results.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2002, 35 (4), pp.433-448
Liste complète des métadonnées

https://hal.inria.fr/inria-00100725
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:50:02
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57

Identifiants

  • HAL Id : inria-00100725, version 1

Collections

Citation

Olivier Bournez, Michael Branicky. On the mortality problem for matrices of low dimensions. Theory of Computing Systems, Springer Verlag, 2002, 35 (4), pp.433-448. 〈inria-00100725〉

Partager

Métriques

Consultations de la notice

99