Shift equivalence of P-finite sequences (Q870019)

Summary: We present an algorithm which decides the shift equivalence problem for P-finite sequences. A sequence is called P-finite if it satisfies a homogeneous linear recurrence equation with polynomial coefficients. Two sequences are called shift equivalent if shifting one of the sequences \(s\) times makes it identical to the other, for some integer \(s\). Our algorithm computes, for any two P-finite sequences, given via recurrence equation and initial values, all integers \(s\) such that shifting the first sequence \(s\) times yields the second.