The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of f...The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for. It is shown that the existence of k-independent sets in G is equivalent to the existence of solutions of a system of multivariate polynomial equations. It follows that the problem of finding k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved. Consequently, the maximal independent sets and the independent number of G are obtained after solving at most n such equations. Finally, the numerical example is presented to illustrate the effectiveness of this algebraic computational method.展开更多
乘法器电路验证是算术电路验证领域内的一个重大难题。Gröbner基方法是其中目前最为有效的验证方法之一。基于此方法开发的Amulet程序通过减少中间变量数量提高了验证效率,但是对于大型乘法器,验证速度慢的问题仍存在。本文对Amule...乘法器电路验证是算术电路验证领域内的一个重大难题。Gröbner基方法是其中目前最为有效的验证方法之一。基于此方法开发的Amulet程序通过减少中间变量数量提高了验证效率,但是对于大型乘法器,验证速度慢的问题仍存在。本文对Amulet的关键算法进行了进一步优化,通过指针操作对函数进行重写,缩短了验证的时间,并根据实验数据体现了其在大型乘法器验证中的应用优势,为形式化验证技术的未来研究提供了参考。The verification of multiplier circuits is a significant challenge in the field of arithmetic circuit verification. The Gröbner basis method is currently one of the most effective verification methods available. The Amulet program, developed based on this method, improves verification efficiency by reducing the number of intermediate variables. However, for large multipliers, the verification speed remains an issue. This paper further optimizes the key algorithms of Amulet, by rewriting functions through pointer operations, reduces verification time. Experimental results demonstrate its advantages in the verification of large multipliers. It provides a reference for future research in formal verification techniques.展开更多
Improved algorithm for Grbner basis is a new way to solve Grbner basis by adopting the locally analytic method,which is based on GrbnerNew algorithm The process consists of relegating the leading terms of generator of...Improved algorithm for Grbner basis is a new way to solve Grbner basis by adopting the locally analytic method,which is based on GrbnerNew algorithm The process consists of relegating the leading terms of generator of the polynomial in the idea according to correlated expressions of leading terms and then analyzing every category.If a polynomial can be reduced to a remainder polynomial by a polynomial in the idea,then it can be replaced by the remainder polynomial as generator In the solving process,local reduction and local puwer decrease are employed to prevent the number of middle terms from increasing too fast and the degrees of polynomial from being too high so as to reduce the amount of展开更多
The full-length sequence of the odorant binding protein 5 gene,HarmOBP5,was obtained from an antennae cDNA library of cotton bollworm,Helicoverpa armigera （Hübner）.The cDNA contains a 444 bp open reading frame,...The full-length sequence of the odorant binding protein 5 gene,HarmOBP5,was obtained from an antennae cDNA library of cotton bollworm,Helicoverpa armigera （Hübner）.The cDNA contains a 444 bp open reading frame,encoding a protein with 147 amino acids,namely HarmOBP5.HarmOBP5 was expressed in Escherichia coli and the recombinant protein was purified by affinity chromatography.SDS-PAGE and Western blot analysis demonstrated that the purified protein can be used for further investigation of its binding characteristics.Competitive binding assays with 113 odorant chemicals indicated that HarmOBP5 has strong affinity to some special plant volatiles,including （E）-β-farnesene,ethyl butyrate,ethyl heptanoate,and acetic acid 2-methylbutyl ester.Based on three-dimensional （3D） model of AaegOBP1 from Aedes aegypti,a 3D model of HarmOBP5 was predicted.The model revealed that some key binding residues in HarmOBP5 may play important roles in odorant perception of H.armigera.This study provides clues for better understanding physiological functions of OBPs in H.armigera and other insects.展开更多
采用Grbner基方法,可以把一个在有限群作用下不变的多项式写成不变环的生成元的多项式.核心问题是如何有效地计算这个正维不变理想的Grbner基.本文引入一个有效提升算法来计算这组Grbner基.当用straight line program模型对整个...采用Grbner基方法,可以把一个在有限群作用下不变的多项式写成不变环的生成元的多项式.核心问题是如何有效地计算这个正维不变理想的Grbner基.本文引入一个有效提升算法来计算这组Grbner基.当用straight line program模型对整个计算过程进行复杂度分析时,可以把计算开销控制在多项式时间内.展开更多
文摘The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for. It is shown that the existence of k-independent sets in G is equivalent to the existence of solutions of a system of multivariate polynomial equations. It follows that the problem of finding k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved. Consequently, the maximal independent sets and the independent number of G are obtained after solving at most n such equations. Finally, the numerical example is presented to illustrate the effectiveness of this algebraic computational method.
文摘乘法器电路验证是算术电路验证领域内的一个重大难题。Gröbner基方法是其中目前最为有效的验证方法之一。基于此方法开发的Amulet程序通过减少中间变量数量提高了验证效率,但是对于大型乘法器,验证速度慢的问题仍存在。本文对Amulet的关键算法进行了进一步优化,通过指针操作对函数进行重写,缩短了验证的时间,并根据实验数据体现了其在大型乘法器验证中的应用优势,为形式化验证技术的未来研究提供了参考。The verification of multiplier circuits is a significant challenge in the field of arithmetic circuit verification. The Gröbner basis method is currently one of the most effective verification methods available. The Amulet program, developed based on this method, improves verification efficiency by reducing the number of intermediate variables. However, for large multipliers, the verification speed remains an issue. This paper further optimizes the key algorithms of Amulet, by rewriting functions through pointer operations, reduces verification time. Experimental results demonstrate its advantages in the verification of large multipliers. It provides a reference for future research in formal verification techniques.
文摘Improved algorithm for Grbner basis is a new way to solve Grbner basis by adopting the locally analytic method,which is based on GrbnerNew algorithm The process consists of relegating the leading terms of generator of the polynomial in the idea according to correlated expressions of leading terms and then analyzing every category.If a polynomial can be reduced to a remainder polynomial by a polynomial in the idea,then it can be replaced by the remainder polynomial as generator In the solving process,local reduction and local puwer decrease are employed to prevent the number of middle terms from increasing too fast and the degrees of polynomial from being too high so as to reduce the amount of
基金supported by the National Basic Research Program of China(2012CB114104)the National Natural Science Foundation of China(30871640,31071694)+1 种基金the National High-Tech R&D Program of China(2008AA02Z307)the International Cooperation and Exchange Foundation of NSFC-RS of China(31111130203).
文摘The full-length sequence of the odorant binding protein 5 gene,HarmOBP5,was obtained from an antennae cDNA library of cotton bollworm,Helicoverpa armigera （Hübner）.The cDNA contains a 444 bp open reading frame,encoding a protein with 147 amino acids,namely HarmOBP5.HarmOBP5 was expressed in Escherichia coli and the recombinant protein was purified by affinity chromatography.SDS-PAGE and Western blot analysis demonstrated that the purified protein can be used for further investigation of its binding characteristics.Competitive binding assays with 113 odorant chemicals indicated that HarmOBP5 has strong affinity to some special plant volatiles,including （E）-β-farnesene,ethyl butyrate,ethyl heptanoate,and acetic acid 2-methylbutyl ester.Based on three-dimensional （3D） model of AaegOBP1 from Aedes aegypti,a 3D model of HarmOBP5 was predicted.The model revealed that some key binding residues in HarmOBP5 may play important roles in odorant perception of H.armigera.This study provides clues for better understanding physiological functions of OBPs in H.armigera and other insects.
文摘采用Grbner基方法,可以把一个在有限群作用下不变的多项式写成不变环的生成元的多项式.核心问题是如何有效地计算这个正维不变理想的Grbner基.本文引入一个有效提升算法来计算这组Grbner基.当用straight line program模型对整个计算过程进行复杂度分析时,可以把计算开销控制在多项式时间内.
