Deciding finiteness for matrix semigroups over function fields over finite fields - A note on a paper by Rockmore, Tan, and Beals

We present a deterministic polynomial time algorithm for testing finiteness of a semigroup S generated by matrices with entries from function fields of constant transcendence degree over finite fields. A special case of the problem was shown to be algorithmically soluble in [RTB] by giving a sharp exponential upper bound on the dimension of the matrix algebra generated by S over the field of constants. One of the exponential time algorithms proposed in [RTB] was expected to be improvable. The polynomial time method presented in this note combines the ideas of that algorithm with a procedure from [IRSz] for calculating the radical.