Algebraic Composition of Function Tables

Abstract. In general, a program is composed of smaller program segments using composition, conditional constructs or loop constructs. We present a theory which enables us to algebraically define and compute the composition of conditional expressions. The conditional expressions are represented using tabular notation. The formal definition of the composition allows us to compute the close form representation of the composition of tabular expressions. The presented approach is based on a many sorted algebra containing information preserving composition. This formal definition of composition is then “lifted” to an extended algebra containing tabular expressions. The presented theory provides very compact algorithms and proofs.