Reduction operators and completion of rewriting systems

DOI10.1016/J.JSC.2017.03.002zbMATH Open1371.68136arXiv1605.00174OpenAlexW2962851192MaRDI QIDQ2399863FDOQ2399863

Cyrille Chenavier

Publication date: 24 August 2017

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We propose a functional description of rewriting systems where reduction rules are represented by linear maps called reduction operators. We show that reduction operators admit a lattice structure. Using this structure we define the notion of confluence and we show that this notion is equivalent to the Church-Rosser property of reduction operators. In this paper we give an algebraic formulation of completion using the lattice structure. We relate reduction operators and Gr"obner bases. Finally, we introduce generalised reduction operators relative to non total ordered sets.

Full work available at URL: https://arxiv.org/abs/1605.00174

zbMATH Keywords

completionreduction operators[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=noncommutative+Gr%EF%BF%BD%EF%BF%BDbner+bases&go=Go noncommutative Gr��bner bases]

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• An introduction to commutative and noncommutative Gröbner bases
• The diamond lemma for ring theory
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Title not available (Why is that?)
• Title not available (Why is that?)
• On theories with a combinatorial definition of 'equivalence'
• Term Rewriting and All That
• Title not available (Why is that?)
• Title not available (Why is that?)
• Confluence and Koszulity
• Representations of non-commutative quantum groups
• Confluence algebras and acyclicity of the Koszul complex
• Koszul Resolutions
• Koszulity for nonquadratic algebras.
• Selected works of A. I. Shirshov. Translated by Murray Bremner and Mikhail V. Kotchetov. Edited by Leonid A. Bokut, Victor Latyshev, Ivan Shestakov and Efim Zelmanov
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Title not available (Why is that?)
• History and basic features of the critical-pair/completion procedure
• Weakly confluent quadratic algebras

Cited In (11)

• A lattice formulation of the noncommutative F4 procedure
• Term Rewriting and Applications
• Processes, Terms and Cycles: Steps on the Road to Infinity
• Elimination transformations for associative-commutative rewriting systems
• Abstract reduction systems and idea of Knuth-Bendix completion algorithm
• Syzygies among reduction operators
• Complete involutive rewriting systems
• Processes, Terms and Cycles: Steps on the Road to Infinity
• Reduction and introducers in \(d\)-contexts
• Topological rewriting systems applied to standard bases and syntactic algebras
• Title not available (Why is that?)

Uses Software

• BERGMAN

This page was built for publication: Reduction operators and completion of rewriting systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399863)