2016/10/31 by Sang‐Ki Ko, Sang-Ki Ko, Ko, Sang-Ki +2
Computer Science · Engineering · #Coding theory and cryptography #Computational Complexity (cs.CC) #F.1.1 #F.2.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.CC #cs.FL #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1610.09834
arxiv created 2016/10/31 · openalex publication_date 2016/10/31 · arxiv updated 2016/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.