Some decision problems on integer matrices
Choffrut, Christian ; Karhumäki, Juhani
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005), p. 125-131 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2005-01-01
DOI : https://doi.org/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},
     volume = {39},
     year = {2005},
     pages = {125-131},
     doi = {10.1051/ita:2005007},
     mrnumber = {2132582},
     zbl = {1081.20066},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 125-131. doi : 10.1051/ita:2005007. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_125_0/

[1] J. Berstel, Transductions and context-free languages. B.G. Teubner (1979). | MR 549481 | Zbl 0424.68040

[2] J. Cassaigne, T. Harju and J. Karhumäki, On the undecidability of freeness of matrix semigroups. Internat. J. Algebra Comput. 9 (1999) 295-305. | Zbl 1029.20027

[3] C. Choffrut, A remark on the representation of trace monoids. Semigroup Forum 40 (1990) 143-152. | Zbl 0693.20064

[4] M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets. Fund. Inform. X (1987) 323-336. | Zbl 0634.94014

[5] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974). | MR 530382 | Zbl 0317.94045

[6] T. Harju, Decision questions on integer matrices. Lect. Notes Comp. Sci. 2295 (2002) 57-68. | Zbl 1073.03519

[7] T. Harju and J. Karhumäki, Morphisms, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997) 439-510. | Zbl 0866.68057

[8] G. Jacob, La finitude des représentations linéaires de semigroupes est décidable. J. Algebra 52 (1978) 437-459. | Zbl 0374.20074

[9] J. Karhumäki, Some opem problems in combinatorics of words and related areas, in Proc. of RIMS Symposium on Algebraic Systems, Formal Languages and Computation. RIMS Institute 1166 (2000) 118-130. | Zbl 0969.68528

[10] D.A. Klarner, J.-C. Birget and W. Satterfield, On the undecidability of the freeness of integer matrix semigroups monoids. Internat. J. Algebra Comput. 1 (1991) 223-226. | Zbl 0737.20029

[11] R. Lyndon and P. Schupp, Combinatorial Group Theory, of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag 89 (1977). | MR 577064 | Zbl 0368.20023

[12] W. Magnus, The use of 2 by 2 matrices in combinatorial group theory. Resultate der Mathematik 4 (1981) 171-192. | Zbl 0468.20031

[13] A. Mandel and I. Simon, On finite semigroups of matrices. Theoret. Comput. Sci. 5 (1978) 101-112. | Zbl 0368.20049

[14] A.A. Markov, On certain insoluble problems concerning matrices (russian). Doklady Akad. Nauk SSSR (N.S.) 57 (1947) 539-542. | Zbl 0037.29706

[15] Open problems in group theory: http://zebra.sci.ccny.edu/cgi-bin/LINK.CGI?/www/web/problems/oproblems.html

[16] M.S. Paterson, Unsolvability in 3×3 matrices. Stud. Appl. Math. 49 (1970) 105-107. | Zbl 0186.01103

[17] J.J. Rotman, An introduction to the Theory of Groups. Ally and Bacon Inc. (1965). | MR 745804 | Zbl 0123.02001