# Algebraic Dynamic Programming on Trees
## 8 Inside and Outside Grammars  
The grammars we defined in previous sections are considered as _inside_ grammars in the DP terminology. Inside grammars can be used to calculate two kinds of results. As we have seen above, a globally optimal solution for optimization problems, say the alignment distance between two trees, can be obtained. Alternatively, the partition function \(\mathcal{Z}=\sum_{\omega}e^{s(\omega)/\mathcal{T}}\) can be computed. Here, the sum runs over all configurations \(\omega\), \(s(\omega)\) is the score of \(\omega\) and \(\mathcal{T}\) is a scaling parameter. For \(\mathcal{T}\to 0\), \(\mathcal{Z}\) just counts the number of optimal solutions, for \(\mathcal{T}\to\infty\), all conformations are treated equally. The partition function \(\mathcal{Z}\) thus provides access to a probabilistic model. This view plays a key role in practical applications. As described e.g., in [5], the inside-outside algorithm for context-free grammars is analogous to the forward-backward algorithm for HMMs. The inside or forward part calculates the probability for a possible (sub)solution whereas the outside part calculates all possible solutions while keeping one (sub)solution fixed. In this way, it is possible to calculate the overall probability of, e.g., two nodes being aligned to each other in an alignment of two trees. To this end, one calculates the partition function \(\mathcal{Z}^{\prime}\) that gives a value for two nodes being matched and the partition function \(\mathcal{Z}\) for all possible cases of the complete alignment where those two nodes match. The desired probability is then the ratio \(\mathcal{Z}^{\prime}/\mathcal{Z}\) of the constrained and the unconstrained partition functions. In order to know which cases have to be calculated to obtain probabilities for possible (sub)solutions, an _Outside_ grammar can be formulated. The Outside grammar usually has more rules than the Inside grammar and is more complex. In particular, it involves additional non-terminals such as \(\left( \begin{smallmatrix}F\\ F\end{smallmatrix} \right)\) that can be conceptualized as referring to complements of non-terminals of the inside grammar. Its productions specify how the outside object on the left-hand side can be decomposed. In general, the r.h.s. of the productions contain another outside non-terminal as well as inside terminals and non-terminals. The inside objects are the ones that are currently kept fixed wheres the outside objects on the right-hand side define the parts that are used to calculate all possible (sub)solutions with the inside object being fixed. For a detailed discussion of the relationship of Inside and Outside grammars we refer to [24]. Below, we give the outside grammar in Equation (12) (with start symbol \(\left( \begin{smallmatrix}F\\ F^{*}\end{smallmatrix} \right)\), and outside \"epsilon\" symbols \(\sigma\)--given that \(\sigma\) in an outside grammar terminates with _full_ input, not the empty input) for the simple linear-cost tree alignment problem (Equation (12)) and combine inside and outside grammar to yield match probabilities. \[\left( \begin{smallmatrix}F\\ F^{*}\end{smallmatrix} \right) \rightarrow\left( \begin{smallmatrix}n\\ n\end{smallmatrix} \right)\shortstack{i}\left( \begin{smallmatrix}T\\ T^{*}\end{smallmatrix} \right)\shortstack{\big{|}\left( \begin{smallmatrix}n\\ m\end{smallmatrix} \right)\shortstack{i}\left( \begin{smallmatrix}T^{*}\\ Z^{*}\end{smallmatrix} \right)\shortstack{\big{|}\left( \begin{smallmatrix}- \\ n\end{smallmatrix} \right)\shortstack{i}\left( \begin{smallmatrix}Z^{*}\\ T^{*}\end{smallmatrix} \right)\shortstack{\big{|}\left( \begin{smallmatrix}T \\ T\end{smallmatrix} \right)\shortstack{\circ}\left( \begin{smallmatrix}F^{*}\\ F^{*}\end{smallmatrix} \right)\shortstack{\big{|}\left( \begin{smallmatrix}Z \\ T\end{smallmatrix} \right)\shortstack{\circ}\left( \begin{smallmatrix}F^{*}\\ F^{*}\end{smallmatrix} \right)\shortstack{\big{|}\left( \begin{smallmatrix}Z \\ T\end{smallmatrix} \right)\shortstack{\circ}\left(