A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Improved matrix pair undecidability results
Tekijät: Halava V, Hirvensalo M
Kustantaja: SPRINGER
Julkaisuvuosi: 2007
Lehti:: Acta Informatica
Tietokannassa oleva lehden nimi: ACTA INFORMATICA
Lehden akronyymi: ACTA INFORM
Vuosikerta: 44
Numero: 3-4
Aloitussivu: 191
Lopetussivu: 205
Sivujen määrä: 15
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s00236-007-0047-y
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali