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