Termination of Original F5

Details Termination of Original F5 Termination of Original F5

2012-03-12

arxiv.org/abs/1203.2402v1

Mathematics

Commutative Algebra

Scientific paper

The original F5 algorithm described in Faug\'ere's paper is formulated for any homogeneous polynomial set input. The correctness of output is shown for any input that terminates the algorithm, but the termination itself is proved only for the case of input being regular polynomial sequence. This article shows that algorithm correctly terminates for any homogeneous input without any reference to regularity. The scheme contains two steps: first it is shown that if the algorithm does not terminate it eventually generates two polynomials where first is a reductor for the second. But first step doesn't show that this reduction is permitted by criteria introduced in F5. The second step shows that if such pair exists then there exists another pair for which the reduction is permitted by all criteria. Existence of such pair leads to contradiction

Affiliated with

Also associated with

No associations

Rating

Termination of Original F5 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Termination of Original F5, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Termination of Original F5 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-487654