| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Signature Rewriting in Gröbner Basis Computation
Abstract : We introduce the RB algorithm for Gro ̈bner basis compu- tation, a simpler yet equivalent algorithm to F5GEN. RB contains the original unmodified F5 algorithm as a special case, so it is possible to study and understand F5 by con- sidering the simpler RB. We present simple yet complete proofs of this fact and of F5's termination and correctness. RB is parametrized by a rewrite order and it contains many published algorithms as special cases, including SB. We prove that SB is the best possible instantiation of RB in the following sense. Let X be any instantiation of RB (such as F5). Then the S-pairs reduced by SB are always a subset of the S-pairs reduced by X and the basis computed by SB is always a subset of the basis computed by X.
Cited literature [11 references]
https://hal.inria.fr/hal-00930273
Contributor : Elias Tsigaridas <>
Submitted on : Tuesday, January 14, 2014 - 3:32:55 PM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Tuesday, April 15, 2014 - 4:25:53 PM
Contributor : Elias Tsigaridas <>
Submitted on : Tuesday, January 14, 2014 - 3:32:55 PM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Tuesday, April 15, 2014 - 4:25:53 PM
File
sbff.pdf
Files produced by the author(s)