On the mortality problem for matrices of low dimensions
Identifieur interne : 00A118 ( Main/Merge ); précédent : 00A117; suivant : 00A119On the mortality problem for matrices of low dimensions
Auteurs : Olivier Bournez ; Michael BranickySource :
English descriptors
- KwdEn :
Abstract
In this paper, we discuss the existence of an algorithm to decide if a given set of 2 \times 2 matrices is mortal : a set F={A_1,\dots,A_m} of 2 \times 2 matrices is said to be \motnouv{mortal} if there exist an integer k \ge 1 and some integers i_1,i_2,\dots,i_k \in {1, \ldots, m} with A_{i_1} A_{i_2} \cdots 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 left upper corner problem and to the reachability problem for piecewise affine functions. Finally, we state some NP-completeness results.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 002954
- to stream Crin, to step Curation: 002954
- to stream Crin, to step Checkpoint: 001A84
Links to Exploration step
CRIN:bournez00bLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="267">On the mortality problem for matrices of low dimensions</title></titleStmt><publicationStmt><idno type="RBID">CRIN:bournez00b</idno><date when="2000" year="2000">2000</date><idno type="wicri:Area/Crin/Corpus">002954</idno><idno type="wicri:Area/Crin/Curation">002954</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">002954</idno><idno type="wicri:Area/Crin/Checkpoint">001A84</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">001A84</idno><idno type="wicri:Area/Main/Merge">00A118</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On the mortality problem for matrices of low dimensions</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></author><author><name sortKey="Branicky, Michael" sort="Branicky, Michael" uniqKey="Branicky M" first="Michael" last="Branicky">Michael Branicky</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>computability</term><term>matrices</term><term>mortality</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="1019">In this paper, we discuss the existence of an algorithm to decide if a given set of 2 \times 2 matrices is mortal : a set F={A_1,\dots,A_m} of 2 \times 2 matrices is said to be \motnouv{mortal} if there exist an integer k \ge 1 and some integers i_1,i_2,\dots,i_k \in {1, \ldots, m} with A_{i_1} A_{i_2} \cdots 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 left upper corner problem and to the reachability problem for piecewise affine functions. Finally, we state some NP-completeness results.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00A118 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00A118 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= CRIN:bournez00b
|texte= On the mortality problem for matrices of low dimensions
}}
| This area was generated with Dilib version V0.6.33. |  |