Applying a generalization of a theorem of Mills to generalized looping structures

摘要

We present a generalization of a theorem of Mills, known as the while statement verification rule, that can be used to verify that a deterministic while loop computes a given function f. First, we study an abstract form of (nondeterministic) looping in the setting of relation algebras. We state a theorem showing how to verify that a given relation is the relation computed by the abstract loop. Then, we specialize this theorem to three forms of generalized looping structures that have been proposed in the literature, namely Dijsktra's do od, Anson's do upon and Parnas' it ti. We take a demonic viewpoint; that is, we assume the worse possible execution of the nondeterministic programs under consideration.