Document Open Access Logo

Vector Reachability Problem in SL(2, Z)

Authors Igor Potapov, Pavel Semukhin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.84.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Igor Potapov
Pavel Semukhin

Cite As Get BibTex

Igor Potapov and Pavel Semukhin. Vector Reachability Problem in SL(2, Z). In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 84:1-84:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.84

Abstract

The decision problems on matrices were intensively studied for many decades as matrix products play an essential role in the representation of various computational processes. However, many computational problems for matrix semigroups are inherently difficult to solve even for problems in low dimensions and most matrix semigroup problems become undecidable in general starting from dimension three or four.

This paper solves two open problems about the decidability of the vector reachability problem over a finitely generated semigroup of matrices from SL(2, Z) and the point to point reachability (over rational numbers) for fractional linear transformations, where associated matrices are from SL(2, Z). The approach to solving reachability problems is based on the characterization of reachability paths between points which is followed by the translation of numerical problems on matrices into computational and combinatorial problems on words and formal languages. We also give a geometric interpretation of reachability paths and extend the decidability results to matrix products represented by arbitrary labelled directed graphs. Finally, we will use this technique to prove that a special case of the scalar reachability problem is decidable.

Subject Classification

Keywords
  • matrix semigroup
  • vector reachability problem
  • special linear group
  • linear fractional transformation
  • automata and formal languages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'96, pages 498-507, Philadelphia, PA, USA, 1996. Society for Industrial and Applied Mathematics. Google Scholar
  2. Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, and Igor Potapov. Matrix equations and Hilbert’s tenth problem. Internat. J. Algebra Comput., 18(8):1231-1241, 2008. Google Scholar
  3. Paul Bell and Igor Potapov. On undecidability bounds for matrix decision problems. Theoretical Computer Science, 391(1-2):3-13, 2008. Google Scholar
  4. Paul Bell and Igor Potapov. Reachability problems in quaternion matrix and rotation semigroups. Information and Computation, 206(11):1353-1361, 2008. Google Scholar
  5. Paul C. Bell, Mika Hirvensalo, and Igor Potapov. Mortality for 2x2 matrices is NP-hard. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012, volume 7464 of Lecture Notes in Computer Science, pages 148-159. Springer Berlin Heidelberg, 2012. Google Scholar
  6. Paul C. Bell and Igor Potapov. On the computational complexity of matrix semigroup problems. Fundam. Inf., 116(1-4):1-13, January 2012. Google Scholar
  7. Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and undecidable problems about quantum automata. SIAM J. Comput., 34(6):1464-1473, June 2005. Google Scholar
  8. Julien Cassaigne, Tero Harju, and Juhani Karhumaki. On the undecidability of freeness of matrix semigroups. International Journal of Algebra and Computation, 09(03n04):295-305, 1999. URL: http://dx.doi.org/10.1142/S0218196799000199.
  9. Julien Cassaigne and François Nicolas. On the decidability of semigroup freeness. RAIRO - Theor. Inf. and Applic., 46(3):355-399, 2012. Google Scholar
  10. Fernando Chamizo. Non-euclidean visibility problems. Proceedings of the Indian Academy of Sciences - Mathematical Sciences, 116(2):147-160, 2006. Google Scholar
  11. Christian Choffrut and Juhani Karhumaki. Some decision problems on integer matrices. RAIRO-Theor. Inf. Appl., 39(1):125-131, 2005. Google Scholar
  12. J. Elstrodt, F. Grunewald, and J. Mennicke. Arithmetic applications of the hyperbolic lattice point theorem. Proc. London Math. Soc., s3-57:pp.239-283, 1988. Google Scholar
  13. J. Esparza, A. Finkel, and R. Mayr. On the verification of broadcast protocols. In Logic in Computer Science, 1999. Proceedings. 14th Symposium on, pages 352-359, 1999. Google Scholar
  14. Esther Galby, Joël Ouaknine, and James Worrell. On Matrix Powering in Low Dimensions. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 329-340, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  15. M. P. García del Moral, I. Martín, J. M. Peña, and A. Restuccia. Sl(2,z) symmetries, supermembranes and symplectic torus bundles. Journal of High Energy Physics, 2011(9):1-12, 2011. Google Scholar
  16. Yuri Gurevich and Paul Schupp. Membership problem for the modular group. SIAM J. Comput., 37(2):425-459, May 2007. Google Scholar
  17. Vesa Halava, Tero Harju, and Mika Hirvensalo. Undecidability bounds for integer matrices using Claus instances. International Journal of Foundations of Computer Science, 18(05):931-948, 2007. URL: http://dx.doi.org/10.1142/S0129054107005066.
  18. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumaki. Skolem’s problem - on the border between decidability and undecidability. Technical Report 683, Turku Centre for Computer Science, 2005. Google Scholar
  19. Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput., 8(4):499-507, 1979. Google Scholar
  20. Alexei Lisitsa and Igor Potapov. Membership and reachability problems for row-monomial transformations. In Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, pages 623-634, 2004. Google Scholar
  21. Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Springer-Verlag, Berlin-New York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. Google Scholar
  22. Dana Mackenzie. A new twist in knot theory. What’s Happening in the Mathematical Sciences, Volume 7, 2009. Google Scholar
  23. Wilhelm Magnus, Abraham Karrass, and Donald Solitar. Combinatorial group theory. Dover Publications, Inc., New York, revised edition, 1976. Presentations of groups in terms of generators and relations. Google Scholar
  24. A. Markov. On certain insoluble problems concerning matrices. Doklady Akad. Nauk SSSR, 57(6):539-542, June 1947. Google Scholar
  25. Thomas Noll. Musical intervals and special linear transformations. Journal of Mathematics and Music: Mathematical and Computational Approaches to Music Theory, Analysis, Composition and Performance, vol.1, 2007. Google Scholar
  26. Joël Ouaknine, João Sousa Pinto, and James Worrell. On termination of integer linear loops. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 957-969. SIAM, 2015. Google Scholar
  27. Joël Ouaknine and James Worrell. On the positivity problem for simple linear recurrence sequences,. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 318-329, 2014. Google Scholar
  28. Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 330-341, 2014. Google Scholar
  29. Leonid Polterovich and Zeev Rudnick. Stable mixing for cat maps and quasi-morphisms of the modular group. Ergodic Theory and Dynamical Systems, 24:609-619, 4 2004. Google Scholar
  30. Igor Potapov. Composition problems for braids. In 33nd International Conference on Foundations of Software Technology and Theoretical Computer Science, volume 24 of LIPIcs. Leibniz Int. Proc. Inform., pages 175-187. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2013. Google Scholar
  31. Igor Potapov and Pavel Semukhin. Vector reachability problem in SL(2,ℤ). CoRR, abs/1510.03227, 2015. URL: http://arxiv.org/abs/1510.03227.
  32. Robert A. Rankin. Modular forms and functions. Cambridge University Press, Cambridge-New York-Melbourne, 1977. Google Scholar
  33. Edward Witten. SL(2,ℤ) action on three-dimensional conformal field theories with abelian symmetry. In From fields to strings: circumnavigating theoretical physics. Vol. 2, pages 1173-1200. World Sci. Publ., Singapore, 2005. Google Scholar
  34. Don Zagier. Elliptic modular forms and their applications. In Kristian Ranestad, editor, The 1-2-3 of Modular Forms, Universitext, pages 1-103. Springer Berlin Heidelberg, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact