Vector Ambiguity and Freeness Problems in SL (2, Z)

• Autorzy: Ko S.-K. , Potapov I.

Identyfikatory

DOI

10.3233/FI-2018-1719

• Konferencja: RuFiDiM Conference, Russian-Finnish Symposium in Discrete Mathematics (5; 16-19.05. 2017; Turku; Finland)
• Języki publikacji: EN

Abstrakty

EN

We study the vector ambiguity problem and the vector freeness problem in SL (2, Z). Given a finitely generated n x n matrix semigroup S and an n-dimensional vector x, the vector ambiguity problem is to decide whether for every target vector y = Mx, 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 Mx has a unique factorization 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 x 2 integer matrices with determinant 1. Moreover, we generalize the vector ambiguity problem and extend to the finite and k-vector ambiguity problems where we consider the degree of vector ambiguity of matrix semigroups.

Słowa kluczowe

EN

matrix semigroup; special linear group; vector ambiguity; vector freeness; decidability; NP-completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 162, nr 2/3
• Strony: 161--182
• Opis fizyczny: Bibliogr. 31 poz., tab., wykr.

Twórcy

autor

Ko S.-K.

• Artificial Intelligence Research Center, Korea Electronics Technology Institute, 22 Daewangpangyo-ro, Gyeonggi-do, 13488, Republic of Korea

autor

Potapov I.

• Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom

Bibliografia

• [1] Bell PC, Chen S, Jackson L. Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages, Proceedings of the 10th International Conference on Language and Automata Theory and Applications, LNCS vol. 9618, Springer 2016, pp. 493-505. doi:10.1007/978-3-319-30000-9_38.
• [2] Bell PC, Hirvensalo M, Potapov I. Mortality for 2 x 2 Matrices Is NP-Hard, Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, LNCS vol. 7464, Springer 2012, pp. 148-159. doi:10.1007/978-3-642-32589-2_16.
• [3] Bell PC, Hirvensalo M, Potapov I. The Identity Problem for Matrix Semigroups in SL2(Z) is NP-complete, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017. Conference Paper (PDF Available), January 2017with25 Reads doi:10.1137/1.9781611974782.13.
• [4] Bell PC, Hirvensalo M, Potapov I. Periodic and Infinite Traces in Matrix Semigroups, Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, LNCS vol. 4910, Springer 2008, pp. 148-161. doi:10.1007/978-3-540-77566-9_13.
• [5] Bell PC, Hirvensalo M, Potapov I. Reachability problems in quaternion matrix and rotation semigroups, Information and Computation, 2008;206(11):1353-1361. URL https://doi.org/10.1016/j.ic.2008.06.004.
• [6] Bell PC, Hirvensalo M, Potapov I. On the Computational Complexity of Matrix Semigroup Problems, Fundamenta Infomaticae, 2012;116(1-4):1-13. doi:10.3233/FI-2012-663.
• [7] Birget JC, Margolis SW. Two-letter group codes that preserve aperiodicity of inverse finite automata, Semigroup Forum, 2008;76(1):159-168. doi:10.1007/s00233-007-9024-6.
• [8] Blondel VD, Cassaigne J, Karhumäki J. Problem 10.3: Freeness of multiplicative matrix semigroups, in: Unsolved Problems in Mathematical Systems and Control Theory, Princeton University Press, 2004 pp. 309-314.
• [9] Cassaigne J, Harju T, Karhumäki J. ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS, International Journal of Algebra and Computation, 1999;9(3-4):295-305. URL https://doi.org/10.1142/S0218196799000199.
• [10] Cassaigne J, Karhumäki J, Harju T. On the Decidability of the Freeness of Matrix Semigroups, Technical report, Turku Center for Computer Science, 1996. ISBN:951-650-875-8, 1239-1891.
• [11] Chamizo F. Non-Euclidean visibility problems, Proceedings of the Indian Academy of Sciences – Mathematical Sciences, 2006;116(2):147-160.
• [12] Charlier E, Honkala J. The freeness problem over matrix semigroups and bounded languages, Information and Computation, 2014;237:243-256. URL https://doi.org/10.1016/j.ic.2014.03.001.
• [13] Choffrut C, Karhumäki J. Some decision problems on integer matrices, RAIRO - Theoretical Informatics and Applications, 2010;39(1):125-131.
• [14] Elstrodt J, Grunewald F, Mennicke J. Arithmetic Applications of the Hyperbolic Lattice Point Theorem, Proceedings of the London Mathematical Society, 1988;s3-57(2):239-283. URL https://doi.org/10.1112/plms/s3-57.2.239.
• [15] García del Moral MP, Martín I, Peña JM, Restuccia A. SL(2,Z) symmetries, supermembranes and symplectic torus bundles, Journal of High Energy Physics, 2011;2011(9):68. doi:10.1007/JHEP09(2011)068.
• [16] Gurevich Y, Schupp P. Membership Problem for the Modular Group, SIAM Journal on Computing, 2007;37(2):425-459. doi:10.1137/050643295.
• [17] Klarner DA, Birget JC, Satterfield W. ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS, International Journal of Algebra and Computation, 1991;01(02):223-226. URL https://doi.org/10.1142/S0218196791000146.
• [18] Ko SK, Potapov I. Matrix Semigroup Freeness Problems in SL(2,Z), Proceedings of the 43rd Conference on Current Trends in Theory and Practice of Computer Science, 2017 pp. 268-279. doi:10.1007/978-3-319-51963-0_21.
• [19] Kozen D. Lower Bounds for Natural Proof Systems, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 1977. doi:10.1109/SFCS.1977.16.
• [20] Lyndon RC, Schupp PE. Combinatorial group theory, Springer Berlin Heidelberg, 1977.
• [21] Mackenzie D. A new twist in knot theory, in: What’s Happening in the Mathematical Sciences, vol. 7, American Mathematical Society, 2009, pp. 3-17.
• [22] Mandel A, Simon I. On finite semigroups of matrices, Theoretical Computer Science, 1977;5(2):101-111. URL https://doi.org/10.1016/0304-3975(77)90001-9.
• [23] Noll T. Musical intervals and special linear transformations, Journal of Mathematics and Music, 2007;1(2):121-137. URL https://doi.org/10.1080/17459730701375026.
• [24] Polterovich L, Rudnick Z. Stable mixing for cat maps and quasi-morphisms of the modular group, Ergodic Theory and Dynamical Systems, 2004;24:609-619. URL https://doi.org/10.1017/S0143385703000531.
• [25] Potapov I. Composition Problems for Braids, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 24, 2013.
• [26] Potapov I, Semukhin P. Vector Reachability Problem in SL(2,Z), Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016.
• [27] Potapov I, Semukhin P. Decidability of the Membership Problem for 2x2 integer matrices, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017. URL http://livrepository.liverpool.ac.uk/id/eprint/3004254.
• [28] Shallit J. A Second Course in Formal Languages and Automata Theory, 1 edition, Cambridge University Press, New York, NY, USA, 2008. ISBN:0521865727, 9780521865722.
• [29] Witten E. SL(2,Z) action on three-dimensional conformal field theories with abelian symmetry, in: From fields to strings: circumnavigating theoretical physics, vol. 2, World Scientific Publishing, 2005 pp. 1173-1200. doi: 10.1142/9789812775344_0028.
• [30] Woeginger GJ, Yu Z. On the equal-subset-sum problem, Information Processing Letters, 1992;42(6):299-302. URL https://doi.org/10.1016/0020-0190(92)90226-L.
• [31] Zagier D. Elliptic Modular Forms and Their Applications, The 1-2-3 of Modular Forms: Lectures at a Summer School in Nordfjordeid, Norway, Springer Berlin Heidelberg, 2008, pp. 1-103. doi:10.1007/978-3-540-74119-0_1.