Frontiers of Mathematics in China >

2015 , Vol. 10 >Issue 3: 635 - 648

DOI: https://doi.org/10.1007/s11464-015-0439-1

RESEARCH ARTICLE

Termination of algorithm for computing relative Gröbner bases and difference differential dimension polynomials

  • Guanli HUANG 1,2 ,
  • Meng ZHOU , 1
Expand
  • 1. School of Mathematics and System Science, LMIB, Beihang University, Beijing 100191, China
  • 2. Beijing Polytechnic, Beijing 100176, China

Received date: 14 Jun 2014

Accepted date: 03 Nov 2014

Published date: 01 Apr 2015

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

Abstract

We introduce the concept of difference-differential degree compatibility on generalized term orders. Then we prove that in the process of the algorithm the polynomials with higher and higher degree would not be produced, if the term orders ‘≺’ and ‘≺′’ are difference-differential degree compatibility. So we present a condition on the generalized orders and prove that under the condition the algorithm for computing relative Gröbner bases will terminate. Also the relative Gröbner bases exist under the condition. Finally, we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.

Key words： Relative Gröbner basis; difference-differential module; bivariate dimension polynomial; termination of algorithm

Cite this article

Guanli HUANG , Meng ZHOU . Termination of algorithm for computing relative Gröbner bases and difference differential dimension polynomials[J]. Frontiers of Mathematics in China, 2015 , 10(3) : 635 -648 . DOI: 10.1007/s11464-015-0439-1

References

Publishing order | Descend order by publishing year | Descend order by cited within
1
Dönch C. Bivariate difference-differential dimension polynomials and their computation in Maple. Proceedings of the 8th International Conference on Applied Informatics, Eger, Hungary, January 27-30, 2010, Vol 1. 2010, 221-228

2
Dönch C. Characterization of relative Gröbner bases. J Symbolic Comput, 2013, 55: 19-29

DOI

3
Insa M, Pauer F. Gröbner bases in rings of differential operators. In: Buchberger B, Winkler F, eds. Gröbner Bases and Applications. London Math Soc Lecture Note Ser,Vol 251. Cambridge: Cambridge University Press, 1998, 367-380

DOI

4
Kolchin E R. The notion of dimension in the theory of algebraic differential equations. Bull Amer Math Soc, 1964, 70: 570-573

DOI

5
Levin A.B. Reduced Gröbner bases, free difference-differential modules and differencedifferential dimension polynomials. J Symbolic Comput, 2000, 30(4): 357-382

DOI

6
Levin A B. Gröbner bases with respect to several orderings and multivariable dimension polynomials. J Symbolic Comput, 2007, 42(5): 561-578

DOI

7
Noumi N M. Wronskian determinants and the Gröbner representation of linear differential equation. In: Algebraic Analysis. Boston: Academic Press, 1988, 549-569

DOI

8
Oaku T, Shimoyama T. A Gröbner basis method for modules over rings of differential operators. J Symbolic Comput, 1994, 18(3): 223-248

DOI

9
Pauer F, Unterkircher A. Gröbner bases for ideals in Laurent polynomial rings and their applications to systems of difference equations. Appl Algebra Engrg Comm Comput, 1999, 9: 271-291

DOI

10
Takayama N. Gröbner basis and the problem of contiguous relations. Japan J Appl Math, 1989, 6: 147-160

DOI

11
Zhou M, Winkler F. Gröbner bases in difference-differential modules. Proceedings ISSAC 2006. New York: ACM Press, 2006: 353-360

DOI

12
Zhou M, Winkler F. Computing difference-differential dimension polynomials by relative Gröbner bases in difference-differential modules. J Symbolic Comput, 2008, 43: 726-745

DOI

Options
Outlines

/

〈 〉