ADAS AND THE EQUATIONAL THEORY OF IF-THEN-ELSE

Programming languages admit the ternary operator if p then f else g where p is a test which may not halt. Here, p ranges over a suitable 3-valued logic. Guzman and Squier recently introduced ''C-algebras'' and an equational 3-valued generalization of Boolean algebra based on ''or'', ''and'' and ''not''. We incorporate their results and introduce as well the concept of ''ada'' (for Algebra of Disjoint Alternatives) which results when C-algebras are equipped with an oracle for the halting problem. The 3-element ada is functionally complete. For if-then-else over a Boolean algebra or over an ada, eight equations generate all. The resulting variety may be represented as a variety of modules over a Boolean algebra. Over a C-algebra, a ninth equation is required.