Extended finite automata and decision problems for matrix semigroups

Abstract

We make a connection between the subgroup membership and identity problems for matrix groups and extended finite automata. We provide an alternative proof for the decidability of the subgroup membership problem for $2\times 2$ integer matrices. We show that the emptiness problem for extended finite automata over $4\times 4$ integer matrix semigroups is undecidable. We prove that the decidability of the universe problem for extended finite automata is a sufficient condition for the decidability of the subgroup membership and identity problems.

NCMA2018 Short Paper