Articles

RITT-WU’S CHARACTERISTIC SET METHOD FOR ORDINARY DIFFERENCE POLYNOMIAL SYSTEMS WITH ARBITRARY ORDERING

  • GAO Xiao-Shan ,
  • YUAN Chun-Meng ,
  • ZHANG Gui-Lin
Expand
  • Key Laboratory of Mathematics Mechanization Institute of Systems Science, AMSS, Chinese Academy of Sciences, Beijing 100080, China

Received date: 2009-02-18

  Online published: 2009-07-20

Abstract

In this paper, a Ritt-Wu’s characteristic set method for ordinary difference systems is proposed, which is valid for any admissible ordering. New definition for irre-ducible chains and new zero decomposition algorithms are also proposed.

Cite this article

GAO Xiao-Shan , YUAN Chun-Meng , ZHANG Gui-Lin . RITT-WU’S CHARACTERISTIC SET METHOD FOR ORDINARY DIFFERENCE POLYNOMIAL SYSTEMS WITH ARBITRARY ORDERING[J]. Acta mathematica scientia, Series B, 2009 , 29(4) : 1063 -1080 . DOI: 10.1016/S0252-9602(09)60086-2

References


[1] Aubry P, Lazard D, Maza M M. On the Theory of Triangular Sets. Journal of Symbolic Computation, 1999, 25: 105–124


[2] Boulier F, Lazard D, Ollivier F, Petitiot M. Representation for the Radical of a Finitely Generated Dif-
ferential Ideal. Proc of ISSAC’95, 158-166, ACM Press, 1995


[3] Bouziane D, Kandri Rody A, Maˆarouf H. Unmixed-dimensional Decomposition of a Finitely Generated Perfect Differential Ideal. Journal of Symbolic Computation, 2001, 31: 631–649


[4] Chai F, Gao X S, Yuan C M. A characteristic set method for solving boolean equations and applications
in cryptanalysis of stream ciphers. Journal of Systems Science & Complexity, 2008, 21(2): 191–208


[5] Cohn R M. Difference Algebra. Interscience Pbulishers, 1965


[6] Gallo G, Mishra B. Efficient Algorithms and Bounds for Wu-Ritt Characteristic Sets, in Effective Methods
in Algebraic Geometry, Progress in Mathematics, 94, 119-142, Birkhauser, Boston, 1991


[7] Gao X S, Luo Y., Yuan C M. A characteristic set method for ordinary difference polynomial systems. Journal of Symbolic Computation, 2009, 44: 242–260


[8] Gao X S, Luo Y, Yuan C M. A Characteristic Set Method for Difference Polynomial Systems. Journal of
Symbolic Computation, 2009, 44: 242–260


[9] Halas M, Kotta U, Li Z, Wang H, Yuan C M. Submersive Rational Difference Systems and Formal Acces-
sibility. submitted to ISSAC 2009


[10] Hubert E. Factorization-free Decomposition Algorithms in Differential Algebra. Journal of Symbolic Com-
putation, 2000, 29: 641–662


[11] Kolchin E. Differential Algebra and Algebraic Groups. New York: Academic Press, 1973


[12] Kondratieva M V, Levin A B, Mikhalev A V, Pankratiev E V. Differential and Difference Dimension Polynomials. Kluwer Academic Publishers, 1999


[13] Ritt J F. Differential Algebra. Amer Math Soc Colloquium, 1950


[14] Ritt J F, Doob J L. Systems of Algebraic Difference Equations. American Journal of Mathematics, 1933, 55: 505–514


[15] Wu W T. On the Decision Problem and the Mechanization of Theorem in Elementary Geometry. Scientia
Sinica, 1978, 21: 159–172


[16] Wu W T. A constructive Theorey of Differential Algebraic Algebraic Geometry. Lect Notes in Math, No. 1255, 173-189, Springer, 1987


[17] Wu W T. Basic Principle of Mechanical Theorem Proving in Geometries (in Chinese). Beijing: Science
Press, 1984; English Version, Wien: Springer, 1994


[18] Wu W T. Mathematics Machenization. Beijing: Science Press/Kluwer, 2001


[19] Yang L, Zhang J Z, Hou X R. Non-linear Algebraic Equations and Automated Theorem Proving (in Chinese). Shanghai: Shanghai Science and Education Pub, 1996

Outlines

/