Document Open Access Logo

Membership Problem in GL(2, Z) Extended by Singular Matrices

Authors Igor Potapov, Pavel Semukhin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.44.pdf
  • Filesize: 0.48 MB
  • 13 pages

Document Identifiers

Author Details

Igor Potapov
Pavel Semukhin

Cite As Get BibTex

Igor Potapov and Pavel Semukhin. Membership Problem in GL(2, Z) Extended by Singular Matrices. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.44

Abstract

We consider the membership problem for matrix semigroups, which is the problem to decide whether a matrix belongs to a given finitely generated matrix semigroup. 

In general, the decidability and complexity of this problem for two-dimensional matrix semigroups remains open. Recently there was a significant progress with this open problem by showing that the membership is decidable for 2x2 nonsingular integer matrices. In this paper we focus on the membership for singular integer matrices and prove that this problem is decidable for 2x2 integer matrices whose determinants are equal to 0, 1, -1 (i.e. for matrices from GL(2,Z) and any singular matrices). Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words and conversion of the membership problem into decision problem on regular languages.

Subject Classification

Keywords
  • Matrix Semigroups
  • Membership Problem
  • General Linear Group
  • Singular Matrices
  • 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 and Igor Potapov. On undecidability bounds for matrix decision problems. Theoretical Computer Science, 391(1-2):3-13, 2008. Google Scholar
  3. 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
  4. Paul C. Bell, Mika Hirvensalo, and Igor Potapov. The identity problem for matrix semigroups in SL₂(ℤ) is NP-complete. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 187-206, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.13.
  5. Paul C. Bell and Igor Potapov. On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. Int. J. Found. Comput. Sci., 21(6):963-978, 2010. 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, Vesa Halava, Tero Harju, and François Nicolas. Tighter undecidability bounds for matrix mortality, zero-in-the-corner problems, and more. CoRR, abs/1404.0644, 2014. Google Scholar
  9. Christian Choffrut and Juhani Karhumaki. Some decision problems on integer matrices. RAIRO-Theor. Inf. Appl., 39(1):125-131, 2005. Google Scholar
  10. 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
  11. 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
  12. Yuri Gurevich and Paul Schupp. Membership problem for the modular group. SIAM J. Comput., 37(2):425-459, May 2007. Google Scholar
  13. 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
  14. R. Kannan and R. J. Lipton. Polynomial-time algorithm for the orbit problem. J. ACM, 33(4):808-821, August 1986. URL: http://dx.doi.org/10.1145/6490.6496.
  15. 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
  16. 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
  17. 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
  18. 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
  19. C. Nuccio and Emanuele Rodaro. Mortality problem for 2times2 integer matrices. In SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, pages 400-405, 2008. URL: http://dx.doi.org/10.1007/978-3-540-77566-9_34.
  20. 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
  21. 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
  22. 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
  23. M. S. Paterson. Unsolvability in 3times3 matrices. Studies in Applied Mathematics, 49(1):pp.105-107, 1970. Google Scholar
  24. Igor Potapov and Pavel Semukhin. Vector reachability problem in SL(2,Z). In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 84:1-84:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.84.
  25. Igor Potapov and Pavel Semukhin. Decidability of the membership problem for 2times2 integer matrices. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 170-186, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.12.
  26. Robert A. Rankin. Modular forms and functions. Cambridge University Press, Cambridge-New York-Melbourne, 1977. 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