Vector ambiguity and freeness problems in sl(2, z)

Sang Ki Ko, Igor Potapov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


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.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
EditorsGerhard Jager, Silvia Steila, T.V. Gopal
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783319559100
StatePublished - 2017
Event14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Switzerland
Duration: 20 Apr 201722 Apr 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10185 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017


  • Decidability
  • Matrix semigroup
  • NP-completeness
  • SL(2,Z)
  • Vector ambiguity
  • Vector freeness


Dive into the research topics of 'Vector ambiguity and freeness problems in sl(2, z)'. Together they form a unique fingerprint.

Cite this