{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T10:38:44Z","timestamp":1725878324568},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319519623"},{"type":"electronic","value":"9783319519630"}],"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":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-51963-0_21","type":"book-chapter","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T06:17:39Z","timestamp":1484029059000},"page":"268-279","source":"Crossref","is-referenced-by-count":1,"title":["Matrix Semigroup 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,1,11]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Bell, P.C., Hirvensalo, M., Potapov, I.: Mortality for $$2\\times 2$$ matrices is NP-hard. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, pp. 148\u2013159 (2012)","key":"21_CR1","DOI":"10.1007\/978-3-642-32589-2_16"},{"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 (2016). To appear in SODA 17","key":"21_CR2","DOI":"10.1137\/1.9781611974782.13"},{"doi-asserted-by":"crossref","unstructured":"Bell, P.C., Potapov, I.: Periodic and infinite traces in matrix semigroups. In: Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, pp. 148\u2013161 (2008)","key":"21_CR3","DOI":"10.1007\/978-3-540-77566-9_13"},{"issue":"11","key":"21_CR4","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":"6","key":"21_CR5","doi-asserted-by":"crossref","first-page":"963","DOI":"10.1142\/S0129054110007660","volume":"21","author":"PC Bell","year":"2010","unstructured":"Bell, P.C., Potapov, I.: On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. Int. J. Found. Comput. Sci. 21(6), 963\u2013978 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20134","key":"21_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. Fundamenta Infomaticae 116(1\u20134), 1\u201313 (2012)","journal-title":"Fundamenta Infomaticae"},{"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)","key":"21_CR7","DOI":"10.1515\/9781400826155.309"},{"issue":"03\u201304","key":"21_CR8","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1142\/S0218196799000199","volume":"09","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. 09(03\u201304), 295\u2013305 (1999)","journal-title":"Int. J. Algebra Comput."},{"issue":"3","key":"21_CR9","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1051\/ita\/2012010","volume":"46","author":"J Cassaigne","year":"2012","unstructured":"Cassaigne, J., Nicolas, F.: On the decidability of semigroup freeness. RAIRO - Theor. Inf. Appl. 46(3), 355\u2013399 (2012)","journal-title":"RAIRO - Theor. Inf. Appl."},{"key":"21_CR10","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":"21_CR11","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 - Theor. Inf. Appl. 39(1), 125\u2013131 (2010)","journal-title":"RAIRO - Theor. Inf. Appl."},{"issue":"2","key":"21_CR12","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. Lond. Math. Soc. s3\u201357(2), 239\u2013283 (1988)","journal-title":"Proc. Lond. Math. Soc."},{"key":"21_CR13","first-page":"1","volume":"9","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. 9, 1\u201312 (2011)","journal-title":"J. High Energy Phys."},{"issue":"7\u20139","key":"21_CR14","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1016\/j.tcs.2009.12.005","volume":"411","author":"P Gawrychowski","year":"2010","unstructured":"Gawrychowski, P., Gutan, M., Kisielewicz, A.: On the problem of freeness of multiplicative matrix semigroups. Theor. Comput. Sci. 411(7\u20139), 1115\u20131120 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"21_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":"05","key":"21_CR16","doi-asserted-by":"crossref","first-page":"931","DOI":"10.1142\/S0129054107005066","volume":"18","author":"V Halava","year":"2007","unstructured":"Halava, V., Harju, T., Hirvensalo, M.: Undecidability bounds for integer matrices using claus instances. Int. J. Found. Comput. Sci. 18(05), 931\u2013948 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"02","key":"21_CR17","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."},{"unstructured":"Ko, S.-K., Potapov, I.: Matrix semigroup freeness problems in SL $$(2,\\mathbb{Z})$$ (2016). CoRR, abs\/1610.09834","key":"21_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)","key":"21_CR19","DOI":"10.1109\/SFCS.1977.16"},{"key":"21_CR20","volume-title":"Combinatorial Group Theory","author":"RC Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer, Heidelberg (1977)"},{"unstructured":"Mackenzie, D.: A New Twist in Knot Theory, vol. 7 (2009)","key":"21_CR21"},{"issue":"2","key":"21_CR22","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. Theor. Comput. Sci. 5(2), 101\u2013111 (1977)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"21_CR23","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":"21_CR24","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 Theor. Dyn. Syst. 24, 609\u2013619 (2004)","journal-title":"Ergodic Theor. Dyn. Syst."},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-540-30550-7_29","volume-title":"Developments in Language Theory","author":"I Potapov","year":"2004","unstructured":"Potapov, I.: From post systems to the reachability problems for matrix semigroups and multicounter automata. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 345\u2013356. Springer, Heidelberg (2004). doi: 10.1007\/978-3-540-30550-7_29"},{"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":"21_CR26"},{"unstructured":"Potapov, I., Semukhin, P.: Vector reachability problem in SL $$(2, \\mathbb{Z})$$ . In: 41st International Symposium on Mathematical Foundations of Computer Science, pp. 84:1\u201384:14 (2016)","key":"21_CR27"},{"key":"21_CR28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511566035","volume-title":"Modular Forms and Functions","author":"R Rankin","year":"1977","unstructured":"Rankin, R.: Modular Forms and Functions. Cambridge University Press, Cambridge (1977)"},{"key":"21_CR29","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"},{"doi-asserted-by":"crossref","unstructured":"Witten, E.: SL $$(2, \\mathbb{Z})$$ action on three-dimensional conformal field theories with abelian symmetry, vol. 2, pp. 1173\u20131200 (2005)","key":"21_CR30","DOI":"10.1142\/9789812775344_0028"},{"issue":"6","key":"21_CR31","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."},{"doi-asserted-by":"crossref","unstructured":"Zagier, D.: Elliptic Modular Forms and Their Applications, pp. 1\u2013103 (2008)","key":"21_CR32","DOI":"10.1007\/978-3-540-74119-0_1"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2017: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-51963-0_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T10:03:43Z","timestamp":1568714623000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-51963-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319519623","9783319519630"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-51963-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}