Some decision problems on integer matrices

Christian Choffrut; Juhani Karhumäki

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

  • Volume: 39, Issue: 1, page 125-131
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Choffrut, Christian, and Karhumäki, Juhani. "Some decision problems on integer matrices." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.1 (2005): 125-131. <http://eudml.org/doc/244723>.

@article{Choffrut2005,
abstract = {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.},
author = {Choffrut, Christian, Karhumäki, Juhani},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {integer matrices; decision problems; semigroups of matrices; finitely generated semigroups; recursive decidability},
language = {eng},
number = {1},
pages = {125-131},
publisher = {EDP-Sciences},
title = {Some decision problems on integer matrices},
url = {http://eudml.org/doc/244723},
volume = {39},
year = {2005},
}

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
PB - EDP-Sciences
VL - 39
IS - 1
SP - 125
EP - 131
AB - 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.
LA - eng
KW - integer matrices; decision problems; semigroups of matrices; finitely generated semigroups; recursive decidability
UR - http://eudml.org/doc/244723
ER -

References

top
  1. [1] J. Berstel, Transductions and context-free languages. B.G. Teubner (1979). Zbl0424.68040MR549481
  2. [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. Zbl1029.20027
  3. [3] C. Choffrut, A remark on the representation of trace monoids. Semigroup Forum 40 (1990) 143–152. Zbl0693.20064
  4. [4] M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets. Fund. Inform. X (1987) 323–336. Zbl0634.94014
  5. [5] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974). Zbl0317.94045MR530382
  6. [6] T. Harju, Decision questions on integer matrices. Lect. Notes Comp. Sci. 2295 (2002) 57–68. Zbl1073.03519
  7. [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. Zbl0866.68057
  8. [8] G. Jacob, La finitude des représentations linéaires de semigroupes est décidable. J. Algebra 52 (1978) 437–459. Zbl0374.20074
  9. [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. Zbl0969.68528
  10. [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. Zbl0724.20036
  11. [11] R. Lyndon and P. Schupp, Combinatorial Group Theory, of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag 89 (1977). Zbl0368.20023MR577064
  12. [12] W. Magnus, The use of 2 by 2 matrices in combinatorial group theory. Resultate der Mathematik 4 (1981) 171–192. Zbl0468.20031
  13. [13] A. Mandel and I. Simon, On finite semigroups of matrices. Theoret. Comput. Sci. 5 (1978) 101–112. Zbl0368.20049
  14. [14] A.A. Markov, On certain insoluble problems concerning matrices (russian). Doklady Akad. Nauk SSSR (N.S.) 57 (1947) 539–542. Zbl0037.29706
  15. [15] Open problems in group theory: http://zebra.sci.ccny.edu/cgi-bin/LINK.CGI?/www/web/problems/oproblems.html 
  16. [16] M.S. Paterson, Unsolvability in 3 × 3 matrices. Stud. Appl. Math. 49 (1970) 105–107. Zbl0186.01103
  17. [17] J.J. Rotman, An introduction to the Theory of Groups. Ally and Bacon Inc. (1965). Zbl0123.02001MR745804

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.