We present an algorithm which decides the shift equivalence problem for Pfinite 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 shi
3
5
6
7
8
9L·f2=0thenc niteSE(f1,f2)//specifyingLasann.operatorofbothf1andf2(s)R(s):=res(rquo(L1,L),rquo(L2,L))∈k(s)(n)C:={s∈:R(s)=0};S:= forallifS:=S∪{s}returnif
4,f2(1)=7
4,
where
L1:=(n+1)E3 (5n+4)E2+4(2n+1)E 4n,
L2:=nE3 (5n+1)E2+4(2n+1)E 4(n+1).
ComputingL:=gcrd(L1,L2)in(s)(s)(n)[E],weobtain
L=E2 4E+4,
andsinceL·f1=L·f2=0,wemayproceedasinExample1,obtainingthatf1=Esf2ifandonlyifs=8.
Example4Letf1,f2:→bede nedvia
f1(0)=5,f1(1)=
f2(0)=5,f2(1)=12554L1·f1=0,
L2·f2=0,,