Supporting UPA and Restriction on an Extension of XML Schema

2.1 Plan of Attack

Ultimately a regular expression is for matching strings of terminals to determine membership in a language. This is done by matching terminals in the input against successive terminal particles in the expression. A regular expression has the UPA if, for any input string, at any point there is only particle in the regular expression which could be used to match the next item in the input. The regular expression (a, b) has UPA because it will only match an 'a' followed by a 'b'. The regular expression (a{0,1}, a) does not because when the first 'a' shows up, it could match either the first a? particle or the second a particle. Determining if a regular expression has UPA is not difficult if we use standard regular expressions as described above, but numeric exponents complicate the picture. In the first case we need only check that there are no two different particles with the same terminal either in the first set of the expression or in the follow set of any particle in the expression. (As an example of why first sets alone are insufficient, consider (a, a{0,1}, (b | a))). In the latter case, though, we have examples like:

1. (a₀{4,8},a₁)
2. (a₀{8,8},a₁)
3. ((a₀,b₁{0,1}){8,8},b₂)
4. ((a₀ & b₁ & (c₂, d₃{0,1})), d₄)
5. ((a₀ & b₁ & c₂), b₃)
6. (a₀ & b₁ & (c₂, b₃{0,1}))

In the first case, we have a UPA violation because the fourth match of a₀ can be followed by either a fifth repetition or a₁. The follow function rightly puts both in follow(a₀). However, in the second case there is no ambiguity (8 repetitions of a₀ followed by one a₁. But in the third case we again have an ambiguity. On the eighth repetition, a₀ can be followed by either b₁ or b₂ - but if we make example two work, then b₂ is not in follow(a₀).

In the fourth case we have a UPA violation between d₃ and d₄. Therefore we'd want the follow set of the &-group to be in the follow set of the individual branches. However, if we do that, then we'd also need to make sure that the first sets of the other branches are not also included, because otherwise c₂ would have both b₁ and b₃ in its follow set in the fifth example. But that would then miss the UPA violation in the sixth example between b₁ and b₃.

2.2 Sources of UPA violations

Because of the issues with the two problematic constructs of &-groups and numeric exponents of the form {m,m} we need to delve further into aspects of UPA violations. There are two sources of UPA violations involving a particle that are particularly germane to our analysis.

2.3 Final UPA Algorithm

We therefore end up with the following algorithm:

UPA(α) => if α = athen

if b_i ∈ follow(a)and b_j ∈ follow(a) -> i=j then true

else if α = β{m,n} then UPA(β) /\ (first(β) ∩ confusion(β) = {})

else if (α = (β₁,...,β_n) or α = (β₁|...|β_n)) and ∩ⁿ_{i = 1} first(β_i) = {} then /\ⁿ_{i = 1}UPA(β_i)

else if α = (β₁&...& β_n) and ∩ⁿ_{i = 1} first(β_i) = {} then /\ⁿ_i=1(UPA(β_i) /\ (confusion(β_i) ∩ (∪_{j not = i}first(β_j)) = {})

else false.

3.1 Subsumption with &-groups

The straightforward subsumption story is complicated by &-groups because, even with UPA, at any point there may be more than one terminal that can match from the other machine. Consider the following pair:

1. (a{0,1}, (d & c & b), b)
2. (c, b, d, b)

Clearly, the second expression is subsumed by the first. The a is optional, (b, c, d) is one of the six possible paths through the & group, and b is the final terminal to be matched. However, the c and d branches of the &-group both have two transitions to a b, so the naive algorithm fails. A naive fix would be to break apart the group, listing all the alternatives:

(a{0,1}, ((d , c , b) | (d , b , c) | (c , d , b) | (c , b , d)(b , c , d)(b , d , c)), b)

However, this is exponential (actually O(n!)) in the size of the orignal expression, although the resulting expression still obeys UPA.

Any solution not expanding the content model needs to keep track of which branches of the &-group have been traversed at any point and only move from the &-group when all the required branches have been matched. Such a solution would also need to keep track of nested &-group - unlike choice, &-groups are commutative but not associative; i.e. ((a & b) & (c & d)) is not the same as ((a & c) & (b & d)), as the second allows (a, c, b, c), but the first requires that a be adjacent to b. This would imply the use of a stack.

To summarize, we need a means of indicating all the branches of an &-group such that we can keep track of which branches have been traversed and which have not. Further, this should not require rewriting the content model - either in advance or during execution of the algorithm - as that would return us to exponential behavior.

We will handle each &-group as a bit-vector of the length of the number of branches. We will divide this vector in two parts - the upper part corresponds to the opaque branches and the lower part to the transparent branches. For example, suppose we have the &-group (a? & b & c &d?) and want to see if it subsumes the sequence (b, a, c). We have two opaque branches and two transparent ones. We rewrite this as (b₃ & c₂ & d₁? &a₀?), corresponding to the bit-vector 1111, or 15, for all four branches, or 12, for just the opaque branches. We assign each branch to the corresponding bit. Let us call these the max and min values for the group. On entering the &-group we start with a bit-vector of 0000 - no branches completed. We cannot "leave" the group unless we've matched at least the required branches, so we'd need a bit vector of at least 1100. At each branch check, the bit vector, as a binary value, must increase so we know we've finished a new branch. Transitions corresponding to choices where the appropriate bit is 0 are active. Those wehre the bit is 1 are inactive.

To show the process, we first match b with b₃ and xor the bit-vector with 2³, where the power is the number of the matched branch. This gives a bit vector or 1000. Next we match the a with a₀ and the bit vector becomes 1001. Finally we match the c with c₂, giving a bit-vector of 1101. As 1100 ≤ 1101 ≤ 1111, the subsumption holds.

On the other hand, if we try to check (b, a, d), our final bit-vector is 1011. Since 1011 < 1100, the subsumption doesn't hold. Finally, if we try to check (b, b, d), we'd check the first b and get 1000. Checking the second b, we'd xor 1000 with 1000 with a result of 0000. As 0000 < 1000, we'd know we've tried to match the same branch twice and the subsumption fails.

At this point we need to describe how to build an automaton for an extended regular expression. In addition to the usual transitions, we need to keep track of the following when traversing a terminal:

• When entering an &-group, push an empty bit-vector on the stack, or push().
• For any state transition from the end of a branch, update the top bit-vector, or update(n), where n is a power of 2. This returns true if the result of an update increases the value of the bit-vector and false otherwise.
• For any state transition leaving the group, ensure the bit-vector's value is between the min and the max and then pop it, or test(min, max).

Note that there may be more two transitions from a state with the same terminal. However (due to UPA) one will return to the &-group and the other will leave it. Each has an associated test condition, and only one can succeed.

Each transition, t, in our automaton therefore has properties:

1. pre(t) is a state, the state the machine must currently be in for this transition to be applied.
2. post(t) is the state the machine is in after the transition
3. terminal(p) is the terminal that this transition matches
4. action(p) is a list of push(), update(n), or test(min, max). It may be empty if no actions are to be performed for that transition.

This automaton does not have provision for numeric exponents - they'll be handled in the sequel.

Consider the following expression: (₀a₁, ((b⁰₂ & c¹₃){0,1}⁰ & ((d₄, e₅) | e₆)¹), e₇), where the subscripts are for identifying the states we'll produce for the automaton and the superscripts are for the branches of the &-groups. By the discussion above, we start at state 0 and produce the following transitions:

1. (0, 1, a, [])
2. (1, 2, b, [push(), push(), update(0)])
3. (1, 3, c, [push(), push(), update(1)])
4. (1, 4, d, [push()])
5. (1, 6, e, [push()])
6. (2, 3, c, [update(1)])
7. (2, 4, d, [test(3,3), update(0)])
8. (2, 6, e, [test(3,3), update(0)])
9. (2, 7, 3 [est(3,3), update(0), test(2,3)])
10. (3, 2, b, [update(0)])
11. (3, 4, d, [test(3,3), update(0)])
12. (3, 6, e, [test(3,3), update(0)])
13. (3, 7, e, [test(3,3), update(0), test(2,3)])
14. (4, 5, e, [])
15. (5, 2, b, [update(1), push()])
16. (5, 3, c, [update(1), push()])
17. (5, 7, e, [update(1), test(2, 3)])
18. (6, 7, e, [update(1), test(2,3)])

The only accepting state is 7.

3.2 Comparing Two Automata

When comparing two automata we are building a new automaton that is a subset of the product of the two input automata. Let us call the automaton for the initial content model B (for base) and the one we are testing as R (for restriction). At each point, there will be some set of possible transitions from a current state in the automaton for R for which corresponding transitions must exist in B. There are two sets of important subcases:

• At least one of the transitions is into an &-group
• None of the transitions is into an &-group

The latter case corresponds to traditional automata - the former to our special cases. All in all, this creates nine cases. For each, transitions can be one of:

• All "ordinary" - there are no push commands associated with the transition, so it does not enter an &-group. We will call these simple transitions.
• All lead into &-groups. The number of groups may actually be nested. We will call transitions leading into an &-group "&-group transitions".
• A mix of the above, where there was a choice (or transparent particle) in the original content model between an &-group and some other particles.

There is also an important asymmetry between B and R for determining valid subsumptions. In particular, if some state in R is matched to a state in B by the algorithm, and one transition from the state in R goes to an &-group, then one of the following must be true:

• All the transitions in B are simple choices. For example, (a & b & c) is subsumed by (a | b | c){1, unbounded}. Likewise, ((a & b & c) | d | e) is subsumed by (a | b | c | d | e){1, unbounded}. Note, additionally, there must be exactly one branch in B for each branch in R - (a & b & c) is not subsumed by (a | (b, c)) because it doesn't allow the ordering (b, a, c)
• At least the transitions in B corresponding to an &-group transitions in R to the same &-group are also to an &-group, and no other choices may be in that &-group. For example, ((a & b & c) | d | e) is subsumed by ((a & b & c & f{0,1}) d | e){1, unbounded} but not by ((a & b & c & d) | e){1, unbounded}, as the latter wouldn't allow the d to come after the e. Therefore if the algorithm is matching transitions from an &-group in R and an &-group in B, it can't leave the &-group in R unless it also leaves B. To aid in this, we introduce two predicates on states:
  1. &-group-only(q) returns true iff all the unmatched transitions leaving state q enter an &-group. Matched transitions are those that have already been examined by the altgorithm and used in a transition in the output.
  2. mixed(q) returns true if some of the unmatched transitions leaving state q enter an &-group, while others do not.

Finally, if the current transition in R is part of an &-group, then clearly there must always be transitions in B corresponding to all the untraversed choices in the &-group in R. Because of the structure of choice groups, this means one of the following must be true:

1. The choice group in B is one or more groups, each containing all the choices in R - i.e., either (a | ... |b){1,unbounded} or ((a |...| b)...(a |...| b)), where the second is a list as long as the choices in the &-group in R.
2. The choice group is a tree of all the alternatives, where at each level there are at least those choices left from the previous level, i.e., if the grup in R is (a & b & c), the the group in B would be ((a, ((b,c)|(c,b))) | (b, ((a,c)|(c,a))) | (c, ((b,a)|(a,b)))).

If there is a sequence of choices similar to the first choice above, but not all of them contain all possible choices, then one of them, say the 3^rd, doesn't contain some choice, say c. Then the sequence doesn't support those alternatives with c in the 3^rd position. Therefore every choice group in the sequence must contain all the alternatives.

As mentioned this is very asymmetric - if all transitions from R are simple;, then it doesn't matter whether transitions in B are simple or &-group transitions. If the transition in R matches a simple transition in B, then we proceed as usual. If it matches an &-group transition in B, then the successor states in R must eventually match all the branches in B, but they only need to match one ordering of them. As a result, when traversing states for an &-group it is not necessary to check all sequences.

This provides enough information to generate an algorithm. Because we need to check all alternatives for each state, we need to explicitly manage the &-group stacks for both B and R. As with the traditional algorithm, we invert the states in the base, create a machine from the cross-product of the states of the input machines, and determine that there are no states in the resulting machine that includes accepting states from both input machines.

cross-product(q_R, q_B, R-stack, B-stack, output) is

        if (&-group-only(q_R) and mixed(q_B)) then fail.

        if &-group-only(q_R) and not &-group-only(q_B then

        either

                for each transition (q_R,q'_R,α,actions_R) there is a transition (q_R,q'_R,α,actions_R)

        or

                for each active transition (q_R,q'_R,α,actions_R) there is a transition (q_R,q'_R,α,actions_R) and not ((q_R,q_B),(q'_R,q'_B)α) ∈ output

        or fail.

        for each active transition (q_R, α, q'_R, actions_R) do

                save top(R-stack) -> hold-R. (As the list of commands may include multiple push() and update() commands, this may involve storing more than one item from the stack. The process is reversed after the recursion.)

                find transition an active transition (q_B, α, q'_B, actions_B) or fail.

                save top(B-stack) -> hold-B.

                if (not ((q_R,q_B), α, (q'_R,q'_B)) ∈ output) then

                        if the number of test() operations in actions_R ≠ number of test() operations in actions_B then fail.

                        add ((q_R,q_B), α, (q'_R,q'_B)) to output.

                        apply actions_R to R-stack.

                        apply actions_B to B-stack.

                        cross-product(q'_R, q'_B, R-stack, B-stack, output).

                        update R-stack from hold-R.

                        update B-stack from hold-B

We start the algorithm with the start states from both machines, two empty stacks, and an empty set for the output states.

3.3 An example

As a simple example, we test whether the expression above subsumes (a, ((d, e) | e), e). If we show it as above, (₀a₁, ((d₂, e₃) | e₄), e₅) we can see that the transitions are:

• (0, 1, a, [])
• (1, 2, d, [])
• (1, 4, e, [])
• (2, 3, e, [])
• (3, 5, e, [])
• (4, 5, e, [])

The only accepting state is 5.

We start at state 0 for both machines. Since we invert the accepting states of the base machine, its accepting states are 0 - 6, but not 7.

1. There is only one transition in R for state 0, and only one for B. We add ((0, 0), (1, 1), a) to the output. Neither stack is changed.
2. We recurse with R state 1 and B state 1. There are two transitions in R from state 1. We start with (1, 2, d, []). This matches (1, 4, d, [push()]) in B. We add ((1,1), (2,4), d) to the output machine and push 0 on the B stack.
3. We recurse with R state 2 and B state 4. There is one transition in R - (2, 3, e, []). There is likewise only one transition in B - (4, 5, e, []). We add ((2,4), (3, 5), e) to the output.
4. We recurse with R state 3 and B state 5. The transition in R is (3, 5, e, []). In B we have (5, 7, e, [update(1), test(2,3)]). We need to test the B transition. We xor 10 binary with the top of the B stack, or 00, to get 10. This is in the acceptable range (10 ≤ 10 ≤ 11). As we are transitioning out of the group we pop the B stack (now empty) and add ((3,5), (5,7), e) to the output.
5. We recurse again with R's state 5 and B's state 7. There are no transitions, so we return to the nearest branch (fixing the stacks as we go up), at 2 above. We take R's other transition, (1, 4, e, []). This matches (1, 6, e, [push()]) in B. We add ((1, 1), (4, 6), e) to the output, and push 0 on the B stack.
6. We recurse with 4 and 6. In R there is only (4, 5, e, []). In B this matches (6, 7, e, [update(1), test(2, 3)]). As with steps 4 we arrive at the end, adding ((4, 6), (5, 7), e) to the output.
7. We terminate as there are no choices left.

The states of the output machine are ((0,0), (1,1), (2,4), (3, 5), (5,7), (4,6)). As the only accepting state in R is 5, and the only non-accepting state in B is 7, we conclude that B subsumes R.

3.4 Subsumption with Numeric Exponents

Numeric exponents add significant complexity to subsumption testing. In particular, the nesting of numeric exponents, both in B and R, potentially require testing a large number of alternatives to ensure for each path through R there is at least one path through B. And yet, in many cases this is not necessary because of overlap in the areas covered by the exponents.

We will first give a couple of example of exponents and valid and invalid content models. From that, we will be able to extract some important aspects of the problem.

For example, consider the following: (a{4,5}{2,3}). Here we have a sequence of either 4 or 5 repetitions of a, repeated 2 or 3 times. This means the following are legal:

• aaaaaaaa
• aaaaaaaaa
• aaaaaaaaaa
• aaaaaaaaaaaa
• aaaaaaaaaaaaa
• aaaaaaaaaaaaaa
• aaaaaaaaaaaaaaa

In other words, sequences of 8 - 10 or 12 - 15 a's. However, if we have, instead, (a{4,5}{6,7}), the we have a series of 24-30 (from 6 X 4 to 6 X 5) and a series of 28 - 35. But since these overlap, we can just consider this a series of 24 to 35. I actually takes a certain amount of effort to construct example that do not have this overlap.

More generally, regarding subsumption, consider two content models, (ρ{m_0,,n₀}...{m_i,n_i}) and (β{m'₀,n'₀}...{m'_j,n'_j}). We wish to establish if the latter subsumes the former. Clearly we must first establish if β subsumes ρ. Then we must determine that all possible ranges of ρ are also possible ranges of β. We can enumerate the ranges by choosing all the different m and n for each subscript - from (m₀*m₁*...*m_i, n₀*m₁*...*m_i) to (m₀*n₁*...*n_i, n₀*n₁*...*n_i). The maximum number of distinct ranges of ρ is 2ⁱ and of β is 2^j. If β subsumes ρ, then we only need to determine that each range of ρ is contained within a range of β. We will use ranges(n) to refer to the ranges of the first n values in a list of exponents.

The more complex case is when the scoping is not so clear. For example, if B is (a | b){4,12} and R is (a{2,3},b{5,7}), then the iterations of a are insuficient without the additional iterations of b. Also consider B as (((a | b){3,5},c{0,1}){6,9},d) and R as ((a,b){20,25},c,d). Here, the repetitions of (a,b) in R must account for both the inner and outer exponents in B.

We can consider each terminal and each transition in B as having a nesting depth, depending on how many exponents are crossed from source to sink. Before a transition may be taken, all the "obligations" at higher levels must be fulfilled. For example, in B above, the d is at level 0 (not in the scope of any exponent) while a, b, and c are at level two. Therefore the transition from a to d is at level 0, and the exponent at levels 1 and 2 must have been satisfied before that transition could be crossed. At the other end, there is a transition from a to b at level 2, so that is counted against the exponent at that level ({3,5}), as well as a transition at level 1, so the number of iterations of a's and b's is either between 3 and 5, or over 18.

As with automata for &-group, we will need a stack for each exponent and some extra commands to attach to each transition. Each entry on the stack has an exponent and a counter to track the number of iterations completed. The counter has a pair to keep track of min and max iterations from the other automaton and a single number to track the number of matches from the innermost particle. In this case there are three kinds of command:

1. push({m,n}) pushes an entry on the stack, initially ({m,n}, 0). These commands are put on transitions entering the scope of an exponent.
2. increment increases the innermost counter. These commands are put on transitions that complete the particle contained in an exponent.
3. check(n) tests whether the counter satisfies the innermost n exponents.
4. upto(m) gives the maximum nesting level that a transition can affect.

It is possible for a single transition to have commands of all three types.

For example, the expression (₀((a₁ | b₂){10,11}²,c₃{0,1}²){6,9}¹,d₄) translates to the following transitions:

1. (0, 1, a, [push({6,9}), push({10,11}), increment])
2. (0, 1, b, [push({6,9}), push({10,11}), increment])
3. (1, 1, a, [increment])
4. (1, 2, b, [increment])
5. (1, 3, c, [check(2), upto(1), increment])
6. (1, 4, d, [check(1)])
7. (2, 1, a, [increment])
8. (2, 2, b, [increment])
9. (2, 3, c, [check(2), upto(1), increment])
10. (2, 4, d, [check(1)])
11. (3, 1, a, [push({10,11}), increment])
12. (3, 2, b, [push({10,11}), increment])
13. (3, 4, d, [check(1)])

The algorithm follows:

cross-product(q_R, q_B, stack_R, stack_B, output) is

        for each transition (q_R,q'_R, α, actions_R) do

                for each transition (q_B,q'_B, α, actions_B) where

                        ((q_R,q_B),(q'_R,q'_B), α) not ∈ output

                do

                        ({m_R,n_R}, iter_R) = top(stack_R);

                        ({m_B,n_B}, iter_B) = top(stack_B);

                        if check(i_R) = actions_R[0] and check(i_B) = actions_B[0] then do

                                for {k_R,l_R} in ranges_R(i)

                                        for {k_B,l_B} in ranges_B(i_B)

                                                if l_R * iter_B > k_B * iter_R and upto(j_B) = actions_B[1] then

                                                        newk = max(0, k_R * iter_B - k_B * iter_R)

                                                        newl = l_R * iter_B - k_B * iter_R

                                                        for {newm, newn} in range_B(j_B + 1)

                                                                pop stack_B to j_B

                                                                ({m_B,n_B},iter_B) = top(stack_B);

                                                                set top of stack_B to ({m_B - (iter_B + newk div newm),n_B - (iter_B + newl div newm)}, 0)

                                                                add ((q_R, q_B), (q'_R, q'_B), α) to output.

                                                                pop stack_R

                                                                apply remaining actions to stacks.

                                                                cross-product(q'_R, q'_B, stack_R, stack_B, output)

                                                                 restore top of stacks.

                                                else if iter_R * k_B > iter_B * k_R

                                                                add ((q_R, q_B), (q'_R, q'_B), α) to output.

                                                        pop stack_R

                                                        set top of stack_B to ({(iter_R * k_B - iter_B * k_R) div iter_R, iter_R * l_B - (iter_B * l_R) div iter_R}, 0)

                                                        if (iter_R * l_B - iter_B * l_R) - (iter_R * k_B - iter_B * k_R) ≥ 0 then

                                                                cross-product(q'_R, q'_B, stack_R, stack_B, output)

                                                else if iter_R * k_B ≤ iter_B * k_R ≤ iter_B * l_R ≤ iter_R * l_B then

                                                        pop stack_B

                                                        pop stack_R

                                                        apply remaining actions to stacks.

                                                        cross-product(q'_R, q'_B, stack_R, stack_B, output)

                                                        restore top of stacks.

                        else if check(i) = actions_R[0] and q'_B ≤ q_B (iteration) then

                                        if iter_B * n_R < n_B do

                                save top of both stacks.

                                apply actions_R to stack_R.

                                set top of stack_B to ({m_B - iter_B * m_R,n_B - iter_B * m_R}, 0)

                                apply actions_B after the initial increment action to stack_B.

                                cross-product(q'_R, q'_B, stack_R, stack_B, output)

                                restore top of stack.

                        else if check(i) = actions_R(0) and

                                m_R ≤ iter_R ≤ n_R then

                                        save top of both stacks.

                                        apply actions to stacks.

                                        cross-product(q'_R, q'_B, stack_R, stack_B, output)

                                        restore both stacks.

                        else if check(j) = actions_B[0] then do

                                        save top of both stacks.

                                        apply actions to stacks.

                                        if m_B ≤ iter_B ≤ n_B then

                                                cross-product(q'_R, q'_B, stack_R, stack_B, output)

                                        restore both stacks.

                        else

                                save top of both stacks.

                                apply actions to stacks.

                                cross-product(q'_R, q'_B, stack_R, stack_B, output)

                                restore both stacks.

3.5 An example

We'll now give an example of this algorithm in action. We'll use the expression ((a, b){40,43}, c, d), which translates to the following automaton:

1. (0, 1, a, [push({40, 43})]
2. (1, 2, b, [increment])
3. (2, 1, a, [])
4. (2, 3, c, [check(1)])
5. (3, 4, d, [])

First, we flip accepting states in B. As the only accepting state was 4, we now have 4 as the only non-accepting state. We then start with state 0 from both machines. For each, there is one transition across a. We push ({40, 43}, {0, 0}) on the R stack and both ({6, 9}, {0, 0}) and ({10, 11}, {0, 0}) on the B stack, then increment B, so the B stack is [({10, 11}, {1, 1}),({6, 9}, {0, 0})]. We are in states 1_R and 1_B. We add ((0, 0), (1, 1), a) to the output. Now the only transitions are across b in both. We execute (1, 2, b, [increment]) in R and then B. The R stack is now [({40, 43}, {1, 1})] and the B stack is [({10, 11}, {2, 2}),({6, 9}, {0, 0})]. We add ((1, 1), (2, 2), b) to the output.

There are now two possibilities in R, either transition 2 or 3 above. If we traverse the a path, we bring ourselves back to state 1 in both machines, but we add ((2, 2), (1, 1), a) to the output.

If we traverse the c, we find ourselves in the most complex part of the algorithm. The R transition is 4, above. The B transition is 5. Top of the R stack is ({40, 43}, {1, 1}), top of the B stack is ({10, 11}, {2, 2}). As 40 * 2 > 10 * 1, and 1 < 2 in check(2, 1), we take the first branch. We set newk to 70 and newl to 76. The only values for newm and newn are 10 and 11. As 6 ≤ 7 ≤ 7 ≤ 9, we set the B stack to [({0, 2}, {0, 0})]. We add ((2, 2), (3, 3) c) to the output and continue. We perform the last command from the B transition, and increment, and we pop the top of the R stack. The R stack is now empty and the B stack is [({0, 2}, {1, 1})]. From here there is one transition in R, across d, and one corresponding one in B. In R we end up in state 4 with an empty stack. In B, we check the first entry on the stack. As 0 ≤ 1 ≤ 1 ≤ 2, we pass and pop the stack. So we add ((3, 3), (4, 4), d) to the output. Checking the output, we see there is no state with an accepting state from both input machines, so we conclude that B subsumes R.