###
Decidable Cases of the Rational Sequence Problem

B. Litow

Department of Computer Science,
James Cook University
Townsville 4811, Australia.

bruce@cs.jcu.edu.au

#### Abstract

Determining whether or not there is a
vanishing term of a linear recurrence with
rational coefficients is the Rational Sequence Problem. The decidability
status of this problem is open. Several formulations of the problem are
presented in this paper. A decision method for determining whether or
not infinitely many terms of a linear recurrence sequence vanish is given
in terms of the Residue Theorem of complex variable theory,
A decidable case, based on transcenedental number
Theory is also discussed.
The last section details an approach to the problem based on polynomial ideal
theory.

Conference Home Page