Search

Abstract This paper solves three open problems about the decidability of the vector and scalar reachability problems and the point to point reachability by fractional linear transformations over finitely generated semigroups of matrices from SL (2 , Z). Our approach to solving these problems is based on the characterization of reachability paths between vectors or points, which is then used to translate the numerical problems on matrices into computational problems on words and regular languages. We will also give geometric interpretations of these results. Highlights • The vector reachability problem in SL (2 , Z) is decidable. • The scalar reachability problem in SL (2 , Z) is decidable. • Reachability problem by fractional linear transformations in SL (2 , Z) is decidable. • Proofs are based on translating matrix equations into problems on regular languages. • We give a geometric interpretation and prove generalizations of these results. [ABSTRACT FROM AUTHOR]