Discrete decision theory: manipulations (Q1102136)

Decision trees are a frequently used form of representation especially in application areas in which efficiency is important. Despite this little is known about how they can be manipulated. This paper introduces identities for manipulating decision trees. Decision trees are interpreted to be terms of coalgebras and for this method of interpretation it is shown that the identities are complete. When decision trees are viewed as terms of an algebraic system, it is reasonable to look for special forms into which these terms can be transformed. Not only do decision trees have a canonical form but also a number of other significant forms. These forms include the simply reduced form and the irreducible form. The former is useful in determining equality, while the latter is significant in the problem of optimizing decision trees.