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

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 = {https://www.numdam.org/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  - https://www.numdam.org/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 https://www.numdam.org/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. https://www.numdam.org/articles/10.1051/ita:2005007/

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

[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

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

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

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

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

[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

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

[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

[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

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

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

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

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

[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

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

  • Bell, Paul C.; Hirvensalo, Mika; Potapov, Igor The membership problem for subsemigroups of GL2(Z) is NP-complete, Information and Computation, Volume 296 (2024), p. 105132 | DOI:10.1016/j.ic.2023.105132
  • Dong, Ruiwen, Proceedings of the 56th Annual ACM Symposium on Theory of Computing (2024), p. 884 | DOI:10.1145/3618260.3649609
  • Dong, Ruiwen Semigroup Intersection Problems in the Heisenberg Groups, SIAM Journal on Discrete Mathematics, Volume 38 (2024) no. 4, p. 3176 | DOI:10.1137/23m1581467
  • Droste, Manfred; Kuich, Werner Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings, Theoretical Computer Science, Volume 1002 (2024), p. 114599 | DOI:10.1016/j.tcs.2024.114599
  • Lohrey, M. Membership Problems in Infinite Groups, Twenty Years of Theoretical and Practical Synergies, Volume 14773 (2024), p. 44 | DOI:10.1007/978-3-031-64309-5_5
  • Dong, Ruiwen, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (2023), p. 1 | DOI:10.1109/lics56636.2023.10175768
  • Dong, Ruiwen Recent Advances in Algorithmic Problems for Semigroups, ACM SIGLOG News, Volume 10 (2023) no. 4, p. 3 | DOI:10.1145/3636362.3636365
  • Bell, Paul C.; Niskanen, Reino; Potapov, Igor; Semukhin, Pavel On the Identity and Group Problems for Complex Heisenberg Matrices, Reachability Problems, Volume 14235 (2023), p. 42 | DOI:10.1007/978-3-031-45286-4_4
  • Bell, Paul C.; Hirvensalo, Mika On injectivity of quantum finite automata, Journal of Computer and System Sciences, Volume 122 (2021), p. 19 | DOI:10.1016/j.jcss.2021.05.002
  • Bell, Paul C.; Chen, Shang; Jackson, Lisa Freeness properties of weighted and probabilistic automata over bounded languages, Information and Computation, Volume 269 (2019), p. 104440 | DOI:10.1016/j.ic.2019.104440
  • Potapov, Igor; Semukhin, Pavel Vector and scalar reachability problems in SL(2,Z), Journal of Computer and System Sciences, Volume 100 (2019), p. 30 | DOI:10.1016/j.jcss.2018.09.003
  • Ouaknine, Joël; Pouly, Amaury; Sousa-Pinto, João; Worrell, James On the Decidability of Membership in Matrix-exponential Semigroups, Journal of the ACM, Volume 66 (2019) no. 3, p. 1 | DOI:10.1145/3286487
  • Ko, Sang-Ki; Potapov, Igor Matrix Semigroup Freeness Problems in SL (2,Z), SOFSEM 2017: Theory and Practice of Computer Science, Volume 10139 (2017), p. 268 | DOI:10.1007/978-3-319-51963-0_21
  • Ko, Sang-Ki; Potapov, Igor Vector Ambiguity and Freeness Problems in SL (2,Z), Theory and Applications of Models of Computation, Volume 10185 (2017), p. 373 | DOI:10.1007/978-3-319-55911-7_27
  • Bell, Paul C.; Hirvensalo, Mika; Potapov, Igor Mortality for 2 ×2 Matrices Is NP-Hard, Mathematical Foundations of Computer Science 2012, Volume 7464 (2012), p. 148 | DOI:10.1007/978-3-642-32589-2_16
  • Cassaigne, Julien; Nicolas, Francois On the decidability of semigroup freeness, RAIRO - Theoretical Informatics and Applications, Volume 46 (2012) no. 3, p. 355 | DOI:10.1051/ita/2012010
  • BELL, PAUL C.; POTAPOV, IGOR ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, International Journal of Foundations of Computer Science, Volume 21 (2010) no. 06, p. 963 | DOI:10.1142/s0129054110007660
  • Gawrychowski, Paweł; Gutan, Marin; Kisielewicz, Andrzej On the problem of freeness of multiplicative matrix semigroups, Theoretical Computer Science, Volume 411 (2010) no. 7-9, p. 1115 | DOI:10.1016/j.tcs.2009.12.005
  • Bell, Paul C.; Potapov, Igor The Identity Correspondence Problem and Its Applications, Algorithms and Computation, Volume 5878 (2009), p. 657 | DOI:10.1007/978-3-642-10631-6_67
  • HALAVA, VESA; HARJU, TERO; HIRVENSALO, MIKA UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, International Journal of Foundations of Computer Science, Volume 18 (2007) no. 05, p. 931 | DOI:10.1142/s0129054107005066
  • Bell, Paul; Potapov, Igor On the membership of invertible diagonal and scalar matrices, Theoretical Computer Science, Volume 372 (2007) no. 1, p. 37 | DOI:10.1016/j.tcs.2006.11.011
  • Bertoni, Alberto; Mereghetti, Carlo; Palano, Beatrice Some formal tools for analyzing quantum automata, Theoretical Computer Science, Volume 356 (2006) no. 1-2, p. 14 | DOI:10.1016/j.tcs.2006.01.042

Cité par 22 documents. Sources : Crossref