Reduction operators and completion of rewriting systems

DOI10.1016/J.JSC.2017.03.002MaRDI QIDQ2399863zbMATH OpenOpenAlexFDO

Authors Cyrille Chenavier

Publication date 24 August 2017

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

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

zbMATH Keywords

completionreduction operatorsnoncommutative 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)

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.

Recommendations

• Systems of reductions
• Structures for abstract rewriting
• Completion of a Set of Rules Modulo a Set of Equations
• scientific article; zbMATH DE number 752977
• Ordered rewriting and confluence

Cites work

• scientific article; zbMATH DE number 992297 (Why is no real title available?)
• scientific article; zbMATH DE number 3544216 (Why is no real title available?)
• scientific article; zbMATH DE number 2019939 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• scientific article; zbMATH DE number 2242607 (Why is no real title available?)
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• An introduction to commutative and noncommutative Gröbner bases
• Confluence algebras and acyclicity of the Koszul complex
• Confluence and Koszulity
• History and basic features of the critical-pair/completion procedure
• Koszul Resolutions
• Koszulity for nonquadratic algebras.
• On theories with a combinatorial definition of 'equivalence'
• Representations of non-commutative quantum groups
• 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
• Term Rewriting and All That
• The diamond lemma for ring theory
• Weakly confluent quadratic algebras

Cited in

(13)

• Reduction relations for monoid semirings
• scientific article; zbMATH DE number 1419256 (Why is no real title available?)
• Term Rewriting and Applications
• Processes, Terms and Cycles: Steps on the Road to Infinity
• Elimination transformations for associative-commutative rewriting systems
• Structures for abstract rewriting
• Abstract reduction systems and idea of Knuth-Bendix completion algorithm
• Syzygies among reduction operators
• Complete involutive rewriting systems
• A lattice formulation of the noncommutative \(F_4\) procedure
• 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

Describes a project that uses

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)