The Identity Problem for GL(2,Z)

Given a finitely generated matrix semigroup, the identity problem asks whether the identity matrix belongs to the semigroup. We study the problem over GL(2, Z), the General Linear Group of 2x2 matrices, where the problem was recently shown to be NP-complete. An interesting corollary of this result is that the freeness and membership problems for GL(2, Z) can then also be shown to be NP-complete. The result is shown by studying compressed word representations of elements of SL(2, Z), the Special Linear Group, and then reformulating the problem into a graph structure. We will also present some results concerning freeness type problems for weighted and probabilistic finite automata where several undecidability results will be shown.