# Kleene Algebra (was: Mathematics of if-else statements)

## whopkins@csd.uwm.edu (Alfred Einstead)11 Sep 2001 23:13:49 -0400

From comp.compilers

Related articles
Mathematics of if-else statements bora@nope.com (Bora Eryilmaz) (2001-09-05)
Kleene Algebra (was: Mathematics of if-else statements) whopkins@csd.uwm.edu (2001-09-11)
| List of all articles for this month |

 From: whopkins@csd.uwm.edu (Alfred Einstead) Newsgroups: comp.compilers Date: 11 Sep 2001 23:13:49 -0400 Organization: http://groups.google.com/ References: 01-09-020 Keywords: optimize Posted-Date: 11 Sep 2001 23:13:49 EDT

"Bora Eryilmaz" <bora@nope.com> wrote in message news:01-09-020...
> Are there any mathematical/logical approaches to analyze nested
> if-else statements in order to simplify or optimize them, or to
> understand the flow of successive tests.

Control flow structures are Kleene algebraic. Dexter Kozen has
numerous papers on Kleene algebra (including, particularly, Kleene
algebra with tests) at www.cs.cornell.edu/kozen

> For example, if I have
> if (a > 10) {
> if (a < 20) {
> statement1;
> } else {
> statement2;
> }
> } else {
> statement3;
> }

Defining the operator (A?B:C) as (A B) + (!A C), you'd probably write
this as

(a>10)? ((a<20)? S1: S2): S3

The statements (a>10), (a<20) reside in a boolean subalgebra of
the Kleene algebra. Substituting a value in for a and reducing
the statements (a>10), (a<20) to 1 or 0 will yield

If a is < 10 --- 1? (1? S1: S2): S3 = 1 (1 S1 + 0 S2) + 0 S3 = S1
If a is >= 20 -- 0? (0? S1: S2): S3 = 0 (0 S1 + 1 S2) + 1 S3 = S3
Otherwise ------ 1? (0? S1: S2): S3 = 1 (0 S1 + 1 S2) + 0 S3 = S2

What's interesting to notice is that a proper account of control flow
structure necessarily involves consideration of the more general type
of branching represented by "+". This is actually the fundamental
concept, not the if-then-else.

Algebraically, you'd write:

(a>10) ((a<20) S1 + (a>=20) S2) + (a<=10) S3
= (a>10)(a<20) S1 + (a>10)(a>=20) S2 + (a<=10)S3

A Boolean algebra is a partially ordered algebra in which the
ordering relation B >= A means (A implies B). This is
equivalently rendered as:

B >= A <--> AB = A

since AB = greatest lower bound of {A,B}. Therefore,
(a>10)(a>=20) = (a>=20).
So, the original statement reduces to:

(a>10)(a<20) S1 + (a>=20) S2 + (a<=10) S3

Post a followup to this message