# Some decision problems on integer matrices

Christian Choffrut; Juhani Karhumäki

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topChoffrut, Christian, and Karhumäki, Juhani. " Some decision problems on integer matrices." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 125-131. <http://eudml.org/doc/92750>.

@article{Choffrut2010,

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},

keywords = {integer matrices; decision problems; semigroups of matrices; finitely generated semigroups; recursive decidability},

language = {eng},

month = {3},

number = {1},

pages = {125-131},

publisher = {EDP Sciences},

title = { Some decision problems on integer matrices},

url = {http://eudml.org/doc/92750},

volume = {39},

year = {2010},

}

TY - JOUR

AU - Choffrut, Christian

AU - Karhumäki, Juhani

TI - Some decision problems on integer matrices

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

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/92750

ER -

## References

top- J. Berstel, Transductions and context-free languages. B.G. Teubner (1979).
- J. Cassaigne, T. Harju and J. Karhumäki, On the undecidability of freeness of matrix semigroups. Internat. J. Algebra Comput.9 (1999) 295–305.
- C. Choffrut, A remark on the representation of trace monoids. Semigroup Forum40 (1990) 143–152.
- M. Chrobak and W. Rytter, Unique decipherability for partially commutative alphabets. Fund. Inform.X (1987) 323–336.
- S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974).
- T. Harju, Decision questions on integer matrices. Lect. Notes Comp. Sci.2295 (2002) 57–68.
- 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.
- G. Jacob, La finitude des représentations linéaires de semigroupes est décidable. J. Algebra52 (1978) 437–459.
- 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.
- 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.
- R. Lyndon and P. Schupp, Combinatorial Group Theory, of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag 89 (1977).
- W. Magnus, The use of 2 by 2 matrices in combinatorial group theory. Resultate der Mathematik4 (1981) 171–192.
- A. Mandel and I. Simon, On finite semigroups of matrices. Theoret. Comput. Sci.5 (1978) 101–112.
- A.A. Markov, On certain insoluble problems concerning matrices (russian). Doklady Akad. Nauk SSSR (N.S.)57 (1947) 539–542.
- Open problems in group theory: http://zebra.sci.ccny.edu/cgi-bin/LINK.CGI?/www/web/problems/oproblems.html
- M.S. Paterson, Unsolvability in 3 x 3 matrices. Stud. Appl. Math.49 (1970) 105–107.
- J.J. Rotman, An introduction to the Theory of Groups. Ally and Bacon Inc. (1965).