Automated Theorem Proving

Getting a Better Insight into Structural TestingGetting a Better Insight into Structural Testing

We, authors of this article, have some experience in executing the program that proves the theorem, using the computerized theorem proving tools such as Gypsy to test approximately a thousand lines of code. The principle of the Gypsy utility is as follows. First, the tester puts the statements of theorems and lemmas together with blocks of code written in Gypsy (one of the variants of Pascal). Then the proof of theorems embedded in Gypsy verifies whether the block of code correctly executes all the statements formulated in the theorems and lemmas. The algorithm, the correctness of which was checked and proven with the help of this formal verification tool, is known as Collision Avoidance (collisions exception). Currently, this algorithm is implemented in the computer systems of the US Federal Aviation Agency to coordinate an aircraft how to avoid threatening collisions. To achieve this goal, radio beacons are installed on aircraft, as well as on high buildings and mountains. These beacon beacons transmit digital packets containing data on such dynamic flight characteristics as altitude, speed and direction of flight. Based on mathematical models of flight dynamics, simulation modeling is performed for data from received digital packages, the purpose of which is to determine the probability of a collision, as well as to develop the necessary tactics to prevent collisions. These data are automatically and preliminarily transmitted to the aircraft with intersecting flight trajectories and help to prevent collision. Thus, it is obvious that the code of the collision avoidance algorithm must be correct, and provably correct.


It is always reasonable to use professional services automation software which helps to manage development projects, people, funds with one view of the client.


Initially, the collision avoidance program was translated into the Gypsy language, and theorems were formulated for each block of code. Then, using the Gypsy capabilities to prove the theorems, it was established that all theorems in the code are implemented. During the process, one software error was detected, after which corresponding corrections were made to the source code. The process was painless and really effective.


Test automation tools


There are many automated static testing tools. Most of them are specialized tools, and not one universal tool that could be used in all cases. Another distinguishing feature of these static testing tools is that they are language dependent. Detection of errors in the source language or in the documentation language involves the allocation of errors, including spelling, syntactic errors, errors associated with undefined variables and pointers, unclosed program constructs, undefined references, including Internet addresses, etc.

Be the first to comment on "Automated Theorem Proving"

Leave a comment

Your email address will not be published.