Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Undecidability Bounds for Inte...

Undecidability Bounds for Integer Matrices using Claus Instances

Vesa Halava, Tero Harju, Mika Hirvensalo, Undecidability Bounds for Integer Matrices using Claus Instances. TUCS Technical Reports 766, Turku Centre for Computer Science, 2006.

Abstract:

There are several known undecidability problems for 3x3 integer matrices the proof of which uses a reduction from the Post Correspondence Problem (PCP). We establish new lower bounds in the numbers of matrices for the mortality, zero in left upper corner, vector reachability, matrix reachability, scaler 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 \subseteq \Z^{4\times 4}$ whether or not $kI_4\in R$ for any given diagonal matrix $kI_4$ with $|k| > 1$. These bounds are obtained by
using Claus instances of the PCP.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaHi06a,
  title = {Undecidability Bounds for Integer Matrices using Claus Instances},
  author = {Halava, Vesa and Harju, Tero and Hirvensalo, Mika},
  number = {766},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {Undecidability; integer matrices; mortality; vector reachability; membership problem; scalar reachability; Post Correspondence Problem},
  ISBN = {952-12-1720-0},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication