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
References
[1]SergeiA.AbramovandManuelBronstein.Hypergeometricdispersionandtheorbit
problem.InProceedingsofISSAC’00,pages8–13,2000.
[2]SergejA.Abramov.Onthesummationofrationalfunctions.Zh.vychisl.mat.Fiz,
pages1071–1075,1971.
[3]ManuelBronstein.Onsolutionsoflinearordinarydi erenceequationsintheircoef-
cient eld.JournalofSymbolicComputation,29:841–877,2000.
[4]ManuelBronsteinandMarkoPetkovˇsek.Anintroductiontopseudo-linearalgebra.
TheoreticalComputerScience,157(1):3–33,1996.
[5]MarcChardin.Di erentialresultantsandsubresultants.InProceedingsofFCT’91,
volume529ofLectureNotesinComputerScience,pages1–10,1991.
[6]Fr´ed´ericChyzakandBrunoSalvy.Non-commutativeeliminationinOrealgebras
provesmultivariateidentities.JournalofSymbolicComputation,26:187–227,1998.
[7]RichardM.Cohn.Di erenceAlgebra.IntersciencePublishers,JohnWiley&Sons,
1965.
[8]GuoqiangGe.Algorithmsrelatedtomultiplicativerepresentationsofalgebraicnum-
bers.PhDthesis,U.C.Berkeley,1993.
[9]J¨urgenGerhard.Modularalgorithmsforpolynomialbasisconversionandgreat-
estfactorialfactorization.InProceedingsofthe7thRhineWorkshopofComputerAlgebra,pages125–141,1999.
[10]J¨urgenGerhard.ModularAlgorithmsinSymbolicSummationandSymbolicIntegra-
tion,volume3218ofLNCS.Springer,2004.
[11]PeterE.Glotov.Analgorithmofsearchingthegreatestcommondivisorforore
polynomialwithpolynomialcoe cientsdependingonaparameter.ProgrammingandComputerSoftware,24(6):275–283,1998.
[12]WilliamGosper.Decisionprocedureforinde nitehypergeometricsummation.Pro-
ceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,75:40–42,1978.
[13]CurtisGreeneandHerbertS.Wilf.ClosedformsummationofC- nitesequences.
TransactionsoftheAmericanMathematicalSociety,2006.toappear.
[14]MichaelKarr.Summationin niteterms.JournaloftheACM,28:305–350,1981.
[15]MichaelKarr.Theoryofsummationin niteterms.JournalofSymbolicComputa-
tion,1(3):303–315,1985.
theelectronicjournalofcombinatorics13(2006),#R0015