## 8 Evaluation Algebras and Their Products  
Up to this point, we were mainly concerned with modeling the search spaces for a variety of optimization problems. Our focus was on signatures, rewrite rules and grammars. The evaluation algebras we gave were simple, or even omitted. Where shown, they were examples of one kind of scoring that could underlie our desired objective. This is fine as long as we think of each ICORE using _one_ particular algebra. In real applications, one is much more likely to work with combinations of several algebras, called algebra products. Products do not formally extend the power of our approach, as each product could also be hand-coded as a single algebra. The gain in terms of programming productivity here comes from the fact that we can create more refined analyses from simpler ones without changing tried-and-tested code.  
In algebraic dynamic programming, _all_ scoring aspects are captured in the algebra. They are independent of the grammar and the rewrite rules. Consequently, Bellman's Principle can be established looking at the algebra only. This, by itself, is an advantage, because we can separately experiment with either algebra, tree grammar, or rewrite system as our modeling ideas evolve.  
The second benefit of such perfect separation of search space and evaluation is that one can define high-level \"product\" operations on two algebras over the same signature. \(\mathcal{G}(A*B,x)\) does an analysis based on \(A\) and \(B\), depending on the precise definition of \"*\". And since \(A*B\) is just another algebra, we can build \((A*B)*C\), \((A*B)*(C*D)\) and so on. Thus, we can build up sophisticated scoring schemes from simpler ones with a single keystroke, and if our framework understands and implements the product operation, this requires no code modification on our side. Three such products were defined with classical ADP [42], a _Cartesian_, a _lexicographic_, and an _interleaved_ product. Let us recall the definition of the most versatile one.  
**Definition 7**.: _Let \(A\), \(B\) be two algebras over a signature \(\Sigma\). The lexicographic product \(A*B\) is an evaluation algebra over \(\Sigma\) which evaluates each candidate \(t\) according to \((A*B)(t)=(A(t),B(t))\) and applies the objective function_  
\[\phi_{A*B}[(a_{1},b_{1}),\ldots,(a_{m},b_{m})]=[\,(l,r)\mid\] (17) \[l\in\mathrm{set}(\phi_{A}[a_{1},\ldots,a_{m}]),\] \[r\in\phi_{B}[\,r^{\prime}\mid(l^{\prime},r^{\prime})\leftarrow[( a_{1},b_{1}),\ldots,(a_{m},b_{m})],\ l^{\prime}=l\,]\ \ ]  
_where \(\mathrm{set}\) reduces a multiset of values to a set. _  
Said in words: The search space is evaluated according to \(A\), and the candidates resulting from this are re-evaluated according to \(B\). When both algebras optimize under some ordering, their product performs optimization under the lexicographic combination of the two orderings; this motivates the name of the product. But the lexicographic product is useful also in cases where some of the algebras involved do not perform optimization.  
To demonstrate the versatility of this product operation,, let \(A\) and \(B\) be two scoring algebras with different optimization objectives, \(C\) a \"counting\" algebra which assigns to each candidate a score of 1, and \(\phi\) sums up the scores, \(D\) an algebra that computes a classification attribute from each candidate, and \(P\) an algebra that computes a print representation from a candidate. For \(D\) and \(P\), \(\phi\) is the identity, i.e., no optimization is performed. For example, \(\mathcal{G}(P,x)\) would simply print all candidates in the search space of \(x\). We show in Table 2 some analyses which can be achieved with \(A,B,C,D\), and \(P\) in lexicographic products. All three product operations mentioned above have been implemented for classical algebraic dynamic programming in the [PERSON]'s GAP system [16; 42], where they have proved useful in real-world applications; they should work with ICOREs just as well.