Another advantage of parsing schemata is that formal results on time complexity can be
obtained easily.
The time-complexity of the algorithms can directly be derived from the number of
relevant indices, where each vector 
represents h indices.
For a complete discussion of the proof on theorem 4.9,
see [Nederhof,1997a]. Note that
only those index variables are relevant, that occur in at least two different
positions.
For
example, step 
in algorithm 
has
three relevant vectors 
which each represent h
indices, resulting in a time-complexity of 
. The Step
has a 
time-complexity.
Since this is the maximum for all deduction steps, the following corollary
holds:
The time complexity analysis of 
and 
is carried out in [Becker,Heckmann,2000]. The following upper time-bounds are received:
Finally, the proofs of correctness, that are directly analogous to the CFG cases
and can be found in [Becker,Heckmann,2000]
In the first section of this chapter, the parsing schemata for CFG, according to [Sikkel,Nijhold,1997], were introduced and defined elaborately in order to offer a complete overview of this formalism. In the second and third section more than fifteen newly created parsing schemata are defined precisely.
In the following chapter, several formal aspects and applications of recursive matrix systems are discussed. In chapter 6, parsing is revisited form the implementation point of view.
