** Next:** Weights
** Up:** Robust parsing of word-graphs
** Previous:** Parser

##

Annotated word-graph

An annotated word-graph is a word-graph annotated with the results of
the parser. Such an annotated word-graph is defined with respect to
an input word-graph (given by the functions
and
) and with respect to the results of parsing (given
by the function
).
The * annotated word-graph* is a directed acyclic graph (*V*,*E*) where

*V* is the set of vertices consisting of the states of the
word-graph , and a new vertex
*v*_{n+1}. *v*_{0} is the start state. *v*_{n+1} is the final state.
*E* is the set of edges consisting of:
* skip* edges. For all
there are edges
.
* category* edges.
For all
there are edges
(*v*_{i},*v*_{j},*x*,*a*,*q*).
* stopping* edges.
For all
there are
edges
.

*2000-07-10*