A1 Refereed original research article in a scientific journal
Improved matrix pair undecidability results
Authors: Halava V, Hirvensalo M
Publisher: SPRINGER
Publication year: 2007
Journal:: Acta Informatica
Journal name in source: ACTA INFORMATICA
Journal acronym: ACTA INFORM
Volume: 44
Issue: 3-4
First page : 191
Last page: 205
Number of pages: 15
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s00236-007-0047-y
Abstract
We improve the undecidability bounds for problems involving two integer matrices by showing that Scalar Reachability, Zero in the Right Upper Corner, Vector Reachability, and Zero in the Left Upper Corner are undecidable for dimensions of 9, 10, 11, and 13, respectively. Problems Scalar Reachability, Zero in the Right Upper Corner, and Vector Reachability were previously known undecidable for dimensions 18, 18, and 16, respectively.
We improve the undecidability bounds for problems involving two integer matrices by showing that Scalar Reachability, Zero in the Right Upper Corner, Vector Reachability, and Zero in the Left Upper Corner are undecidable for dimensions of 9, 10, 11, and 13, respectively. Problems Scalar Reachability, Zero in the Right Upper Corner, and Vector Reachability were previously known undecidable for dimensions 18, 18, and 16, respectively.
UTU Research Portal