Undecidability bounds for integer matrices using claus instances



: Halava V, Harju T, Hirvensalo M

Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD

: 2007

: International Journal of Foundations of Computer Science

: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

: INT J FOUND COMPUT S

: 18

: 5

: 931

: 948

: 18

: 0129-0541

DOI: https://doi.org/10.1142/S0129054107005066


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.



Last updated on 2025-14-10 at 09:58