|Abstract of Paper|
Iteration Theories of Boolean Functions
by Z. Esik
An iteration theory is an algebraic theory equipped with a dagger operation satisfying all equations that hold for the least (or greatest) fixed point operation on monotonic functions on complete lattices. We prove that all iteration theories of boolean functions equipped with a pointwise dagger operation consist of monotonic functions, and that the dagger operation is either the least, or the greatest fixed point operation. Thus, the iteration theory identities provide a characterization of the extremal fixed point operations on monotonic boolean functions. Our argument also proves that any Conway theory of boolean functions with a pointwise dagger is an iteration theory. Along the way of obtaining these results, we relate the parameter identity, an equation that holds in all Conway and iteration theories, to the pointwise property of the dagger operation, and to the extension of the dagger operation to the theory obtained by adjoining all constants. We also study conditions ensuring that the extension be conservative. It follows form the general result proved in the paper that if a Conway theory is equipped with a pointwise dagger, then the theory obtained by adjoining all constants is a Conway theory in a unique way, and that the same fact holds for iteration theories. We also exhibit an iteration theory of boolean functions with a non-pointwise dagger, an iteration theory of monotonic functions on the three-element lattice which has a pointwise dagger but such that the dagger operation is not one of the extremal fixed point operations, and a pointwise iteration theory on the three-element set such that there is no cpo structure which would make all functions of the theory monotonic.