
My thesis is divided into two parts. The first one handles the N best trees problem for weighted tree automata, and the second one handles the modelling of semantic representations via graph grammars.

*Write down 1 and 2 with titles*

Start with 1 (and perhaps note that the introduction to the problem will be rather long).

Show the example sentence "They scratch the dog with a stick."

Say that it is ambiguous and that we can represent the various meanings using syntax trees. Syntax is the words, and their order. 

Build the two syntax trees for the two possible interpretations. 

Extract wta rules from them both.

Say that this is what is done by computers given a human-annotated corpus. Also assign weights -- smaller is better.

Then, assume that we have a wta that represents a weighted tree language. If we want to use the trees that best represent what we can expect to see in a language over the domain of concepts and relations, then one method is to extract the N trees of smallest weight from a compact representation -- a wta. 

*Show how our algorithm works*

Now, to part 2.

*Take and draw the example with the host*

Modelling semantics using graphs is "newer" than using trees to model syntax and is therefore less researched. We represented weighted tree languages using a weighted tree automaton, and the goal is to develop a model to represent graph languages to model semantic graphs.

*Show HRG and CHRG*

(Perhaps mention that there is also graph automata?)

*Finally, show our graph extension grammars*
