×

Standard Gröbner-Shirshov bases of free algebras over rings. I: Free associative algebras. (English) Zbl 0923.16024

Standard bases of ideals of free associative algebras over rings are under consideration. The main result of the article is a criterion for a subset of a free associative algebra to be a standard basis of the ideal it generates. Using this result the authors obtain an infinite algorithm to construct the reduced standard basis of an ideal (a generalization for some semigroup algebras is presented). They also describe a way to construct weak standard bases and reduced standard bases of ideals of a free associative algebra over an arbitrary finitely generated ring (over a finitely generated algebra over a field). Some examples of constructions of standard bases and of solutions of the equality problem are included.

MSC:

16S15 Finite generation, finite presentability, normal forms (diamond lemma, term-rewriting)
16S10 Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.)
68W30 Symbolic computation and algebraic computation
68Q42 Grammars and rewriting systems
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1090/S0002-9947-1986-0846601-5 · doi:10.1090/S0002-9947-1986-0846601-5
[2] DOI: 10.1016/S0747-7171(88)80053-1 · Zbl 0663.68044 · doi:10.1016/S0747-7171(88)80053-1
[3] DOI: 10.1007/3-540-51517-8_156 · Zbl 1209.68663 · doi:10.1007/3-540-51517-8_156
[4] DOI: 10.1016/0022-314X(83)90021-5 · Zbl 0516.13018 · doi:10.1016/0022-314X(83)90021-5
[5] DOI: 10.1007/BFb0016860 · doi:10.1007/BFb0016860
[6] Bayer D., Sympos. Math. X X X I pp 198– (1993)
[7] DOI: 10.1016/S0747-7171(08)80056-9 · Zbl 0726.16027 · doi:10.1016/S0747-7171(08)80056-9
[8] DOI: 10.1016/0001-8708(78)90010-5 · Zbl 0326.16019 · doi:10.1016/0001-8708(78)90010-5
[9] Bokut’ L. A., Izv. Akad. Nauk SSSR Ser. Mat. 3 pp 1173–
[10] Bokut’ L. A., Trudy Mat. Inst. Steklov. 148 pp 30– (1978)
[11] Bokut’ L. A., Sibirsk. Mat. Zh. 22 (3) pp 15– (1981)
[12] DOI: 10.1142/S0218196796000222 · Zbl 0866.17007 · doi:10.1142/S0218196796000222
[13] Bokut’ L. A., Sibirsk. Mat. Zh. 32 (6) pp 12– (1991)
[14] DOI: 10.1007/BF02785535 · Zbl 0910.17004 · doi:10.1007/BF02785535
[15] DOI: 10.1007/3-540-13331-3_39 · doi:10.1007/3-540-13331-3_39
[16] Buchberger B., Proc. Logic and Machines: Decision Problems and Complexity. Springer-Verlag pp 137– (1983)
[17] DOI: 10.1016/S0747-7171(87)80020-2 · Zbl 0645.68094 · doi:10.1016/S0747-7171(87)80020-2
[18] Buchberger B., Wien pp 11– (1983)
[19] Dershowitz N., North-Holland pp 243– (1990)
[20] Dorr H., Lecture Notes in Comput. Sci. pp 922– (1995)
[21] Evans T., Proc. Cambridge Philos. Soc. 4 pp 7– (1951)
[22] DOI: 10.1112/jlms/s1-26.1.64 · Zbl 0042.03303 · doi:10.1112/jlms/s1-26.1.64
[23] DOI: 10.1090/S0002-9947-1963-0153727-5 · doi:10.1090/S0002-9947-1963-0153727-5
[24] DOI: 10.5802/aif.745 · Zbl 0412.32011 · doi:10.5802/aif.745
[25] DOI: 10.1007/BF01188747 · Zbl 0809.13016 · doi:10.1007/BF01188747
[26] DOI: 10.1006/jabr.1996.0348 · Zbl 0863.16016 · doi:10.1006/jabr.1996.0348
[27] DOI: 10.1016/S0747-7171(88)80054-3 · Zbl 0663.68045 · doi:10.1016/S0747-7171(88)80054-3
[28] Gerdt V. P., Singapore pp 312– (1991)
[29] DOI: 10.1006/jsco.1996.0016 · Zbl 0876.17002 · doi:10.1006/jsco.1996.0016
[30] DOI: 10.1007/3-540-51084-2_29 · doi:10.1007/3-540-51084-2_29
[31] Gluhov M. M., Soviet Math. Dokl. 1 pp 519– (1960)
[32] DOI: 10.1007/BFb0082019 · doi:10.1007/BFb0082019
[33] Golod E. S., Proc. Steklov Inst. Math. 208 pp 96– (1995)
[34] Grigorchuk R. I., Zametki 58 pp 653– (1995)
[35] DOI: 10.1007/BFb0100735 · doi:10.1007/BFb0100735
[36] DOI: 10.1145/322217.322230 · Zbl 0458.68007 · doi:10.1145/322217.322230
[37] Jouannaud J.-P., Springer-Verlag pp 271– (1995)
[38] DOI: 10.1007/3-540-59340-3_1 · doi:10.1007/3-540-59340-3_1
[39] DOI: 10.1016/0304-3975(92)90165-C · Zbl 0759.68047 · doi:10.1016/0304-3975(92)90165-C
[40] DOI: 10.1007/BFb0032842 · doi:10.1007/BFb0032842
[41] DOI: 10.1016/S0747-7171(88)80020-8 · Zbl 0658.13016 · doi:10.1016/S0747-7171(88)80020-8
[42] DOI: 10.1016/S0747-7171(08)80003-X · Zbl 0715.16010 · doi:10.1016/S0747-7171(08)80003-X
[43] DOI: 10.1142/S0218196795000227 · Zbl 0837.08002 · doi:10.1142/S0218196795000227
[44] Lalonde P., Trans. Amer. Math. Soc. 3 pp 1821–
[45] Latyshev V. N., Vestnik Kiev. Univ. Mat. Mekh. 27 pp 67– (1985)
[46] DOI: 10.1006/jsco.1996.0053 · Zbl 0865.68070 · doi:10.1006/jsco.1996.0053
[47] DOI: 10.1006/jsco.1996.0011 · Zbl 0859.68050 · doi:10.1006/jsco.1996.0011
[48] Mikhalev A. A., Mat. Zametki 3 pp 653–
[49] Mikhalev A. A., Dokl. Akad. Nauk 286 (3) pp 551– (1986)
[50] Mikhalev A. A., Mat. Zametki 4 pp 178–
[51] Mikhalev A. A., Vestnik Moskov. Univ. Ser. I Mat. Mekh. 5 pp 88– (1989)
[52] DOI: 10.1090/conm/131.2/1175824 · doi:10.1090/conm/131.2/1175824
[53] Mikhalev A. A., Uspekhi Mat. Nauk 48 (5) pp 179– (1993)
[54] Mikhalev A. A., Trudy Sem. Petrovsk. 18 pp 277– (1995)
[55] DOI: 10.1080/00927879808826139 · Zbl 0892.17002 · doi:10.1080/00927879808826139
[56] Mikhalev A. A., Matem. 2 pp 611– (1996)
[57] DOI: 10.1006/jsco.1996.0006 · Zbl 0867.13007 · doi:10.1006/jsco.1996.0006
[58] Mora T., Sci. 229 pp 353– (1986)
[59] Mora T., Comput. Sci. 358 pp 150– (1988)
[60] DOI: 10.1016/0304-3975(94)90283-6 · Zbl 0824.68056 · doi:10.1016/0304-3975(94)90283-6
[61] DOI: 10.1016/0021-8693(86)90071-2 · Zbl 0621.13007 · doi:10.1016/0021-8693(86)90071-2
[62] Newman M. H. A., Ann. Math. 4 pp 3– (1942)
[63] Ollivier F., Birkhauser pp 379– (1991)
[64] DOI: 10.1016/S0747-7171(89)80006-9 · Zbl 0668.68034 · doi:10.1016/S0747-7171(89)80006-9
[65] DOI: 10.1016/0747-7171(92)90018-Y · Zbl 0776.13014 · doi:10.1016/0747-7171(92)90018-Y
[66] Pauer F, Enseign. Math. 34 pp 215– (1988)
[67] DOI: 10.1006/jsco.1996.0040 · Zbl 0954.16019 · doi:10.1006/jsco.1996.0040
[68] DOI: 10.4153/CJM-1960-044-x · Zbl 0093.25503 · doi:10.4153/CJM-1960-044-x
[69] Richman F., Proc. Amer. Math. Soc. 4 pp 4– (1974)
[70] DOI: 10.1016/0550-3213(78)90186-4 · doi:10.1016/0550-3213(78)90186-4
[71] DOI: 10.1016/S0747-7171(86)80019-0 · Zbl 0609.13007 · doi:10.1016/S0747-7171(86)80019-0
[72] DOI: 10.1063/1.524113 · Zbl 0423.17003 · doi:10.1063/1.524113
[73] DOI: 10.2307/2373905 · Zbl 0416.13013 · doi:10.2307/2373905
[74] Shirshov A. I., Mat. Sb. 45 pp 113– (1958)
[75] Shirshov A. I., Sibirsk. Mat. Zh. 3 pp 132– (1962)
[76] Shirshov A. I., Sibirsk. Mat. Zh. 3 pp 292– (1962)
[77] Shirshov A. I., Sibirsk. Mat. Zh. 3 pp 297– (1962)
[78] DOI: 10.1016/S0747-7171(87)80012-3 · Zbl 0655.13019 · doi:10.1016/S0747-7171(87)80012-3
[79] DOI: 10.1016/0021-8693(91)90166-6 · Zbl 0732.13013 · doi:10.1016/0021-8693(91)90166-6
[80] DOI: 10.1006/jabr.1993.1146 · Zbl 0807.13014 · doi:10.1006/jabr.1993.1146
[81] DOI: 10.2307/2306808 · Zbl 0047.03303 · doi:10.2307/2306808
[82] Talapov V. V., Sibirsk. Mat. Zh. 22 (4) pp 176– (1981)
[83] Comon H., Lecture Notes in Comput. Sci. pp 909– (1995)
[84] DOI: 10.1016/0022-314X(78)90019-7 · Zbl 0404.13004 · doi:10.1016/0022-314X(78)90019-7
[85] Ufiiarovski V. A., Mat. Sb. 180 pp 1548– (1989)
[86] Ufiiarovski V. A., Encyclopaedia Math. Sci. 5 pp 7– (1995)
[87] DOI: 10.1007/3-540-51517-8_137 · Zbl 1209.13036 · doi:10.1007/3-540-51517-8_137
[88] Zhegalkin I. I., Mat. Sb. 3 pp 4– (1927)
[89] Zhukov A. I., Mat. Sb. 27 pp 267– (1950)
[90] Matem. 3 pp 453– (1997)
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.