@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",

}