{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T18:16:38Z","timestamp":1758478598447,"version":"3.40.5"},"reference-count":49,"publisher":"Cambridge University Press (CUP)","issue":"7","license":[{"start":{"date-parts":[[2021,12,10]],"date-time":"2021-12-10T00:00:00Z","timestamp":1639094400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Convergent rewriting systems on algebraic structures give methods to solve decision problems, to prove coherence results, and to compute homological invariants. These methods are based on higher-dimensional extensions of the critical branching lemma that proves local confluence from confluence of the critical branchings. The analysis of local confluence of rewriting systems on algebraic structures, such as groups or linear algebras, is complicated because of the underlying algebraic axioms. This article introduces the structure of algebraic polygraph modulo that formalizes the interaction between the rules of an algebraic rewriting system and the inherent algebraic axioms, and we show a critical branching lemma for algebraic polygraphs. We deduce a critical branching lemma for rewriting systems on algebraic models whose axioms are specified by convergent modulo rewriting systems. We illustrate our constructions for string, linear, and group rewriting systems.<\/jats:p>","DOI":"10.1017\/s0960129521000426","type":"journal-article","created":{"date-parts":[[2021,12,10]],"date-time":"2021-12-10T06:45:06Z","timestamp":1639118706000},"page":"870-897","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Confluence of algebraic rewriting systems"],"prefix":"10.1017","volume":"32","author":[{"given":"Cyrille","family":"Chenavier","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7477-9112","authenticated-orcid":false,"given":"Benjamin","family":"Dupont","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4449-0091","authenticated-orcid":false,"given":"Philippe","family":"Malbos","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2021,12,10]]},"reference":[{"key":"S0960129521000426_ref15","doi-asserted-by":"publisher","DOI":"10.1112\/S0010437X14007842"},{"key":"S0960129521000426_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129516000220"},{"key":"S0960129521000426_ref45","first-page":"292","article-title":"Some algorithmic problems for Lie algebras","volume":"3","author":"Shirshov","year":"1962","journal-title":"Sib. Mat. Zh."},{"key":"S0960129521000426_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S096012951100065X"},{"key":"S0960129521000426_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7643-9911-5_3"},{"key":"S0960129521000426_ref39","unstructured":"March\u00e9, C. (1993). R\u00e9\u00e9criture modulo une th\u00e9orie pr\u00e9sent\u00e9e par un syst\u00e8me convergent et d\u00e9cidabilit\u00e9 des probl\u00e8mes du mot dans certaines classes de th\u00e9ories equationnelles. PhD thesis. 1993PA112312."},{"key":"S0960129521000426_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90003-0"},{"key":"S0960129521000426_ref38","doi-asserted-by":"crossref","unstructured":"Malbos, P. and Ren, I. (2021). Completion in operads via essential syzygies. In: Proceedings of the 46th International Symposium on Symbolic and Algebraic Computation, ISSAC \u201921. Association for Computing Machinery.","DOI":"10.1145\/3452143.3465552"},{"key":"S0960129521000426_ref24","doi-asserted-by":"crossref","unstructured":"Iohara, K. and Malbos, P. (2020). Maurice Janet\u2019s algorithms on systems of linear partial differential equations. Archive for History of Exact Sciences. Springer, to appear.","DOI":"10.1007\/s00407-020-00255-y"},{"key":"S0960129521000426_ref11","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0020"},{"key":"S0960129521000426_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(87)80020-2"},{"key":"S0960129521000426_ref6","doi-asserted-by":"publisher","DOI":"10.1515\/GCC.2009.131"},{"key":"S0960129521000426_ref10","unstructured":"Curien, P.-L. and Mimram, S. (2017). Coherent presentations of monoidal categories. Logical Methods in Computer Science 13 (3): Paper No. 31, 38."},{"key":"S0960129521000426_ref42","unstructured":"Nivat, M. (1973). Congruences parfaites et quasi-parfaites. In: S\u00e9minaire P. Dubreil, 25e ann\u00e9e (1971\/72), Alg\u00e8bre, Fasc. 1, Exp. No. 7, p. 9. Secr\u00e9tariat Math\u00e9matique, 1973."},{"key":"S0960129521000426_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(90)90106-R"},{"key":"S0960129521000426_ref44","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"S0960129521000426_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(86)80004-9"},{"key":"S0960129521000426_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511542770.026"},{"key":"S0960129521000426_ref27","unstructured":"Jouannaud, J.-P. and Li, J. (2012). Church-Rosser properties of normal rewriting. In: Computer Science Logic 2012, vol. 16. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., 350\u2013365."},{"key":"S0960129521000426_ref4","doi-asserted-by":"crossref","unstructured":"Buchberger, B. (1965). 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). PhD thesis, Mathematical Institute, University of Innsbruck, Austria. English translation in Journal of Symbolic Computation, Special Issue on Logic, Mathematics, and Computer Science: Interactions 41 (3\u20134) 475\u2013511 (2006).","DOI":"10.1016\/j.jsc.2005.09.007"},{"key":"S0960129521000426_ref8","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1996.0046"},{"key":"S0960129521000426_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(94)00043-I"},{"key":"S0960129521000426_ref29","doi-asserted-by":"crossref","unstructured":"Knuth, D. and Bendix, P. (1970). Simple word problems in universal algebras. In: Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967). Pergamon, 263\u2013297.","DOI":"10.1016\/B978-0-08-012975-4.50028-X"},{"key":"S0960129521000426_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(78)90010-5"},{"key":"S0960129521000426_ref41","unstructured":"Mimram, S. (2010). Computing critical pairs in 2-dimensional rewriting systems. In: RTA 2010: Proceedings of the 21st International Conference on Rewriting Techniques and Applications, vol. 6. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., 227\u2013241."},{"key":"S0960129521000426_ref43","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322251"},{"key":"S0960129521000426_ref47","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90175-9"},{"key":"S0960129521000426_ref25","first-page":"65","article-title":"Sur les syst\u00e8mes d\u2019\u00e9quations aux d\u00e9riv\u00e9es partielles","volume":"8","author":"Janet","year":"1920","journal-title":"Journal de math\u00e9matiques pures et appliqu\u00e9es"},{"key":"S0960129521000426_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0047119"},{"key":"S0960129521000426_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.05.010"},{"key":"S0960129521000426_ref35","unstructured":"Malbos, P. and Mimram, S. (2016). Homological computations for term rewriting systems. In: 1st International Conference on Formal Structures for Computation and Deduction, vol. 52. LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 27, 17. Schloss Dagstuhl. Leibniz-Zent. Inform."},{"key":"S0960129521000426_ref48","unstructured":"Terese. (2003). Term Rewriting Systems, vol. 55. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press."},{"key":"S0960129521000426_ref49","unstructured":"Viry, P. (1995). Rewriting modulo a rewrite system. Technical report."},{"key":"S0960129521000426_ref32","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.50.5.869"},{"key":"S0960129521000426_ref1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1986-0846601-5"},{"key":"S0960129521000426_ref28","doi-asserted-by":"crossref","unstructured":"Jouannaud, J.-P. and Mu\u00f1oz, M. (1984). Termination of a set of rules modulo a set of equations. In: 7th International Conference on Automated Deduction (Napa, Calif., 1984), vol. 170. Lecture Notes in Computer Science. Springer, 175\u2013193.","DOI":"10.1007\/978-0-387-34768-4_11"},{"key":"S0960129521000426_ref13","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-2010-026"},{"key":"S0960129521000426_ref9","unstructured":"Curien, P.-L. , Duric, A. and Guiraud, Y. (2021). Coherent presentations of a class of monoids admitting a garside family. arXiv 2107.00498."},{"key":"S0960129521000426_ref14","unstructured":"Dupont, B. and Malbos, P. (2018). Coherent confluence modulo relations and double groupoids. preprint arXiv:1810.08184, Hal-01898868."},{"key":"S0960129521000426_ref17","unstructured":"Guiraud, Y. and Malbos, P. (2009). Higher-dimensional categories with finite derivation type. Theory and Applications of Categories 22 (18) 420\u2013478."},{"key":"S0960129521000426_ref37","unstructured":"Malbos, P. and Ren, I. (2020). Shuffle polygraphic resolutions for operads. submitted preprint, arXiv:2012.15718."},{"key":"S0960129521000426_ref40","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1996.0011"},{"key":"S0960129521000426_ref36","unstructured":"Malbos, P. and Mimram, S. (2021). Cartesian polygraphic resolutions. en pr\u00e9paration."},{"key":"S0960129521000426_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-010-9288-0"},{"key":"S0960129521000426_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00209-018-2185-z"},{"key":"S0960129521000426_ref23","doi-asserted-by":"publisher","DOI":"10.21236\/ADA087641"},{"key":"S0960129521000426_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/800017.800519"},{"key":"S0960129521000426_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322230"},{"key":"S0960129521000426_ref46","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(87)90129-0"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129521000426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,22]],"date-time":"2023-02-22T08:15:51Z","timestamp":1677053751000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129521000426\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,10]]},"references-count":49,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["S0960129521000426"],"URL":"https:\/\/doi.org\/10.1017\/s0960129521000426","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2021,12,10]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}