License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.44
URN: urn:nbn:de:0030-drops-80737
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8073/
Go to the corresponding LIPIcs Volume Portal

Potapov, Igor ; Semukhin, Pavel

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

pdf-format:
LIPIcs-MFCS-2017-44.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{potapov_et_al:LIPIcs:2017:8073,
  author =	{Igor Potapov and Pavel Semukhin},
  title =	{{Membership Problem in GL(2, Z) Extended by Singular Matrices}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{44:1--44:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8073},
  URN =		{urn:nbn:de:0030-drops-80737},
  doi =		{10.4230/LIPIcs.MFCS.2017.44},
  annote =	{Keywords: Matrix Semigroups, Membership Problem, General Linear Group, Singular Matrices, Automata and Formal Languages}
}

Keywords: Matrix Semigroups, Membership Problem, General Linear Group, Singular Matrices, Automata and Formal Languages
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI