文章基本信息

标题：On Reachability Problems for Low-Dimensional Matrix Semigroups
本地全文：下载
作者：Thomas Colcombet ; Jo{"e}l Ouaknine ; Pavel Semukhin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-15
DOI：10.4230/LIPIcs.ICALP.2019.44
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the Membership and the Half-Space Reachability problems for matrices in dimensions two and three. Our first main result is that the Membership Problem is decidable for finitely generated sub-semigroups of the Heisenberg group over rational numbers. Furthermore, we prove two decidability results for the Half-Space Reachability Problem. Namely, we show that this problem is decidable for sub-semigroups of GL(2,Z) and of the Heisenberg group over rational numbers.
关键词：membership problem; half-space reachability problem; matrix semigroups; Heisenberg group; general linear group