@inproceedings{72bb0bfef164440eafc08fd96e3af708,
title = "Matrix semigroup freeness problems in SL(2, ℤ)",
abstract = "In this paper we study decidability and complexity of decision problems on matrices from the special linear group SL(2, ℤ). In particular, we study the freeness problem: given a finite set of matrices G generating a multiplicative semigroup S, decide whether each element of S has at most one factorization over G. In other words, is G a code? We show that the problem of deciding whether a matrix semigroup in SL(2, ℤ) is non-free is NP-hard. Then, we study questions about the number of factorizations of matrices in the matrix semigroup such as the finite freeness problem, the recurrent matrix problem, the unique factorizability problem, etc. Finally, we show that some factorization problems could be even harder in SL(2, ℤ), for example we show that to decide whether every prime matrix has at most k factorizations is PSPACE-hard.",
keywords = "Computational complexity, Decidability, Decision problems, Freeness, Matrix semigroups",
author = "Ko, {Sang Ki} and Igor Potapov",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017 ; Conference date: 16-01-2017 Through 20-01-2017",
year = "2017",
doi = "10.1007/978-3-319-51963-0_21",
language = "English",
isbn = "9783319519623",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "268--279",
editor = "Christel Baier and {van den Brand}, Mark and Johann Eder and Mike Hinchey and Tiziana Margaria and Bernhard Steffen",
booktitle = "SOFSEM 2017",
address = "Germany",
}