In the formal derivation and proof of binary tree algorithms,Dijkstra’s weakest predicate method is commonly used.However,the method has some drawbacks,including a time-consuming derivation process,complicated loop i...In the formal derivation and proof of binary tree algorithms,Dijkstra’s weakest predicate method is commonly used.However,the method has some drawbacks,including a time-consuming derivation process,complicated loop invariants,and the inability to generate executable programs from the specification.This paper proposes a unified strategy for the formal derivation and proof of binary tree non-recursive algorithms to address these issues.First,binary tree problem solving sequences are decomposed into two types of recursive relations based on queue and stack,and two corresponding loop invariant templates are constructed.Second,high-reliability Apla(abstract programming language)programs are derived using recursive relations and loop invariants.Finally,Apla programs are converted automatically into C++executable programs.Two types of problems with binary tree queue and stack recursive relations are used as examples,and their formal derivation and proof are performed to validate the proposed strategy’s effectiveness.This strategy improves the efficiency and correctness of binary tree algorithm derivation.展开更多
基金Supported by the National Natural Science Foundation of China(61862033,61902162)Key Project of Science and Technology Research of Department of Education of Jiangxi Province(GJJ210307)。
文摘In the formal derivation and proof of binary tree algorithms,Dijkstra’s weakest predicate method is commonly used.However,the method has some drawbacks,including a time-consuming derivation process,complicated loop invariants,and the inability to generate executable programs from the specification.This paper proposes a unified strategy for the formal derivation and proof of binary tree non-recursive algorithms to address these issues.First,binary tree problem solving sequences are decomposed into two types of recursive relations based on queue and stack,and two corresponding loop invariant templates are constructed.Second,high-reliability Apla(abstract programming language)programs are derived using recursive relations and loop invariants.Finally,Apla programs are converted automatically into C++executable programs.Two types of problems with binary tree queue and stack recursive relations are used as examples,and their formal derivation and proof are performed to validate the proposed strategy’s effectiveness.This strategy improves the efficiency and correctness of binary tree algorithm derivation.
