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-4-20 - 2017-4-22, Bern, Switzerland.
Text
tamc2017.pdf - Author Accepted Manuscript 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: | 19 Jan 2023 07:06 |
DOI: | 10.1007/978-3-319-55911-7_27 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007003 |