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

Skolem's Problem - On the Border between Decidability and Undecidability

Vesa Halava, Tero Harju, Mika Hirvensalo, Juhani Karhumäki, Skolem's Problem - On the Border between Decidability and Undecidability. TUCS Technical Reports 683, Turku Centre for Computer Science, 2005.

Abstract:

We give a survey of Skolem's problem for linear recurrence sequences. We cover the known decidable cases for recurrence depths of at most 4, and give detailed proofs for these cases. Moreover, we shall prove that
the problem is decidable for linear recurrences of depth 5.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaHiKa05a,
  title = {Skolem's Problem - On the Border between Decidability and Undecidability},
  author = {Halava, Vesa and Harju, Tero and Hirvensalo, Mika and Karhumäki, Juhani},
  number = {683},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2005},
  keywords = {Skolem's Problem, Linear Recurrence, Undecidability, Matrix Problems},
  ISBN = {952-12-1534-8},
}

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

Edit publication