@inproceedings{44bbb7b1d9184c15a9e723c2ed2b0c3f,
title = "Vector ambiguity and freeness problems in sl(2, z)",
abstract = "We study the vector ambiguity problem and the vector free-ness problem in SL(2, Z). Given a finitely generated n × n matrix semi-group S and an n-dimensional vector x, the vector ambiguity problem is to decide whether for every target vector y = M x, 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 M x has a unique factor-ization 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 prob-lem and extend to the finite and k-vector ambiguity problems where we consider the degree of vector ambiguity of matrix semigroups.",
keywords = "Decidability, Matrix semigroup, NP-completeness, SL(2,Z), Vector ambiguity, Vector freeness",
author = "Ko, {Sang Ki} and Igor Potapov",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",
year = "2017",
doi = "10.1007/978-3-319-55911-7_27",
language = "English",
isbn = "9783319559100",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "373--388",
editor = "Gerhard Jager and Silvia Steila and T.V. Gopal",
booktitle = "Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings",
address = "Germany",
}