×

Computing Gröbner bases by FGLM techniques in a non-commutative setting. (English) Zbl 0996.16033

Summary: A generalization of the FGLM technique is given to compute Gröbner bases for two-sided ideals of free finitely generated algebras. Specializations of this algorithm are presented for the cases in which the ideal is determined by either functionals or monoid (group) presentations. Generalizations are discussed in order to compute Gröbner bases on (twisted) semigroup rings.

MSC:

16Z05 Computational aspects of associative rings (general theory)
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
16D25 Ideals in associative algebras
16S10 Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.)
16S36 Ordinary and skew polynomial rings and semigroup rings
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alonso, M. E., The big mother of all the dualities, Draft (1995)
[2] Apel, J., The computation of Gröbner bases using an alternative algorithm, Prog. Comput. Sci. Appl. Logic, 15, 35-45 (1998) · Zbl 0985.16034
[3] Borges, M. A.; Borges, M., (Buchberger; Winkler, Gröbner bases property on elimination ideal in the non-commutative case (1998)), 323-337 · Zbl 0924.16001
[4] Buchberger, B., An algorithmic criterion for the solvability of algebraic systems of equations. (German), Aequat. Math., 4, 374-383 (1970)
[5] B. Buchberger, H. M. Möller, EUROCAM’82, 1982, Marseille, Springer Verlag, Berlin Heidelberg, New York, 24, 31; B. Buchberger, H. M. Möller, EUROCAM’82, 1982, Marseille, Springer Verlag, Berlin Heidelberg, New York, 24, 31
[6] Buchberger, B.; Winkler, F., (Buchberger, B.; Winkler, F., Gröbner Bases and Applications (Proceedings of the Conference 33 Years of Gröbner Bases) (1998), Cambridge University Press) · Zbl 0883.00014
[7] Faugère, J.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symb. Comput., 16, 329-344 (1993) · Zbl 0805.13007
[8] Gianni, P.; Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases, AAECC-5, LNCS 356 (1989), Minorca, Springer Verlag: Minorca, Springer Verlag Berlin Heidelberg, New York, p. 247-257
[9] Janet, M., Lecons sur les systèmes d’equations aux dérivées partielles (1929), Gauthier-Villars: Gauthier-Villars Paris · JFM 55.0276.01
[10] Kandri-Rody, A.; Weispfenning, V., Non-commutative Gröbner bases in algebras of solvable type, J. Symb. Comput., 9, 1-26 (1987) · Zbl 0715.16010
[11] Labontè, G., An algorithm for the construction of matrix representations for finite presented non-commutative algebras, J. Symb. Comput., 9, 27-38 (1990) · Zbl 0702.16011
[12] Madlener, K.; Reinert, B., Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings, Theor. Comput. Sci., 208, 3-31 (1998) · Zbl 0912.68104
[13] Marinari, M. G.; Möller, H. M.; Mora, T., Gröbner bases of ideals defined by functionals with an application to ideals of projective points, AAECC 4 (1993), p. 103-145 · Zbl 0785.13009
[14] T. Mora, Proceedings of the Joint Conference International Symposium on Symbolic and Algebraic Computation’88 and AAECC 6, 1988, 150, 161; T. Mora, Proceedings of the Joint Conference International Symposium on Symbolic and Algebraic Computation’88 and AAECC 6, 1988, 150, 161
[15] Mora, T., An introduction to commutative and non-commutative Gröbner bases, Theor. Comput. Sci., 134, 131-173 (1994) · Zbl 0824.68056
[16] Möller, H. M., (Buchberger; Winkler, Gröbner bases and numerical analysis (1998)), 159-178 · Zbl 0928.65058
[17] B. Reinert, 1995; B. Reinert, 1995
[18] Reinert, B.; Madlener, K.; Mora, T., A note on Nielsen reduction and coset enumeration, Proceeding of the International Symposium on Symbolic Algebraic Computation 98 (1998), p. 171-178 · Zbl 0922.20041
[19] Sauer, T., (Buchberger; Winkler, Polynomial interpolation of minimal degree and Gröbner bases (1998)), 483-494 · Zbl 0898.41001
[20] Zharkov, A. Yu, Solving zero-dimensional involutive systems, Prog. Math., 143, 389-399 (1996) · Zbl 0878.13019
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.