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.2016.84
URN: urn:nbn:de:0030-drops-64925
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6492/
Go to the corresponding LIPIcs Volume Portal

Potapov, Igor ; Semukhin, Pavel

Vector Reachability Problem in SL(2, Z)

pdf-format:
LIPIcs-MFCS-2016-84.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{potapov_et_al:LIPIcs:2016:6492,
  author =	{Igor Potapov and Pavel Semukhin},
  title =	{{Vector Reachability Problem in SL(2, Z)}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{84:1--84:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6492},
  URN =		{urn:nbn:de:0030-drops-64925},
  doi =		{10.4230/LIPIcs.MFCS.2016.84},
  annote =	{Keywords: matrix semigroup, vector reachability problem, special linear group, linear fractional transformation, automata and formal languages}
}

Keywords: matrix semigroup, vector reachability problem, special linear group, linear fractional transformation, automata and formal languages
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

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