文章基本信息

标题：On Affine Reachability Problems
本地全文：下载
作者：Stefan Jaax ; Stefan Kiefer
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：48:1-48:14
DOI：10.4230/LIPIcs.MFCS.2020.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, hence PSPACE-complete, strengthening a result by Finkel et al. that required polynomial updates. Building on recent results on two-dimensional integer matrices, we prove NP-completeness of the mortality problem for 2-dimensional integer matrices with determinants +1 and 0. Motivated by tight connections with 1-dimensional affine reachability problems without control states, we also study the complexity of a number of reachability problems in finitely generated semigroups of 2-dimensional upper-triangular integer matrices.
关键词：Counter Machines; Matrix Semigroups; Reachability