Vector Reachability Problem in SL(2,Z)



Semukhin, P and Potapov, I
(2019) Vector Reachability Problem in SL(2,Z). Journal of Computer and System Sciences, 100. 30 - 43.

[img] Text
vrp.pdf - Submitted Version

Download (465kB)

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 . 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.

Item Type: Article
Uncontrolled Keywords: Vector reachability problem, Scalar reachability problem, Matrix semigroup, Special linear group, Linear fractional transformation, Automata and formal languages
Depositing User: Symplectic Admin
Date Deposited: 05 Sep 2017 09:02
Last Modified: 13 Jun 2022 14:11
DOI: 10.1016/j.jcss.2018.09.003
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3009296