Rewriting as a Special Case of Noncommutative Groebner Basis Theory

1999/01/11 by Anne Heyworth, Heyworth, Anne
Computer Science · Mathematics · #68Q40 (Secondary) #68Q42 (Primary) 16S15 #Combinatorics (math.CO) #FOS: Mathematics #Formal Methods in Verification #Polynomial and algebraic computation #math.CO #msc:16S15 #msc:68Q40 #msc:68Q42 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/9901044

article, 4 pages, LaTeX2e

arxiv created 1999/01/11 · openalex publication_date 1999/01/11 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Rewriting for semigroups is a special case of Groebner basis theory for noncommutative polynomial algebras. The fact is a kind of folklore but is not fully recognised. The aim of this paper is to elucidate this relationship, showing that the noncommutative Buchberger algorithm corresponds step-by-step to the Knuth-Bendix completion procedure.

Related

• One-sided Noncommutative Groebner Bases with Applications to Green's Relations
• Noncommutative Involutive Bases
• On Groebner Basis in Monoid and Group Rings
• Applications of Rewriting Systems and Groebner Bases to Computing Kan Extensions and Identities Among Relations
• Extended letterplace correspondence for nongraded noncommutative ideals and related algorithms