A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Undecidability bounds for integer matrices using claus instances
Tekijät: Halava V, Harju T, Hirvensalo M
Kustantaja: WORLD SCIENTIFIC PUBL CO PTE LTD
Julkaisuvuosi: 2007
Lehti:: International Journal of Foundations of Computer Science
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Lehden akronyymi: INT J FOUND COMPUT S
Vuosikerta: 18
Numero: 5
Aloitussivu: 931
Lopetussivu: 948
Sivujen määrä: 18
ISSN: 0129-0541
DOI: https://doi.org/10.1142/S0129054107005066
Tiivistelmä
There are several known undecidable problems for 3 x 3 integer matrices the proof of which use a reduction from the Post Correspondence Problem (PCP). We establish new lower bounds in the number of matrices for the mortality, zero in the left upper corner, vector reachability, matrix reachability, scalar reachability and freeness problems. Also, we give a short proof for a strengthened result due to Bell and Potapov stating that the membership problem is undecidable for finitely generated matrix semigroups R subset of Z(4x4) whether or not KI4 is an element of R for any given vertical bar k vertical bar > 1. These bounds axe obtained by using the Claus instances of the PCP.
There are several known undecidable problems for 3 x 3 integer matrices the proof of which use a reduction from the Post Correspondence Problem (PCP). We establish new lower bounds in the number of matrices for the mortality, zero in the left upper corner, vector reachability, matrix reachability, scalar reachability and freeness problems. Also, we give a short proof for a strengthened result due to Bell and Potapov stating that the membership problem is undecidable for finitely generated matrix semigroups R subset of Z(4x4) whether or not KI4 is an element of R for any given vertical bar k vertical bar > 1. These bounds axe obtained by using the Claus instances of the PCP.
Turun yliopiston Tutkimustietojärjestelmän portaali