On Reachability Problems for Low-Dimensional Matrix Semigroup

Semukhin, P, Colcombet, T, Ouaknine, J and Worrell, J (2019) On Reachability Problems for Low-Dimensional Matrix Semigroup. In: LIPIcs : Leibniz International Proceedings in Informatics , 132 (44). 44:1-44:15. (46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 08 July 2019 - 12 July 2019, Patras, Greece).

Preview

Text On Reachability Problems for Low-Dimensional Matrix Semigroups.pdf - Published Version Available under License Creative Commons Attribution. Download (532kB) | Preview

Abstract

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.

Item Type:	Conference or Workshop Item (Paper)
Uncontrolled Keywords:	membership problem; half-space reachability problem; matrix semigroups; Heisenberg group; general linear group
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	Computer Science and Mathematics
Publisher:	Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Date of acceptance:	18 February 2019
Date of first compliant Open Access:	25 February 2022
Date Deposited:	25 Feb 2022 10:11
Last Modified:	13 Apr 2022 15:18
DOI or ID number:	10.4230/LIPIcs.ICALP.2019.44
URI:	https://researchonline.ljmu.ac.uk/id/eprint/16414

View Item