Geodesic
Some decision problems on integer matrices
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 125-131

Voir la notice de l'article provenant de la source Numdam

Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension 3, questions 1) and 3) are undecidable. For dimension 2, they are still open as far as we know. Here we prove that problems 2) and 4) are decidable by proving more generally that it is recursively decidable whether or not a given non singular matrix belongs to a given finitely generated semigroup.

DOI : 10.1051/ita:2005007
Classification : 20M05, 68R15 
@article{ITA_2005__39_1_125_0,
     author = {Choffrut, Christian and Karhum\"aki, Juhani},
     title = {Some decision problems on integer matrices},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {125--131},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     year = {2005},
     doi = {10.1051/ita:2005007},
     mrnumber = {2132582},
     zbl = {1081.20066},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005007/}
}
TY  - JOUR
AU  - Choffrut, Christian
AU  - Karhumäki, Juhani
TI  - Some decision problems on integer matrices
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2005
SP  - 125
EP  - 131
VL  - 39
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005007/
DO  - 10.1051/ita:2005007
LA  - en
ID  - ITA_2005__39_1_125_0
ER  - 
%0 Journal Article
%A Choffrut, Christian
%A Karhumäki, Juhani
%T Some decision problems on integer matrices
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 125-131
%V 39
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005007/
%R 10.1051/ita:2005007
%G en
%F ITA_2005__39_1_125_0
Choffrut, Christian; Karhumäki, Juhani. Some decision problems on integer matrices. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 125-131. doi: 10.1051/ita:2005007

Cité par Sources :