We present a symbolic-numeric hybrid method, based on sum-of-squares （SOS） relaxation and rational vec- tor recovery, to compute inequality invariants and ranking functions for proving total correctness and generati...We present a symbolic-numeric hybrid method, based on sum-of-squares （SOS） relaxation and rational vec- tor recovery, to compute inequality invariants and ranking functions for proving total correctness and generating pre- conditions for programs. The SOS relaxation method is used to compute approximate invariants and approximate rank- ing functions with floating point coefficients. Then Gauss- Newton refinement and rational vector recovery are applied to approximate polynomials to obtain candidate polynomials with rational coefficients, which exactly satisfy the conditions of invariants and ranking functions. In the end, several exam- ples are given to show the effectiveness of our method.展开更多
文摘We present a symbolic-numeric hybrid method, based on sum-of-squares （SOS） relaxation and rational vec- tor recovery, to compute inequality invariants and ranking functions for proving total correctness and generating pre- conditions for programs. The SOS relaxation method is used to compute approximate invariants and approximate rank- ing functions with floating point coefficients. Then Gauss- Newton refinement and rational vector recovery are applied to approximate polynomials to obtain candidate polynomials with rational coefficients, which exactly satisfy the conditions of invariants and ranking functions. In the end, several exam- ples are given to show the effectiveness of our method.
