Issue Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist Page(s) 125 - 131 DOI 10.1051/ita:2005007

Theoret. Informatics Appl. 39, 125-131 (2005)
DOI: 10.1051/ita:2005007

Some decision problems on integer matrices

Christian Choffrut¹ and Juhani Karhumäki<sup>2

1</sup>  L.I.A.F.A, Université Paris VII, Tour 55-56, 1 étage, 2 pl. Jussieu, 75 251 Paris Cedex, France; Christian.Choffrut@liafa.jussieu.fr
²  Dept. of Mathematics and TUCS, University of Turku, 20014 Turku, Finland; Juhani.Karhumaki@cs.utu.fi

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.

Mathematics Subject Classification. 20M05, 68R15


© EDP Sciences 2005

What is OpenURL?