{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:07:52Z","timestamp":1742911672687,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319559100"},{"type":"electronic","value":"9783319559117"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-55911-7_27","type":"book-chapter","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T10:23:37Z","timestamp":1490005417000},"page":"373-388","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Vector Ambiguity and Freeness Problems in SL $$(2,\\mathbb {Z})$$"],"prefix":"10.1007","author":[{"given":"Sang-Ki","family":"Ko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"key":"27_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/978-3-319-30000-9_38","volume-title":"Language and Automata Theory and Applications","author":"PC Bell","year":"2016","unstructured":"Bell, P.C., Chen, S., Jackson, L.: Scalar ambiguity and freeness in matrix semigroups over bounded languages. In: Dediu, A.-H., Janou\u0161ek, J., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 493\u2013505. Springer, Cham (2016). doi: 10.1007\/978-3-319-30000-9_38"},{"key":"27_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-642-32589-2_16","volume-title":"Mathematical Foundations of Computer Science 2012","author":"PC Bell","year":"2012","unstructured":"Bell, P.C., Hirvensalo, M., Potapov, I.: Mortality for $$2\\times 2$$ matrices is NP-hard. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 148\u2013159. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-32589-2_16"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Bell, P.C., Hirvensalo, M., Potapov, I.: The identity problem for matrix semigroups in SL $$_2 (\\mathbb{Z})$$ is NP-complete. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 187\u2013206 (2017)","DOI":"10.1137\/1.9781611974782.13"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-540-77566-9_13","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"P Bell","year":"2008","unstructured":"Bell, P., Potapov, I.: Periodic and infinite traces in matrix semigroups. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 148\u2013161. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-77566-9_13"},{"issue":"11","key":"27_CR5","doi-asserted-by":"crossref","first-page":"1353","DOI":"10.1016\/j.ic.2008.06.004","volume":"206","author":"PC Bell","year":"2008","unstructured":"Bell, P.C., Potapov, I.: Reachability problems in quaternion matrix and rotation semigroups. Inf. Comput. 206(11), 1353\u20131361 (2008)","journal-title":"Inf. Comput."},{"issue":"1\u20134","key":"27_CR6","first-page":"1","volume":"116","author":"PC Bell","year":"2012","unstructured":"Bell, P.C., Potapov, I.: On the computational complexity of matrix semigroup problems. Fundam. Infomaticae 116(1\u20134), 1\u201313 (2012)","journal-title":"Fundam. Infomaticae"},{"issue":"1","key":"27_CR7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00233-007-9024-6","volume":"76","author":"J-C Birget","year":"2008","unstructured":"Birget, J.-C., Margolis, S.W.: Two-letter group codes that preserve aperiodicity of inverse finite automata. Semigroup Forum 76(1), 159\u2013168 (2008)","journal-title":"Semigroup Forum"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Blondel, V.D., Cassaigne, J., Karhum\u00e4ki, J.: Problem 10.3: freeness of multiplicative matrix semigroups. In: Unsolved Problems in Mathematical Systems and Control Theory, pp. 309\u2013314. Princeton University Press (2004)","DOI":"10.1515\/9781400826155.309"},{"issue":"3\u20134","key":"27_CR9","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1142\/S0218196799000199","volume":"9","author":"J Cassaigne","year":"1999","unstructured":"Cassaigne, J., Harju, T., Karhum\u00e4ki, J.: On the undecidability of freeness of matrix semigroups. Int. J. Algebra Comput. 9(3\u20134), 295\u2013305 (1999)","journal-title":"Int. J. Algebra Comput."},{"issue":"2","key":"27_CR10","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF02829784","volume":"116","author":"F Chamizo","year":"2006","unstructured":"Chamizo, F.: Non-euclidean visibility problems. Proc. Indian Acad. Sci. - Math. Sci. 116(2), 147\u2013160 (2006)","journal-title":"Proc. Indian Acad. Sci. - Math. Sci."},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/j.ic.2014.03.001","volume":"237","author":"E Charlier","year":"2014","unstructured":"Charlier, E., Honkala, J.: The freeness problem over matrix semigroups and bounded languages. Inf. Comput. 237, 243\u2013256 (2014)","journal-title":"Inf. Comput."},{"issue":"1","key":"27_CR12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1051\/ita:2005007","volume":"39","author":"C Choffrut","year":"2010","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Some decision problems on integer matrices. RAIRO - Theoret. Inf. Appl. 39(1), 125\u2013131 (2010)","journal-title":"RAIRO - Theoret. Inf. Appl."},{"issue":"2","key":"27_CR13","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1112\/plms\/s3-57.2.239","volume":"s3\u201357","author":"J Elstrodt","year":"1988","unstructured":"Elstrodt, J., Grunewald, F., Mennicke, J.: Arithmetic applications of the hyperbolic lattice point theorem. Proc. London Math. Soc. s3\u201357(2), 239\u2013283 (1988)","journal-title":"Proc. London Math. Soc."},{"issue":"9","key":"27_CR14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/JHEP09(2011)068","volume":"2011","author":"MP Garc\u00eda del Moral","year":"2011","unstructured":"Garc\u00eda del Moral, M.P., Mart\u00edn, I., Pe\u00f1a, J.M., Restuccia, A.: SL $$(2, \\mathbb{Z})$$ symmetries, supermembranes and symplectic torus bundles. J. High Energy Phys. 2011(9), 68 (2011)","journal-title":"J. High Energy Phys."},{"issue":"2","key":"27_CR15","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1137\/050643295","volume":"37","author":"Y Gurevich","year":"2007","unstructured":"Gurevich, Y., Schupp, P.: Membership problem for the modular group. SIAM J. Comput. 37(2), 425\u2013459 (2007)","journal-title":"SIAM J. Comput."},{"issue":"02","key":"27_CR16","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1142\/S0218196791000146","volume":"01","author":"DA Klarner","year":"1991","unstructured":"Klarner, D.A., Birget, J.-C., Satterfield, W.: On the undecidability of the freeness of integer matrix semigroups. Int. J. Algebra Comput. 01(02), 223\u2013226 (1991)","journal-title":"Int. J. Algebra Comput."},{"key":"27_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-319-51963-0_21","volume-title":"SOFSEM 2017: Theory and Practice of Computer Science","author":"S-K Ko","year":"2017","unstructured":"Ko, S.-K., Potapov, I.: Matrix semigroup freeness problems in SL $$(2,\\mathbb{Z})$$ . In: Steffen, B., Baier, C., Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds.) SOFSEM 2017. LNCS, vol. 10139, pp. 268\u2013279. Springer, Cham (2017). doi: 10.1007\/978-3-319-51963-0_21"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"27_CR19","volume-title":"Combinatorial Group Theory","author":"RC Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer, Heidelberg (1977)"},{"key":"27_CR20","unstructured":"Mackenzie, D.: A new twist in knot theory. In: What\u2019s Happening in the Mathematical Sciences, vol. 7, pp. 3\u201317. American Mathematical Society (2009)"},{"issue":"2","key":"27_CR21","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0304-3975(77)90001-9","volume":"5","author":"A Mandel","year":"1977","unstructured":"Mandel, A., Simon, I.: On finite semigroups of matrices. Theoret. Comput. Sci. 5(2), 101\u2013111 (1977)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"27_CR22","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1080\/17459730701375026","volume":"1","author":"T Noll","year":"2007","unstructured":"Noll, T.: Musical intervals and special linear transformations. J. Math. Music 1(2), 121\u2013137 (2007)","journal-title":"J. Math. Music"},{"key":"27_CR23","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1017\/S0143385703000531","volume":"24","author":"L Polterovich","year":"2004","unstructured":"Polterovich, L., Rudnick, Z.: Stable mixing for cat maps and quasi-morphisms of the modular group. Ergodic Theory Dyn. Syst. 24, 609\u2013619 (2004)","journal-title":"Ergodic Theory Dyn. Syst."},{"key":"27_CR24","unstructured":"Potapov, I.: Composition problems for braids. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 24, pp. 175\u2013187 (2013)"},{"key":"27_CR25","unstructured":"Potapov, I., Semukhin, P.: Vector reachability problem in SL $$(2, \\mathbb{Z})$$ . In: Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, pp. 84:1\u201384:14 (2016)"},{"key":"27_CR26","doi-asserted-by":"crossref","unstructured":"Potapov, I., Semukhin, P.: Decidability of the membership problem for $$2 \\times 2$$ integer matrices. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 170\u2013186 (2017)","DOI":"10.1137\/1.9781611974782.12"},{"key":"27_CR27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511808876","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2008","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory, 1st edn. Cambridge University Press, New York (2008)","edition":"1"},{"key":"27_CR28","doi-asserted-by":"crossref","unstructured":"Witten, E.: SL $$(2, \\mathbb{Z})$$ action on three-dimensional conformal field theories with abelian symmetry. In: From fields to strings: circumnavigating theoretical physics, vol. 2, pp. 1173\u20131200. World Scientific Publishing (2005)","DOI":"10.1142\/9789812775344_0028"},{"issue":"6","key":"27_CR29","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0020-0190(92)90226-L","volume":"42","author":"GJ Woeginger","year":"1992","unstructured":"Woeginger, G.J., Yu, Z.: On the equal-subset-sum problem. Inf. Process. Lett. 42(6), 299\u2013302 (1992)","journal-title":"Inf. Process. Lett."},{"key":"27_CR30","series-title":"Universitext","first-page":"1","volume-title":"The 1-2-3 of Modular Forms","author":"D Zagier","year":"2008","unstructured":"Zagier, D.: Elliptic modular forms and their applications. In: Ranestad, K. (ed.) The 1-2-3 of Modular Forms. Universitext, pp. 1\u2013103. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-55911-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T20:20:13Z","timestamp":1568924413000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-55911-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319559100","9783319559117"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-55911-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}