Loop Variant - Rule of Inference For Total Correctness

Rule of Inference For Total Correctness

In order to formally state the rule of inference for the termination of a while loop we have demonstrated above, recall that in Floyd–Hoare logic, the rule for expressing the partial correctness of a while loop is:

where I is the invariant, C is the condition, and S is the body of the loop. To express total correctness, we write instead:

\frac{< \textrm{\ is\ well-founded},\;\;S\;} {\;\mathbf{while}\;C\; \mathbf{do}\; S \;},

where, in addition, V is the variant, and by convention the unbound symbol z is taken to be universally quantified.

Read more about this topic:  Loop Variant

Famous quotes containing the words rule of, rule, inference, total and/or correctness:

    “The first rule of education for me was discipline. Discipline is the keynote to learning. Discipline has been the great factor in my life. I discipline myself to do everything—getting up in the morning, walking, dancing, exercise. If you won’t have discipline, you won’t have a nation. We can’t have permissiveness. When someone comes in and says, “Oh, your room is so quiet,” I know I’ve been successful.”
    —Rose Hoffman, U.S. public school third-grade teacher. As quoted in Working, book 8, by Studs Terkel (1973)

    “To rule is not so much a question of the heavy hand as the firm seat.”
    —José Ortega Y Gasset (1883–1955)

    “Rules and particular inferences alike are justified by being brought into agreement with each other. A rule is amended if it yields an inference we are unwilling to accept; an inference is rejected if it violates a rule we are unwilling to amend. The process of justification is the delicate one of making mutual adjustments between rules and accepted inferences; and in the agreement achieved lies the only justification needed for either.”
    —Nelson Goodman (b. 1906)

    “I only know that a rook
    Ordering its black feathers can so shine
    As to seize me senses, haul
    My eyelids up, and grant

    A brief respite from fear
    Of total neutrality.”
    —Sylvia Plath (1932–1963)

    “With impressive proof on all sides of magnificent progress, no one can rightly deny the fundamental correctness of our economic system.”
    —Herbert Hoover (1874–1964)