YES Problem: strict: topB(i,N1(x),y) -> topA(1(),T1(x),y) topA(i,x,N2(y)) -> topB(0(),x,T2(y)) topB(i,S1(x),y) -> topA(i,N1(x),y) topA(i,x,S2(y)) -> topB(i,x,N2(y)) topA(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topA(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) weak: topA(i,N1(x),y) -> topA(1(),T1(x),y) topB(i,x,N2(y)) -> topB(0(),x,T2(y)) topA(i,S1(x),y) -> topA(i,N1(x),y) topB(i,x,S2(y)) -> topB(i,x,N2(y)) topB(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) topA(i,N1(x),y) -> topA(i,N1(C(x)),y) topB(i,x,N2(y)) -> topB(i,x,N2(C(y))) topA(i,T1(x),y) -> topA(i,T1(x),y) topB(i,x,T2(y)) -> topB(i,x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,S2(D(y))) Proof: Matrix Interpretation Processor: dim=2 interpretation: [2 0] [2 1] [1 0] [topA](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [0 0]x2, [1 0] [1] [S1](x0) = [0 3]x0 + [1], [2 0] [2 1] [1 0] [topB](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [0 0]x2, [1 0] [T1](x0) = [0 0]x0, [3 0] [N2](x0) = [0 1]x0, [1 0] [C](x0) = [0 2]x0, [1 0] [N1](x0) = [0 0]x0, [3 0] [T2](x0) = [0 0]x0, [D](x0) = x0, [3 0] [0] [S2](x0) = [2 2]x0 + [2], [0] [0] = [0], [0] [1] = [0] orientation: [2 0] [2 0] [1 0] [2 0] [1 0] topB(i,N1(x),y) = [0 0]i + [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topA(1(),T1(x),y) [2 0] [2 1] [3 0] [2 1] [3 0] topA(i,x,N2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(0(),x,T2(y)) [2 0] [2 3] [1 0] [3] [2 0] [2 0] [1 0] topB(i,S1(x),y) = [0 0]i + [0 0]x + [0 0]y + [0] >= [0 0]i + [0 0]x + [0 0]y = topA(i,N1(x),y) [2 0] [2 1] [3 0] [2 0] [2 1] [3 0] topA(i,x,S2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,N2(y)) [2 0] [2 0] [3 0] [2 0] [2 0] [3 0] topA(i,N1(x),T2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,N1(x),S2(y)) [2 0] [3 0] [2 0] [3 0] topA(1(),T1(x),T2(y)) = [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(1(),T1(x),S2(y)) [2 0] [2 0] [1 0] [2 0] [1 0] topA(i,N1(x),y) = [0 0]i + [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topA(1(),T1(x),y) [2 0] [2 1] [3 0] [2 1] [3 0] topB(i,x,N2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(0(),x,T2(y)) [2 0] [2 3] [1 0] [3] [2 0] [2 0] [1 0] topA(i,S1(x),y) = [0 0]i + [0 0]x + [0 0]y + [0] >= [0 0]i + [0 0]x + [0 0]y = topA(i,N1(x),y) [2 0] [2 1] [3 0] [2 0] [2 1] [3 0] topB(i,x,S2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,N2(y)) [2 0] [2 0] [3 0] [2 0] [2 0] [3 0] topB(i,N1(x),T2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,N1(x),S2(y)) [2 0] [3 0] [2 0] [3 0] topB(1(),T1(x),T2(y)) = [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(1(),T1(x),S2(y)) [2 0] [2 0] [1 0] [2 0] [2 0] [1 0] topA(i,N1(x),y) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topA(i,N1(C(x)),y) [2 0] [2 1] [3 0] [2 0] [2 1] [3 0] topB(i,x,N2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,N2(C(y))) [2 0] [2 0] [1 0] [2 0] [2 0] [1 0] topA(i,T1(x),y) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topA(i,T1(x),y) [2 0] [2 1] [3 0] [2 0] [2 1] [3 0] topB(i,x,T2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,T2(y)) [2 0] [2 1] [3 0] [2 0] [2 1] [3 0] topB(i,x,S2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,S2(D(y))) problem: strict: topB(i,N1(x),y) -> topA(1(),T1(x),y) topA(i,x,N2(y)) -> topB(0(),x,T2(y)) topA(i,x,S2(y)) -> topB(i,x,N2(y)) topA(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topA(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) weak: topA(i,N1(x),y) -> topA(1(),T1(x),y) topB(i,x,N2(y)) -> topB(0(),x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,N2(y)) topB(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) topA(i,N1(x),y) -> topA(i,N1(C(x)),y) topB(i,x,N2(y)) -> topB(i,x,N2(C(y))) topA(i,T1(x),y) -> topA(i,T1(x),y) topB(i,x,T2(y)) -> topB(i,x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,S2(D(y))) Matrix Interpretation Processor: dim=2 interpretation: [1 0] [2 1] [2 0] [topA](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [0 0]x2, [1 0] [2 0] [2 0] [topB](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [0 0]x2, [1 0] [T1](x0) = [0 0]x0, [N2](x0) = x0, [1 0] [0] [C](x0) = [0 0]x0 + [1], [1 0] [0] [N1](x0) = [0 0]x0 + [2], [1 0] [T2](x0) = [0 0]x0, [1 0] [0] [D](x0) = [0 2]x0 + [2], [S2](x0) = x0, [0] [0] = [0], [0] [1] = [0] orientation: [1 0] [2 0] [2 0] [2 0] [2 0] topB(i,N1(x),y) = [0 0]i + [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topA(1(),T1(x),y) [1 0] [2 1] [2 0] [2 0] [2 0] topA(i,x,N2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(0(),x,T2(y)) [1 0] [2 1] [2 0] [1 0] [2 0] [2 0] topA(i,x,S2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,N2(y)) [1 0] [2 0] [2 0] [2] [1 0] [2 0] [2 0] topA(i,N1(x),T2(y)) = [0 0]i + [0 0]x + [0 0]y + [0] >= [0 0]i + [0 0]x + [0 0]y = topB(i,N1(x),S2(y)) [2 0] [2 0] [2 0] [2 0] topA(1(),T1(x),T2(y)) = [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(1(),T1(x),S2(y)) [1 0] [2 0] [2 0] [2] [2 0] [2 0] topA(i,N1(x),y) = [0 0]i + [0 0]x + [0 0]y + [0] >= [0 0]x + [0 0]y = topA(1(),T1(x),y) [1 0] [2 0] [2 0] [2 0] [2 0] topB(i,x,N2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(0(),x,T2(y)) [1 0] [2 0] [2 0] [1 0] [2 0] [2 0] topB(i,x,S2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,N2(y)) [1 0] [2 0] [2 0] [1 0] [2 0] [2 0] topB(i,N1(x),T2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,N1(x),S2(y)) [2 0] [2 0] [2 0] [2 0] topB(1(),T1(x),T2(y)) = [0 0]x + [0 0]y >= [0 0]x + [0 0]y = topB(1(),T1(x),S2(y)) [1 0] [2 0] [2 0] [2] [1 0] [2 0] [2 0] [2] topA(i,N1(x),y) = [0 0]i + [0 0]x + [0 0]y + [0] >= [0 0]i + [0 0]x + [0 0]y + [0] = topA(i,N1(C(x)),y) [1 0] [2 0] [2 0] [1 0] [2 0] [2 0] topB(i,x,N2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,N2(C(y))) [1 0] [2 0] [2 0] [1 0] [2 0] [2 0] topA(i,T1(x),y) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topA(i,T1(x),y) [1 0] [2 0] [2 0] [1 0] [2 0] [2 0] topB(i,x,T2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,T2(y)) [1 0] [2 0] [2 0] [1 0] [2 0] [2 0] topB(i,x,S2(y)) = [0 0]i + [0 0]x + [0 0]y >= [0 0]i + [0 0]x + [0 0]y = topB(i,x,S2(D(y))) problem: strict: topB(i,N1(x),y) -> topA(1(),T1(x),y) topA(i,x,N2(y)) -> topB(0(),x,T2(y)) topA(i,x,S2(y)) -> topB(i,x,N2(y)) topA(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) weak: topB(i,x,N2(y)) -> topB(0(),x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,N2(y)) topB(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) topA(i,N1(x),y) -> topA(i,N1(C(x)),y) topB(i,x,N2(y)) -> topB(i,x,N2(C(y))) topA(i,T1(x),y) -> topA(i,T1(x),y) topB(i,x,T2(y)) -> topB(i,x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,S2(D(y))) Matrix Interpretation Processor: dim=2 interpretation: [2 0] [1 0] [2 2] [topA](x0, x1, x2) = [0 0]x0 + [1 1]x1 + [0 0]x2, [1 0] [1 0] [2 2] [topB](x0, x1, x2) = [0 0]x0 + [1 0]x1 + [0 0]x2, [2 0] [T1](x0) = [0 0]x0, [1 0] [0] [N2](x0) = [0 0]x0 + [1], [1 0] [C](x0) = [0 0]x0, [2 0] [1] [N1](x0) = [0 0]x0 + [0], [1 0] [0] [T2](x0) = [0 0]x0 + [1], [1 0] [D](x0) = [0 0]x0, [1 0] [0] [S2](x0) = [0 0]x0 + [1], [0] [0] = [0], [0] [1] = [0] orientation: [1 0] [2 0] [2 2] [1] [2 0] [2 2] topB(i,N1(x),y) = [0 0]i + [2 0]x + [0 0]y + [1] >= [2 0]x + [0 0]y = topA(1(),T1(x),y) [2 0] [1 0] [2 0] [2] [1 0] [2 0] [2] topA(i,x,N2(y)) = [0 0]i + [1 1]x + [0 0]y + [0] >= [1 0]x + [0 0]y + [0] = topB(0(),x,T2(y)) [2 0] [1 0] [2 0] [2] [1 0] [1 0] [2 0] [2] topA(i,x,S2(y)) = [0 0]i + [1 1]x + [0 0]y + [0] >= [0 0]i + [1 0]x + [0 0]y + [0] = topB(i,x,N2(y)) [2 0] [2 0] [2] [2 0] [2 0] [2] topA(1(),T1(x),T2(y)) = [2 0]x + [0 0]y + [0] >= [2 0]x + [0 0]y + [0] = topB(1(),T1(x),S2(y)) [1 0] [1 0] [2 0] [2] [1 0] [2 0] [2] topB(i,x,N2(y)) = [0 0]i + [1 0]x + [0 0]y + [0] >= [1 0]x + [0 0]y + [0] = topB(0(),x,T2(y)) [1 0] [1 0] [2 0] [2] [1 0] [1 0] [2 0] [2] topB(i,x,S2(y)) = [0 0]i + [1 0]x + [0 0]y + [0] >= [0 0]i + [1 0]x + [0 0]y + [0] = topB(i,x,N2(y)) [1 0] [2 0] [2 0] [3] [1 0] [2 0] [2 0] [3] topB(i,N1(x),T2(y)) = [0 0]i + [2 0]x + [0 0]y + [1] >= [0 0]i + [2 0]x + [0 0]y + [1] = topB(i,N1(x),S2(y)) [2 0] [2 0] [2] [2 0] [2 0] [2] topB(1(),T1(x),T2(y)) = [2 0]x + [0 0]y + [0] >= [2 0]x + [0 0]y + [0] = topB(1(),T1(x),S2(y)) [2 0] [2 0] [2 2] [1] [2 0] [2 0] [2 2] [1] topA(i,N1(x),y) = [0 0]i + [2 0]x + [0 0]y + [1] >= [0 0]i + [2 0]x + [0 0]y + [1] = topA(i,N1(C(x)),y) [1 0] [1 0] [2 0] [2] [1 0] [1 0] [2 0] [2] topB(i,x,N2(y)) = [0 0]i + [1 0]x + [0 0]y + [0] >= [0 0]i + [1 0]x + [0 0]y + [0] = topB(i,x,N2(C(y))) [2 0] [2 0] [2 2] [2 0] [2 0] [2 2] topA(i,T1(x),y) = [0 0]i + [2 0]x + [0 0]y >= [0 0]i + [2 0]x + [0 0]y = topA(i,T1(x),y) [1 0] [1 0] [2 0] [2] [1 0] [1 0] [2 0] [2] topB(i,x,T2(y)) = [0 0]i + [1 0]x + [0 0]y + [0] >= [0 0]i + [1 0]x + [0 0]y + [0] = topB(i,x,T2(y)) [1 0] [1 0] [2 0] [2] [1 0] [1 0] [2 0] [2] topB(i,x,S2(y)) = [0 0]i + [1 0]x + [0 0]y + [0] >= [0 0]i + [1 0]x + [0 0]y + [0] = topB(i,x,S2(D(y))) problem: strict: topA(i,x,N2(y)) -> topB(0(),x,T2(y)) topA(i,x,S2(y)) -> topB(i,x,N2(y)) topA(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) weak: topB(i,x,N2(y)) -> topB(0(),x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,N2(y)) topB(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) topA(i,N1(x),y) -> topA(i,N1(C(x)),y) topB(i,x,N2(y)) -> topB(i,x,N2(C(y))) topA(i,T1(x),y) -> topA(i,T1(x),y) topB(i,x,T2(y)) -> topB(i,x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,S2(D(y))) Bounds Processor: bound: 1 enrichment: match-rt automaton: final states: {1} transitions: N10(1) -> 1* S21(1) -> 7* S21(19) -> 7* S21(34) -> 7* N20(1) -> 1* topA0(1,1,1) -> 1* C1(34) -> 1* C1(1) -> 19* C1(19) -> 19* N21(34) -> 7* N21(1) -> 7* N21(19) -> 7* 11() -> 1* 00() -> 1* N11(1) -> 1* N11(19) -> 20* topB0(1,1,1) -> 1* C0(1) -> 1* 01() -> 1* T20(1) -> 1* D1(19) -> 1* D1(34) -> 1* D1(1) -> 34* T21(1) -> 7* T21(34) -> 7* T21(19) -> 7* topB1(1,20,7) -> 1* topB1(1,1,7) -> 1* T11(1) -> 1* S20(1) -> 1* topA1(1,1,1) -> 1* topA1(1,20,1) -> 1* T10(1) -> 1* 10() -> 1* D0(1) -> 1* problem: strict: topA(i,x,N2(y)) -> topB(0(),x,T2(y)) topA(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) weak: topB(i,x,N2(y)) -> topB(0(),x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,N2(y)) topB(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) topA(i,N1(x),y) -> topA(i,N1(C(x)),y) topB(i,x,N2(y)) -> topB(i,x,N2(C(y))) topA(i,T1(x),y) -> topA(i,T1(x),y) topB(i,x,T2(y)) -> topB(i,x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,S2(D(y))) Bounds Processor: bound: 1 enrichment: match-rt automaton: final states: {2} transitions: N10(2) -> 2* S21(26) -> 21* S21(19) -> 10* S21(2) -> 10* N20(2) -> 2* topA0(2,2,2) -> 2* C1(19) -> 19* C1(26) -> 19* C1(2) -> 19* N21(26) -> 21* N21(2) -> 10* N21(19) -> 21* 11() -> 12* 00() -> 2* N11(19) -> 20* N11(2) -> 20* topB0(2,2,2) -> 2* C0(2) -> 2* 01() -> 32* T20(2) -> 2* D1(19) -> 2* D1(26) -> 26* D1(2) -> 26* T21(26) -> 34* T21(2) -> 31* T21(19) -> 34* topB1(32,20,10) -> 2* topB1(12,11,21) -> 2* topB1(2,2,21) -> 2* topB1(32,2,34) -> 2* topB1(32,20,31) -> 2* topB1(32,20,21) -> 2* topB1(32,20,34) -> 2* topB1(32,11,34) -> 2* topB1(32,11,31) -> 2* topB1(12,11,10) -> 2* T11(2) -> 11* S20(2) -> 2* topA1(2,20,2) -> 2* T10(2) -> 2* 10() -> 2* D0(2) -> 2* problem: strict: topA(i,x,N2(y)) -> topB(0(),x,T2(y)) weak: topB(i,x,N2(y)) -> topB(0(),x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,N2(y)) topB(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) topA(i,N1(x),y) -> topA(i,N1(C(x)),y) topB(i,x,N2(y)) -> topB(i,x,N2(C(y))) topA(i,T1(x),y) -> topA(i,T1(x),y) topB(i,x,T2(y)) -> topB(i,x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,S2(D(y))) Bounds Processor: bound: 1 enrichment: match-rt automaton: final states: {2} transitions: N10(2) -> 2* S21(11) -> 5* S21(2) -> 5* S21(15) -> 14* N20(2) -> 2* topA0(2,2,2) -> 2* C1(11) -> 11* C1(15) -> 2* C1(2) -> 11* N21(15) -> 14* N21(11) -> 14* N21(2) -> 5* 11() -> 2* 00() -> 2* N11(11) -> 12* N11(2) -> 2* C0(2) -> 2* topB0(2,2,2) -> 2* 01() -> 6* T20(2) -> 2* D1(2) -> 15* D1(11) -> 2* D1(15) -> 2* topB1(2,2,5) -> 2* topB1(6,12,14) -> 2* topB1(6,2,14) -> 2* topB1(6,2,5) -> 2* topB1(2,2,14) -> 2* topB1(6,12,5) -> 2* T21(11) -> 5* T21(2) -> 5* T21(15) -> 5* T11(2) -> 2* S20(2) -> 2* topA1(2,2,2) -> 2* topA1(2,12,2) -> 2* 10() -> 2* T10(2) -> 2* D0(2) -> 2* problem: strict: weak: topB(i,x,N2(y)) -> topB(0(),x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,N2(y)) topB(i,N1(x),T2(y)) -> topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) -> topB(1(),T1(x),S2(y)) topA(i,N1(x),y) -> topA(i,N1(C(x)),y) topB(i,x,N2(y)) -> topB(i,x,N2(C(y))) topA(i,T1(x),y) -> topA(i,T1(x),y) topB(i,x,T2(y)) -> topB(i,x,T2(y)) topB(i,x,S2(y)) -> topB(i,x,S2(D(y))) Qed