Complete proof rules for strong fairness and strong extreme fairness

AbstractThis paper demonstrates completeness of a termination-rule for iterative programs with strongly fair nondeterminism, even when there are countably infinite options for the nondeterminism. This means that whenever a program is guaranteed to terminate under the assumption of strong fairness, then this termination can be proved via the strongly fair termination rule. A variant of the rule is also shown to be complete for extremely fair nondeterminism, as introduced by Pnueli (1983) and developed by Francez (1986)