×

Noncommutative Gröbner bases: applications and generalizations. (English) Zbl 1457.16046

Iohara, Kenji (ed.) et al., Two algebraic byways from differential equations: Gröbner bases and quivers. Cham: Springer. Algorithms Comput. Math. 28, 115-183 (2020).
Summary: The aim of this chapter is to provide a summary of the theory of linear rewriting and the application of this theory to the construction of free resolutions for associative algebras. In Sect. 2, we present linear polygraphs as an algebraic setting for linear rewriting without a monomial order, and we review the fundamental notion of linear polygraphs. In Sect. 3, we recall several historical constructions on linear rewriting systems for associative algebras, and we show how the confluence properties are studied in these different approaches. We relate the notion of convergent linear polygraph with the notion of noncommutative Gröbner basis. In Sect. 4, we describe an algorithmic way to compute free resolutions for algebras using a method introduced by Anick. Section 5 deals with extension of linear polygraphs, seen as higher dimensional linear rewriting systems, into polygraphic resolutions for algebras. We show how to construct such a resolution starting from a convergent presentation. In the last section, we show how to relate Koszulness for algebras with the property of confluence.
For the entire collection see [Zbl 1444.14002].

MSC:

16Z10 Gröbner-Shirshov bases
16S37 Quadratic and Koszul algebras

Software:

operads
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D.J. Anick, On monomial algebras of finite global dimension. Trans. Amer. Math. Soc. 291(1), 291-310 (1985) · Zbl 0575.16002 · doi:10.1090/S0002-9947-1985-0797061-3
[2] D.J. Anick, On the homology of associative algebras. Trans. Amer. Math. Soc. 296(2), 641-659 (1986) · Zbl 0598.16028 · doi:10.1090/S0002-9947-1986-0846601-5
[3] D.J. Anick, E.L. Green, On the homology of quotients of path algebras. Commun. Algebra 15(1-2), 309-341 (1987) · Zbl 0608.16029 · doi:10.1080/00927878708823422
[4] F. Baader, T. Nipkow, Term Rewriting and All That (Cambridge University Press, 1998) · Zbl 0948.68098
[5] J. Backelin, La série de Poincaré-Betti d’une algèbre graduée de type fini à une relation est rationnelle. C. R. Acad. Sci. Paris Sér. A-B 287(13), A843-A846 (1978) · Zbl 0395.16025
[6] J. Backelin, A distributiveness property of augmented algebras, and some related homological results. Ph.D. thesis, Stockholm University, 1983
[7] J. Backelin, R. Fröberg, Koszul algebras, Veronese subrings and rings with linear resolutions. Rev. Roumaine Math. Pures Appl. 30(2), 85-97 (1985) · Zbl 0583.16017
[8] T. Becker, V. Weispfenning, Gröbner Bases. Graduate Texts in Mathematics, vol. 141 (Springer, New York, 1993). A computational approach to commutative algebra, in cooperation with Heinz Kredel · Zbl 0772.13010
[9] R. Berger, Confluence and Koszulity. J. Algebra 201(1), 243-283 (1998) · Zbl 0915.16025 · doi:10.1006/jabr.1997.7249
[10] R. Berger, Koszulity for nonquadratic algebras. J. Algebra 239(2), 705-734 (2001) · Zbl 1035.16023 · doi:10.1006/jabr.2000.8703
[11] R. Berger, N. Marconnet, Koszul and Gorenstein properties for homogeneous algebras. Algebr. Represent. Theory 9(1), 67-97 (2006) · Zbl 1125.16017 · doi:10.1007/s10468-005-9002-1
[12] G.M. Bergman, The diamond lemma for ring theory. Adv. Math. 29(2), 178-218 (1978) · Zbl 0326.16019 · doi:10.1016/0001-8708(78)90010-5
[13] L.A. Bokut, Imbeddings into simple associative algebras. Algebra Logika 15(2), 117-142, 245 (1976) · Zbl 0349.16007
[14] L.A. Bokut, Y. Chen, Gröbner-Shirshov bases and their calculation. Bull. Math. Sci. 4(3), 325-395 (2014) · Zbl 1350.13001 · doi:10.1007/s13373-014-0054-6
[15] R. Book, F. Otto, String-rewriting Systems, Texts and Monographs in Computer Science (Springer, 1993) · Zbl 0832.68061
[16] M. Bremner, V. Dotsenko, Algebraic Operads: An Algorithmic Companion (Taylor & Francis Group, 2016) · Zbl 1350.18001
[17] K.S. Brown, The geometry of rewriting systems: a proof of the Anick-Groves-Squier theorem, in Algorithms and Classification in Combinatorial Group Theory (Berkeley, CA, 1989), Math. Sci. Res. Inst. Publ., vol. 23 (Springer, New York, 1992), pp. 137-163 · Zbl 0764.20016
[18] B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal). Ph.D. thesis, Mathematical Institute, University of Innsbruck, Austria, 1965. English translation in J. Symb. Comput. Special Issue on Logic, Mathematics, and Computer Science: Interactions 41(3-4), 475-511 (2006) · Zbl 1245.13020
[19] B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems. Aequ. Math. 4, 374-383 (1970) · Zbl 0212.06401 · doi:10.1007/BF01844169
[20] B. Buchberger, History and basic features of the critical-pair/completion procedure. J. Symb. Comput. 3(1-2), 3-38 (1987). Rewriting techniques and applications (Dijon, 1985) · Zbl 0645.68094
[21] B. Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput. 41(3-4), 475-511 (2006). Translated from the 1965 German original by Michael P. Abramson · Zbl 1158.01307
[22] S. Burckel, Syntactical methods for braids of three strands. J. Symb. Comput. 31(5), 557-564 (2001) · Zbl 0990.20022 · doi:10.1006/jsco.2000.0473
[23] A. Burroni, Higher-dimensional word problems with applications to equational logic. Theor. Comput. Sci. 115(1), 43-62 (1993). 4th Summer Conference on Category Theory and Computer Science (Paris, 1991) · Zbl 0791.08004
[24] P.M. Cohn, Universal Algebra (Harper & Row Publishers, New York, London, 1965) · Zbl 0141.01002
[25] V. Dotsenko, S.R. Chowdhury, Anick resolution and Koszul algebras of finite global dimension. Commun. Algebra 45(12), 5380-5383 (2017) · Zbl 1388.16031 · doi:10.1080/00927872.2017.1307383
[26] V. Dotsenko, A. Khoroshkin, Free resolutions via Gröbner bases. ArXiv e-prints (2009) · Zbl 1278.18018
[27] V. Dotsenko, A. Khoroshkin, Gröbner bases for operads. Duke Math. J. 153(2), 363-396 (2010) · Zbl 1208.18007 · doi:10.1215/00127094-2010-026
[28] V. Dotsenko, A. Khoroshkin, Quillen homology for operads via gröbner bases. Documenta Math. 18, 707-747 (2013) · Zbl 1278.18018
[29] S. Gaussent, Y. Guiraud, P. Malbos, Coherent presentations of Artin monoids. Compos. Math. 151(5), 957-998 (2015) · Zbl 1398.20069 · doi:10.1112/S0010437X14007842
[30] H. Grauert, Über die Deformation isolierter Singularitäten analytischer Mengen. Invent. Math. 15, 171-198 (1972) · Zbl 0237.32011 · doi:10.1007/BF01404124
[31] E.L. Green, Noncommutative Gröbner bases, and projective resolutions, in Computational Methods for Representations of Groups and Algebras (Essen, 1997), Progr. Math., vol. 173 (Birkhäuser, Basel, 1999), pp. 29-60 · Zbl 0957.16033 · doi:10.1007/978-3-0348-8716-8_2
[32] J.R.J. Groves, Rewriting systems and homology of groups, in Groups—Canberra 1989, Lecture Notes in Math., vol. 1456 (Springer, Berlin, 1990), pp. 114-141 · Zbl 0732.20032
[33] Y. Guiraud, E. Hoffbeck, P. Malbos, Convergent presentations and polygraphic resolutions of associative algebras. Math. Z. 293(1-2), 113-179 (2019) · Zbl 1423.16008 · doi:10.1007/s00209-018-2185-z
[34] Y. Guiraud, P. Malbos, Coherence in monoidal track categories. Math. Struct. Comput. Sci. 22(6), 931-969 (2012) · Zbl 1264.18007 · doi:10.1017/S096012951100065X
[35] Y. Guiraud, P. Malbos, Higher-dimensional normalisation strategies for acyclicity. Adv. Math. 231(3-4), 2294-2351 (2012) · Zbl 1266.18008 · doi:10.1016/j.aim.2012.05.010
[36] Y. Guiraud, P. Malbos, Polygraphs of finite derivation type. Math. Struct. Comput. Sci. 28(2), 155-201 (2018) · Zbl 1396.18004 · doi:10.1017/S0960129516000220
[37] N. Hage, P. Malbos, Knuth’s coherent presentations of plactic monoids of type A. Algebr. Represent. Theory 20(5), 1259-1288 (2017) · Zbl 1422.20022 · doi:10.1007/s10468-017-9686-z
[38] H. Hironaka, Resolution of singularities of an algebraic variety over a field of characteristic zero. I, II. Ann. Math. 79(2), 109-203 (1964); Ann. Math. 79(2) (1964), 205-326 · Zbl 1420.14031 · doi:10.2307/1970547
[39] G. Huet, Confluent reductions: abstract properties and applications to term rewriting systems. J. Assoc. Comput. Mach. 27(4), 797-821 (1980) · Zbl 0458.68007 · doi:10.1145/322217.322230
[40] K. Iohara, P. Malbos, From analytical mechanical problems to rewriting theory through M. Janet, in Two Algebraic Byways from Differential Equations: Gröbner Bases and Quivers, Algorithms Comput. Math., vol. 28, eds. by K. Iohara et al. chapter 1 (Springer, Berlin, 2019, this volume)
[41] M. Janet, Sur les systèmes d’équations aux dérivées partielles. J. Math. Pures Appl. 8(3), 65-151 (1920) · JFM 47.0440.03
[42] M. Jöllenbeck, V. Welker, Minimal resolutions via algebraic discrete Morse theory. Mem. Amer. Math. Soc. 197(923), vi+74 (2009) · Zbl 1160.13007
[43] J.W. Klop, Term rewriting systems, in Handbook of Logic in Computer Science, vol. 2 (Oxford University Press, 1992), pp. 1-117, chapter 1
[44] D. Knuth, P. Bendix, Simple word problems in universal algebras, in Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) (Pergamon, Oxford, 1970), pp. 263-297 · Zbl 0188.04902
[45] Y. Kobayashi, Complete rewriting systems and homology of monoid algebras. J. Pure Appl. Algebra 65(3), 263-275 (1990) · Zbl 0711.20035 · doi:10.1016/0022-4049(90)90106-R
[46] Y. Kobayashi, Gröbner bases of associative algebras and the Hochschild cohomology. Trans. Amer. Math. Soc. 357(3), 1095-1124 (2005) (electronic) · Zbl 1069.16010
[47] M. Kreuzer, L. Robbiano, Computational Commutative Algebra. 1 (Springer-Verlag, Berlin, 2000) · Zbl 0956.13008
[48] P. Malbos, S. Mimram, Homological computations for term rewriting systems, in 1st International Conference on Formal Structures for Computation and Deduction, LIPIcs. Leibniz Int. Proc. Inform., vol. 52 (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016), p. 17, Art. No. 27 · Zbl 1387.68146
[49] B. Mitchell, Rings with several objects. Adv. Math. 8, 1-161 (1972) · Zbl 0232.18009 · doi:10.1016/0001-8708(72)90002-3
[50] T. Mora, An introduction to commutative and noncommutative Gröbner bases. Theor. Comput. Sci. 134(1), 131-173 (1994). Second International Colloquium on Words, Languages and Combinatorics (Kyoto, 1992) · Zbl 0824.68056
[51] H. Nakayama, N. Takayama, Introduction to algorithms for \(D\)-modules with quiver \(D\)-modules, in Two Algebraic Byways from Differential Equations: Gröbner Bases and Quivers, Algorithms Comput. Math., vol. 28, eds. by K. Iohara et al. (Springer, Berlin, this volume) · Zbl 1453.14057
[52] M. Newman, On theories with a combinatorial definition of “equivalence”. Ann. Math. (2) 43(2), 223-243 (1942) · Zbl 0060.12501 · doi:10.2307/1968867
[53] A. Polishchuk, L. Positselski, Quadratic Algebras, University Lecture Series, vol. 37 (American Mathematical Society, Providence, RI, 2005) · Zbl 1145.16009
[54] J.-F. Pommaret, Systems of Partial Differential Equations and Lie Pseudogroups, Mathematics and Its Applications, vol. 14 (Gordon & Breach Science Publishers, New York, 1978). With a preface by André Lichnerowicz · Zbl 0418.35028
[55] S.B. Priddy, Koszul resolutions. Trans. Amer. Math. Soc. 152, 39-60 (1970) · Zbl 0261.18016 · doi:10.1090/S0002-9947-1970-0265437-8
[56] M. Saito, B. Sturmfels, N. Takayama, Gröbner Deformations of Hypergeometric Differential Equations, Algorithms and Computation in Mathematics, vol. 6 (Springer, Berlin, 2000) · Zbl 0946.13021
[57] A.I. Shirshov, Some algorithmic problems for Lie algebras. Sib. Mat. Zh. 3, 292-296 (1962) · Zbl 0104.26004
[58] E. Sköldberg, Morse theory from an algebraic viewpoint. Trans. Amer. Math. Soc. 358(1), 115-129 (2006) · Zbl 1150.16008 · doi:10.1090/S0002-9947-05-04079-1
[59] C.C. Squier, F. Otto, Y. Kobayashi, A finiteness condition for rewriting systems. Theor. Comput. Sci. 131(2), 271-294 (1994) · Zbl 0863.68082 · doi:10.1016/0304-3975(94)90175-9
[60] R. Street, Limits indexed by category-valued \(2\)-functors. J. Pure Appl. Algebra 8(2), 149-181 (1976) · Zbl 0335.18005 · doi:10.1016/0022-4049(76)90013-X
[61] R. Street, The algebra of oriented simplexes. J. Pure Appl. Algebra 49(3), 283-335 (1987) · Zbl 0661.18005 · doi:10.1016/0022-4049(87)90137-X
[62] Terese, Term Rewriting Systems, Cambridge Tracts in Theoretical Computer Science, vol. 55 (Cambridge University Press, 2003) · Zbl 1030.68053
[63] J.M. Thomas, Differential Systems (American Mathematical Society (American Mathematical Society Colloquium Publications Vol. XXI), New York, 1937), IX + 118 p · JFM 63.0438.03
[64] A. Thue, Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln. Kristiania Vidensk. Selsk, Skr. 10, 493-524 (1914) · JFM 45.0333.19
[65] V. Ufnarovskij, Introduction to noncommutative Gröbner bases theory, in Gröbner Bases and Applications (Linz, 1998), London Math. Soc. Lecture Note Ser., vol. 251 (Cambridge Univ. Press, Cambridge, 1998), pp. 259-280 · Zbl 0902.16002 · doi:10.1017/CBO9780511565847.015
[66] V.
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.