## 9 Relation with Other Formal Models
### \"Classical\" ADP Algorithms Seen as ICOREs  
ICOREs build upon and extend the framework of ADP. Up to this point, ADP has been formulated solely for problems where the inputs are sequences [13; 42], whereas ICOREs can also handle ordered trees. But the transition from ADP to ICOREs is deeper than just a change of the input data type. In ADP, the tree grammar is responsible for defining the search space _and_ relating its candidates to the input sequence(s). A process called _yield parsing_ serves as the underlying machinery for the implementation of ADP programs. With ICOREs, the tree grammar takes only responsibility for defining the search space over _all_ problem instances, while the relation to a concrete problem instance is established by the inverse coupled rewrite relation. This brings more expressive power-but a direct implementation in the style of a yield parser is no longer at hand. What remains common to both ADP and ICOREs is the evaluation of the search space via scoring algebras. Claiming that ICOREs subsume ADP in a mathematically strict sense, we should indicate how an ADP algorithm is re-coded as an ICORE. Formally, ADP uses input sequences over alphabets, tree grammars and signatures, but no rewrite rules. Let \(\Sigma\) be a signature over alphabet \(\mathcal{A}\). A tree grammar \(\mathcal{G}\) over \(\Sigma\) specifies a language of trees, \(L(\mathcal{G})\subseteq T_{\Sigma}\) as usual. The yield string \(y(t)\) of a tree \(t\in T_{\Sigma}\) is the string of its leaf symbols from \(\mathcal{A}\), in their left-to-right order. Let \(\mathcal{E}\) be a \(\Sigma\)-algebra with objective function \(\phi\), and let \(x\in\mathcal{A}^{*}\) be our input sequence. An ADP problem instance is defined by \(\mathcal{G}\), \(\mathcal{E}\), and \(x\). Its solution is  
\[\mathcal{G}(\mathcal{E},x):=\phi[\mathcal{E}(t)|t\in L(\mathcal{G}),y(t)=x] \tag{18}\]  
where square brackets denote multisets. Another way to express the above definition would be (where \(\circ\) denotes function composition and \(\mathcal{E}(...)\) evaluates to a multiset.) \[\mathcal{G}(\mathcal{E},x)=(\phi\ \circ\ \mathcal{E})(y^{-1}(x)\cap L( \mathcal{G})) \tag{19}\]  
The process of computing \(y^{-1}(x)\cap L(\mathcal{G})\) is called yield parsing, and a top-down or bottom-up yield parser is the basic engine behind ADP implementations. Such an ADP specification given by \(\Sigma,\mathcal{G}\) and \(\mathcal{E}\) is converted into an equivalent ICORE as follows:  
The ICORE schematic_ADPintroduces a satellite signature _SEQ_ for the input sequence, uses \(\Sigma\) as the core signature, and retains the tree grammar. In the rewrite rules of form, \(x_{i}\) and \(x_{j}\) are differentvariables even when \(X_{i}\) and \(X_{j}\) are the same non-terminal symbol, and the righthand side produces a portion of the yield string of \(t(x_{1},...,x_{k})\). Remember that \(t\) must not be a single variable, as term rewrite rules of the form \(x\rightarrow\ldots\) are not allowed. Therefore, chain productions \(X\to Y\) in \(\mathcal{G}\) cannot give rise to rewrite rules, and this is why we need to retain \(\mathcal{G}\) as a grammar in the ICORE rather than simply replacing it with \(T_{\Sigma}\). By construction, the rules in this ICORE rewrite a core term \(t\in L(\mathcal{G})\) to its yield string \(y(t)\in\mathcal{A}^{*}\). Constructing the inverse of this particular relation is yield parsing. Hence, the same set of core terms is evaluated in Equation (19) and in the ICORE schematic_ADP by virtue of Definition 4). The above construction was given for a n ADP program with single input. For several input sequences, ADP uses a multi-track tree grammar. In this case, each track of the grammar gives rise to a component in the coupled rewrite rules. This proves the equivalence of the search spaces in the ADP and the ICORE problem specification. On the side of evaluation algebras, there is no difference between ICOREs and ADP.