A new proof for the correctness of the F5 algorithm

CSpace

	A new proof for the correctness of the F5 algorithm
其他题名	A new proof for the correctness of the F5 algorithm
	Sun Yao; Wang DingKang
	2013
发表期刊	中国科学:数学(英文版)
ISSN	1674-7283
卷号	56 期号:4 页码:745-756
摘要	In 2002, FaugSre presented the famous F5 algorithm for computing Grobner basis where two criteria, syzygy criterion and rewritten criterion, were proposed to avoid redundant computations. He proved the correctness of the syzygy criterion, but the proof for the correctness of the rewritten criterion was left. Since then, F5 has been studied extensively. Some proofs for the correctness of F5 were proposed, but these proofs are valid only under some extra assumptions. In this paper, we give a proof for the correctness of F5B, an equivalent version of F5 in Buchberger's style. The proof is valid for both homogeneous and non-homogeneous polynomial systems. Since this proof does not depend on the computing order of the S-pairs, any strategy of selecting S-pairs could be used in F5B or F5. Furthermore, we propose a natural and non-incremental variant of F5 where two revised criteria can be used to remove almost all redundant S-pairs.
其他摘要	In 2002,Faugère presented the famous F5 algorithm for computing Grbner basis where two criteria,syzygy criterion and rewritten criterion,were proposed to avoid redundant computations.He proved the correctness of the syzygy criterion,but the proof for the correctness of the rewritten criterion was left.Since then,F5 has been studied extensively.Some proofs for the correctness of F5 were proposed,but these proofs are valid only under some extra assumptions.In this paper,we give a proof for the correctness of F5B,an equivalent version of F5 in Buchberger’s style.The proof is valid for both homogeneous and non-homogeneous polynomial systems.Since this proof does not depend on the computing order of the S-pairs,any strategy of selecting S-pairs could be used in F5B or F5.Furthermore,we propose a natural and non-incremental variant of F5 where two revised criteria can be used to remove almost all redundant S-pairs.
关键词	GROBNER BASES Grobner basis F5 F5B correctness of F5
收录类别	CSCD
语种	中文
资助项目	[National Key Basic Research Project of China] ; [National Natural Science Foundation of China]
CSCD记录号	CSCD:4814855
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/53496
专题	中国科学院数学与系统科学研究院
作者单位	中国科学院数学与系统科学研究院
推荐引用方式 GB/T 7714	Sun Yao,Wang DingKang. A new proof for the correctness of the F5 algorithm[J]. 中国科学:数学(英文版),2013,56(4):745-756.
APA	Sun Yao,&Wang DingKang.(2013).A new proof for the correctness of the F5 algorithm.中国科学:数学(英文版),56(4),745-756.
MLA	Sun Yao,et al."A new proof for the correctness of the F5 algorithm".中国科学:数学(英文版) 56.4(2013):745-756.