Vector Ambiguity and Freeness Problems in SL (2, ℤ).



Potapov, I and Ko, S
(2017) Vector Ambiguity and Freeness Problems in SL (2, ℤ). In: Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, 2017-04-20 - 2017-04-22, Bern, Switzerland.

[img] Text
tamc2017.pdf - Accepted Version

Download (139kB)

Abstract

We study the vector ambiguity problem and the vector freeness problem in SL(2,Z). Given a finitely generated n×n matrix semigroup S and an n-dimensional vector x, the vector ambiguity problem is to decide whether for every target vector y=Mx, where M∈S, M is unique. We also consider the vector freeness problem which is to show that every matrix M which is transforming x to Mx has a unique factorization with respect to the generator of S. We show that both problems are NP-complete in SL(2,Z), which is the set of 2×2 integer matrices with determinant 1. Moreover, we generalize the vector ambiguity problem and extend to the finite and k-vector ambiguity problems where we consider the degree of vector ambiguity of matrix semigroups.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: Matrix semigroup Vector ambiguity Vector freeness Decidability NP-completeness
Depositing User: Symplectic Admin
Date Deposited: 19 Apr 2017 10:22
Last Modified: 13 Dec 2021 16:10
DOI: 10.1007/978-3-319-55911-7_27
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007003