Improved matrix pair undecidability results

: Halava V, Hirvensalo M

Publisher: SPRINGER

: 2007

Acta Informatica

ACTA INFORMATICA

: ACTA INFORM

: 44

: 3-4

: 191

: 205

: 15

: 0001-5903

DOI: https://doi.org/10.1007/s00236-007-0047-y

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.