×

A signature-based algorithm for computing Gröbner-Shirshov bases in skew solvable polynomial rings. (English) Zbl 1350.16042

Summary: Signature-based algorithms are efficient algorithms for computing Gröbner-Shirshov bases in commutative polynomial rings, and some noncommutative rings. In this paper, we first define skew solvable polynomial rings, which are generalizations of solvable polynomial algebras and (skew) PBW extensions. Then we present a signature-based algorithm for computing Gröbner-Shirshov bases in skew solvable polynomial rings over fields.

MSC:

16Z05 Computational aspects of associative rings (general theory)
16S36 Ordinary and skew polynomial rings and semigroup rings
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Software:

Plural
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [1] Adams W. W. and Loustaunau P., An introduction to Gröbner bases, Graduate Studies in Mathematics, vol. 3, American Mathematical Society, 1994.; · Zbl 0803.13015
[2] Bokut’ L. A., Chen Y., and Shum K. P., Some new results on Gröbner-Shirshov bases, Proceedings of International Conference on Algebra 2010-Advances in Algebraic Structures (W. Hemakul, S. Wahyuni, and P. W. Sy, eds.), 2012, pp. 53-102.; · Zbl 1264.16025
[3] Buchberger B., Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, Ph.D. thesis, University of Innsbruck, 1965.; · Zbl 1245.13020
[4] Bueso J. L., Gómez-Torrecillas J., and Verschoren A., Algorithmic methods in non-commutative algebra: Applications to quantum groups, Mathematical Modelling: Theory and Applications, vol. 17, Springer, 2003.; · Zbl 1063.16054
[5] Chyzak F. and Salvy B., Non-commutative elimination in Ore algebras proves multivariate identities, J. Symbolic Comput. 26 (1998), no. 2, 187-227.; · Zbl 0944.05006
[6] Faugère J. C., A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra 139 (1999), no. 1, 61-88.; · Zbl 0930.68174
[7] Faugère J. C., A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, 2002, pp. 75-83.; · Zbl 1072.68664
[8] Gallego C. and Lezama O., Gröbner bases for ideals of σ-PBW extensions, Comm. Algebra 39 (2011), no. 1, 50-75.; · Zbl 1259.16053
[9] Galligo A., Some algorithmic questions on ideals of differential operators, EUROCAL’85, Springer, 1985, pp. 413-421.; · Zbl 0634.16001
[10] Gao S., Guan Y., and Volny IV F., A new incremental algorithm for computing Gröbner bases, Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, 2010, pp. 13-19.; · Zbl 1321.68531
[11] Gao S., Volny IV F., and Wang M., A new algorithm for computing Gröbner bases, Cryptology ePrint Archive (2010).; · Zbl 1331.13018
[12] Giesbrecht M., Reid G., and Zhang Y., Non-commutative Gröbner bases in Poincaré-Birkhoff-Witt extensions, Computer Algebra in Scientific Computing (CASC), 2002.;
[13] Insa M. and Pauer F., Gröbner bases in rings of differential operators, London Math. Soc. Lecture Note Ser. (1998), 367-380.; · Zbl 0945.13021
[14] Kandri-Rody A. and Weispfenning V., Non-commutative Gröbner bases in algebras of solvable type, J. Symbolic Comput. 9 (1990), no. 1, 1-26.; · Zbl 0715.16010
[15] Levandovskyy V. and Schönemann H., Plural: a computer algebra system for noncommutative polynomial algebras, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ACM, 2003, pp. 176-183.; · Zbl 1072.68681
[16] Ma X., Sun Y., and Wang D., On computing Gröbner bases in rings of differential operators, Sci. China Math. 54 (2011), no. 6, 1077-1087.; · Zbl 1236.13010
[17] Mansfield E. L. and Szanto A., Elimination theory for differential difference polynomials, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ACM, 2003, pp. 191-198.; · Zbl 1072.68684
[18] Oh S.-Q., Catenarity in a class of iterated skew polynomial rings, Comm. Algebra 25 (1997), no. 1, 37-49.; · Zbl 0872.16018
[19] Shirshov A. I., Some algorithmic problems for Lie algebras, Sibirsk. Mat. Zh. 3 (1962), no. 2, 292-296.; · Zbl 0104.26004
[20] Sun Y., Wang D., Ma X., and Zhang Y., A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras, Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation, ACM, 2012, pp. 351-358.; · Zbl 1308.68193
[21] Zhang Y. and Zhao X., Gelfand-Kirillov dimension of differential difference algebras, LMS J. Comput. Math. 17 (2014), no. 1, 485- 495.; · Zbl 1351.16022
[22] Zhou M. and Winkler F., On computing Gröbner bases in rings of differential operators with coefficients in a ring, Math. Comput. Sci. 1 (2007), no. 2, 211-223.; · Zbl 1132.68075
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.