Least and greatest fixed points of a while semantics function
Fairouz Tchier, Relation Algebras · 2009
The meaning of a program is given by specifying the function (from input to output) that corresponds to the program. The denotational semantic definition, thus maps syntactical things into functions. A relational semantics is a mapping of programs to relations. We consider that the input-output semantics of a program is given by a relation on its set of states. In a nondeterministic context, this relation is calculated by considering the worst behavior of the program (demonic relational semantics). In this paper, we concentrate on while loops. We will present some interesting results about the fixed points of the while semantics function; f(X) = Q _ P 2 X where P < ^ Q < = O, by taking P := t 2 B and Q := t , one gets the demonic semantics we have assigned to while loops in previous papers. We will show that the least angelic fixed point is equal to the greatest demonic fixed point of the semantics function.