×

Normalized rewriting: A unified view of Knuth-Bendix completion and Gröbner bases computation. (English) Zbl 0915.68100

Bronstein, Manuel (ed.) et al., Symbolic rewriting techniques. Papers from the workshop held in Ascona, Switzerland, April 30 - May 4, 1995. Basel: Birkhäuser Verlag. Prog. Comput. Sci. Appl. Log. 15, 193-208 (1998).
Summary: Buchberger’s algorithm and Knuth-Bendix completion are two fundamental algorithms used respectively in computer algebra and in equational logic. It has been remarked since 1981 that these two algorithms behave in the same way. We show that this similarity is made explicit by viewing them as two particular instances of a very general completion algorithm: normalized completion.
For the entire collection see [Zbl 0897.00036].

MSC:

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