A1 Refereed original research article in a scientific journal
Undecidability bounds for integer matrices using claus instances
Authors: Halava V, Harju T, Hirvensalo M
Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD
Publication year: 2007
Journal:: International Journal of Foundations of Computer Science
Journal name in source: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Journal acronym: INT J FOUND COMPUT S
Volume: 18
Issue: 5
First page : 931
Last page: 948
Number of pages: 18
ISSN: 0129-0541
DOI: https://doi.org/10.1142/S0129054107005066
Abstract
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.
UTU Research Portal