Thus, because bags of T correspond to the cache at each step of the parser, the parser's cache will contain u at the step at which v is pushed into the rightmost position of the cache.
the automaton can build each edge of G. Combining Lemmas 3 and 4, and using Lemma 1 from Section 2, we have the following main result, which is a characterization of the relative treewidth of a graph with respect to an ordering of its vertices.