• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Improved Matrix Pair Undecidability Results

Vesa Halava, Mika Hirvensalo, Improved Matrix Pair Undecidability Results. TUCS Technical Reports 799, Turku Centre for Computer Science, 2006.

Abstract:

We improve undecidability bounds for problems involving two integer matrices. We prove that <I>Scalar Reachability</I>,
<I>Zero in the Right Upper Corner</I>,
<I>Vector Reachability</I>, and
<I>Zero in the Left Upper Corner</I> are
undecidable for dimensions of
9, 10, 11, and 13, respectively.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHi06a,
  title = {Improved Matrix Pair Undecidability Results},
  author = {Halava, Vesa and Hirvensalo, Mika},
  number = {799},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  ISBN = {952-12-1840-1},
}

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

Edit publication