Graph transformation for incremental natural language analysis

Millstream systems have been proposed as a non-hierarchical method for modelling natural language. Millstream configurations represent and connect multiple structural aspects of sentences. We present a method by which the Millstream configurations corresponding to a sentence are constructed. The construction   is incremental, that is, it proceeds as the sentence is being read and is complete when the end of the sentence is reached. It is based on graph transformations and a lexicon which associates words with graph transformation rules that implement the incremental construction process. Our main result states that, for an effectively nonterminal-bounded reader RR and a Millstream system MS   based on monadic second-order logic, the correctness of RR with respect to MS   can be checked: it is decidable whether all graphs generated by RR belong to the language of configurations specified by MS.