×

Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\). (English) Zbl 1421.68095

Summary: This paper solves three open problems about the decidability of the vector and scalar reachability problems and the point to point reachability by fractional linear transformations over finitely generated semigroups of matrices from \(\operatorname{SL}(2, \mathbb{Z})\). Our approach to solving these problems is based on the characterization of reachability paths between vectors or points, which is then used to translate the numerical problems on matrices into computational problems on words and regular languages. We will also give geometric interpretations of these results.

MSC:

68Q45 Formal languages and automata
15A30 Algebraic systems of matrices
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Markov, A., On certain insoluble problems concerning matrices, Dokl. Akad. Nauk SSSR, 57, 6, 539-542 (1947)
[2] Halava, V.; Harju, T.; Hirvensalo, M.; Karhumaki, J., Skolem’s Problem — On the Border Between Decidability and Undecidability (2005), Turku Centre for Computer Science, Tech. Rep. 683
[3] Ouaknine, J.; Worrell, J., On the positivity problem for simple linear recurrence sequences, (Automata, Languages, and Programming - 41st International Colloquium, Proceedings, Part II. Automata, Languages, and Programming - 41st International Colloquium, Proceedings, Part II, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014 (2014)), 318-329 · Zbl 1410.11134
[4] Ouaknine, J.; Worrell, J., Ultimate positivity is decidable for simple linear recurrence sequences, (Automata, Languages, and Programming - 41st International Colloquium, Proceedings, Part II. Automata, Languages, and Programming - 41st International Colloquium, Proceedings, Part II, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014 (2014)), 330-341 · Zbl 1410.11135
[5] Galby, E.; Ouaknine, J.; Worrell, J., On matrix powering in low dimensions, (Mayr, E. W.; Ollinger, N., 32nd International Symposium on Theoretical Aspects of Computer Science. 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015. 32nd International Symposium on Theoretical Aspects of Computer Science. 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, LIPIcs. Leibniz Int. Proc. Inform., vol. 30 (2015), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 329-340 · Zbl 1355.68117
[6] Ouaknine, J.; Pinto, J.a. S.; Worrell, J., On termination of integer linear loops, (Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15 (2015), SIAM), 957-969 · Zbl 1372.68065
[7] Bell, P.; Potapov, I., On undecidability bounds for matrix decision problems, Theor. Comput. Sci., 391, 1-2, 3-13 (2008) · Zbl 1133.03019
[8] Blondel, V. D.; Jeandel, E.; Koiran, P.; Portier, N., Decidable and undecidable problems about quantum automata, SIAM J. Comput., 34, 6, 1464-1473 (2005) · Zbl 1078.81012
[9] Esparza, J.; Finkel, A.; Mayr, R., On the verification of broadcast protocols, (Logic in Computer Science, 1999. Proceedings. 14th Symposium on (1999)), 352-359
[10] Bell, P. C.; Potapov, I., On the computational complexity of matrix semigroup problems, Fundam. Inform., 116, 1-4, 1-13 (2012) · Zbl 1242.68120
[11] Cassaigne, J.; Harju, T.; Karhumaki, J., On the undecidability of freeness of matrix semigroups, Int. J. Algebra Comput., 09, 03n04, 295-305 (1999) · Zbl 1029.20027
[12] Bell, P.; Potapov, I., Reachability problems in quaternion matrix and rotation semigroups, Inf. Comput., 206, 11, 1353-1361 (2008) · Zbl 1151.03021
[13] Choffrut, C.; Karhumaki, J., Some decision problems on integer matrices, RAIRO Theor. Inform. Appl., 39, 1, 125-131 (2005) · Zbl 1081.20066
[14] Cassaigne, J.; Nicolas, F., On the decidability of semigroup freeness, RAIRO Theor. Inform. Appl., 46, 3, 355-399 (2012) · Zbl 1252.20050
[15] Charlier, E.; Honkala, J., The freeness problem over matrix semigroups and bounded languages, Inf. Comput., 237, 243-256 (2014) · Zbl 1294.15013
[16] Bell, P. C.; Hirvensalo, M.; Potapov, I., Mortality for 2x2 matrices is NP-hard, (Rovan, B.; Sassone, V.; Widmayer, P., Mathematical Foundations of Computer Science 2012. Mathematical Foundations of Computer Science 2012, Lect. Notes Comput. Sci., vol. 7464 (2012), Springer Berlin Heidelberg), 148-159 · Zbl 1365.68265
[17] Gurevich, Y.; Schupp, P., Membership problem for the modular group, SIAM J. Comput., 37, 2, 425-459 (2007) · Zbl 1136.03013
[18] Potapov, I.; Semukhin, P., Decidability of the membership problem for \(2 \times 2\) integer matrices, (Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, 2017 (2017)), 170-186 · Zbl 1410.68245
[19] Potapov, I.; Semukhin, P., Membership problem in \(GL(2, Z)\) extended by singular matrices, (42nd International Symposium on Mathematical Foundations of Computer Science. 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, Aalborg, Denmark, August 21-25, 2017 (2017)), 44:1-44:13 · Zbl 1441.20037
[20] Bell, P. C.; Hirvensalo, M.; Potapov, I., The identity problem for matrix semigroups in \(SL_2(Z)\) is NP-complete, (Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, 2017 (2017)), 187-206 · Zbl 1410.68139
[21] Ko, S.; Potapov, I., Matrix semigroup freeness problems in \(SL(2, Z)\), (SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017 (2017)), 268-279 · Zbl 1444.20034
[22] Zagier, D., Elliptic modular forms and their applications, (Ranestad, K., The 1-2-3 of Modular Forms. The 1-2-3 of Modular Forms, Universitext (2008), Springer Berlin Heidelberg), 1-103 · Zbl 1259.11042
[23] Chamizo, F., Non-euclidean visibility problems, Proc. Indian Acad. Sci. Math. Sci., 116, 2, 147-160 (2006) · Zbl 1126.11033
[24] Elstrodt, J.; Grunewald, F.; Mennicke, J., Arithmetic applications of the hyperbolic lattice point theorem, Proc. Lond. Math. Soc., s3, 57, 239-283 (1988) · Zbl 0752.11018
[25] Polterovich, L.; Rudnick, Z., Stable mixing for cat maps and quasi-morphisms of the modular group, Ergod. Theory Dyn. Syst., 24, 609-619 (2004) · Zbl 1071.37019
[26] Mackenzie, D., A new twist in knot theory, (What’s Happening in the Mathematical Sciences, vol. 7 (2009))
[27] Potapov, I., Composition problems for braids, (33nd International Conference on Foundations of Software Technology and Theoretical Computer Science. 33nd International Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 24 (2013), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), 175-187 · Zbl 1359.68142
[28] Witten, E., \(SL(2, Z)\) action on three-dimensional conformal field theories with abelian symmetry, (From Fields to Strings: Circumnavigating Theoretical Physics, vol. 2 (2005), World Sci. Publ.: World Sci. Publ. Singapore), 1173-1200 · Zbl 1160.81457
[29] García del Moral, M. P.; Martín, I.; Peña, J. M.; Restuccia, A., Sl(2,z) symmetries, supermembranes and symplectic torus bundles, J. High Energy Phys., 2011, 9, 1-12 (2011) · Zbl 1301.81202
[30] Noll, T., Musical intervals and special linear transformations, J. Math. Music, 1, 2, 121-137 (2007) · Zbl 1181.00022
[31] Babai, L.; Beals, R.; Cai, J.-y.; Ivanyos, G.; Luks, E. M., Multiplicative equations over commuting matrices, (Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’96 (1996), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 498-507 · Zbl 0865.15012
[32] Lisitsa, A.; Potapov, I., Membership and reachability problems for row-monomial transformations, (Mathematical Foundations of Computer Science 2004, 29th International Symposium, Proceedings. Mathematical Foundations of Computer Science 2004, 29th International Symposium, Proceedings, MFCS 2004, Prague, Czech Republic, August 22-27, 2004 (2004)), 623-634 · Zbl 1096.68108
[33] Halava, V.; Harju, T.; Hirvensalo, M., Undecidability bounds for integer matrices using Claus instances, Int. J. Found. Comput. Sci., 18, 05, 931-948 (2007) · Zbl 1202.03052
[34] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory, Ergeb. Math. Grenzgeb., vol. 89 (1977), Springer-Verlag: Springer-Verlag Berlin-New York · Zbl 0368.20023
[35] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations (1976), Dover Publications, Inc.: Dover Publications, Inc. New York · Zbl 0362.20023
[36] Rankin, R. A., Modular Forms and Functions (1977), Cambridge University Press: Cambridge University Press Cambridge-New York-Melbourne · Zbl 0376.10020
[37] Bell, P.; Halava, V.; Harju, T.; Karhumäki, J.; Potapov, I., Matrix equations and Hilbert’s tenth problem, Int. J. Algebra Comput., 18, 8, 1231-1241 (2008) · Zbl 1173.03009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.