## 2 A Motivating Example
Therefore, it is possible to assign a score to each core term with a score algebra implementing \(\mathtt{rep}\), \(\mathtt{ins}\), \(\mathtt{del}\), and \(\mathtt{mty}\) as functions over some concrete score data type. For example, the unit cost model used in the Levenshtein distance is expressed by the score algebra UnitScore. \[\mathtt{rep}(a,b,x) = \text{if }a==b\text{ then }x\text{ else }x+1\] \[\mathtt{del}(a,x) = x+1\] \[\mathtt{ins}(a,x) = x+1\] \[\mathtt{mty} = 0\] \[\phi = \min\]  
\(\phi=\min\) means that we search for the edit script of minimal cost. Under interpretation by algebra UnitScore, our example core term \(c\) evaluates to a score of 3 (which happens to be optimal). Given these ingredients, a solution to the edit distance problem is defined as any core term which rewrites to \(U\) and \(V\) by the above rewrite rules, and evaluates under the algebra UnitScore to the optimal score of all such terms. Signatures and terms, rewrite rules and algebras--this may seem a bit of a technical overhead for defining the Levenshtein distance of two strings. However, note that we have achieved a perfect separation of search space definition and scoring. This pays off when it comes to specifying more sophisticated problems. More flexible scoring schemes for the edit distance problem are easily provided. For example, our functions can score in a character-dependent fashion. Similarity scoring can replace distance scores, with positive scores for matches, negative scores for gaps and proper replacements, and switching to \(\phi=\max\). Under a probabilistic scoring algebra, scores should multiply (rather than add up), and we better set \(\mathtt{mty}=1\). Such variations to the scoring scheme only require a new algebra definition. Other changes affect the signature, and consequently the rewrite rules. We shall see in Section 5 that to introduce affine gap scoring, for example, it is enough to add operators \(\mathtt{open\_del}\) and \(\mathtt{open\_ins}\) to the signature. In optimization there are many situations where we want to restrict the set of admissible solutions to those satisfying additional criteria. To this end, we add to our formal machinery one more feature: We will use tree grammars to restrict the universe of candidates to a subset of the algebra of core terms. Let us come back to the string edit distance problem, and specialize it at hand. We now require that an edit script must not have two adjacent indels (insertion or deletion). This type of constraint is applied, for example, in RNA-RNA interaction. We design a tree grammar that restricts the candidate space accordingly:  
\[A^{*} \rightarrow \mathtt{rep}(a,b,A)\mid\mathtt{del}(a,M)\mid\mathtt{ins}(a,M) \mid\mathtt{mty}\] \[a{\sim}X \leftarrow \mathtt{del}(a,X) \rightarrow X\]0  
\(A\) and \(M\) are non-terminal symbols. The asterisk marks \(A\) as the axiom symbol of the grammar. The set of edit scripts satisfying the constraint on indels is exactly the language of core terms accepted by the grammar. This concludes our informal presentation of ICOREs. The reader who feels familiar with established concepts such as signatures, rewrite rules and tree grammars may skip ahead from here to the definition of ICOREs in Section 4.