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=1 interpretation: [topA](x0, x1, x2) = 2x0 + 8x1 + 4x2, [S1](x0) = x0 + 2, [topB](x0, x1, x2) = 2x0 + 8x1 + 4x2, [T1](x0) = x0, [N2](x0) = 4x0, [C](x0) = x0, [N1](x0) = x0, [T2](x0) = 4x0, [D](x0) = x0, [S2](x0) = 4x0, [0] = 0, [1] = 0 orientation: topB(i,N1(x),y) = 2i + 8x + 4y >= 8x + 4y = topA(1(),T1(x),y) topA(i,x,N2(y)) = 2i + 8x + 16y >= 8x + 16y = topB(0(),x,T2(y)) topB(i,S1(x),y) = 2i + 8x + 4y + 16 >= 2i + 8x + 4y = topA(i,N1(x),y) topA(i,x,S2(y)) = 2i + 8x + 16y >= 2i + 8x + 16y = topB(i,x,N2(y)) topA(i,N1(x),T2(y)) = 2i + 8x + 16y >= 2i + 8x + 16y = topB(i,N1(x),S2(y)) topA(1(),T1(x),T2(y)) = 8x + 16y >= 8x + 16y = topB(1(),T1(x),S2(y)) topA(i,N1(x),y) = 2i + 8x + 4y >= 8x + 4y = topA(1(),T1(x),y) topB(i,x,N2(y)) = 2i + 8x + 16y >= 8x + 16y = topB(0(),x,T2(y)) topA(i,S1(x),y) = 2i + 8x + 4y + 16 >= 2i + 8x + 4y = topA(i,N1(x),y) topB(i,x,S2(y)) = 2i + 8x + 16y >= 2i + 8x + 16y = topB(i,x,N2(y)) topB(i,N1(x),T2(y)) = 2i + 8x + 16y >= 2i + 8x + 16y = topB(i,N1(x),S2(y)) topB(1(),T1(x),T2(y)) = 8x + 16y >= 8x + 16y = topB(1(),T1(x),S2(y)) topA(i,N1(x),y) = 2i + 8x + 4y >= 2i + 8x + 4y = topA(i,N1(C(x)),y) topB(i,x,N2(y)) = 2i + 8x + 16y >= 2i + 8x + 16y = topB(i,x,N2(C(y))) topA(i,T1(x),y) = 2i + 8x + 4y >= 2i + 8x + 4y = topA(i,T1(x),y) topB(i,x,T2(y)) = 2i + 8x + 16y >= 2i + 8x + 16y = topB(i,x,T2(y)) topB(i,x,S2(y)) = 2i + 8x + 16y >= 2i + 8x + 16y = 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))) Matrix Interpretation Processor: dim=2 interpretation: [2 1] [2 0] [2 1] [topA](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [1 0]x2, [2 2] [2 0] [2 0] [topB](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [0 0]x2, [1 1] [T1](x0) = [0 0]x0, [1 0] [0] [N2](x0) = [0 0]x0 + [2], [1 0] [0] [C](x0) = [0 2]x0 + [1], [1 0] [N1](x0) = [2 1]x0, [1 0] [0] [T2](x0) = [0 2]x0 + [1], [0] [D](x0) = x0 + [1], [1 0] [S2](x0) = [0 2]x0, [0] [0] = [0], [0] [1] = [1] orientation: [2 1] [2 0] [2 0] [2] [2 0] [2 0] topA(i,x,N2(y)) = [0 0]i + [0 0]x + [1 0]y + [0] >= [0 0]x + [0 0]y = topB(0(),x,T2(y)) [2 2] [2 2] [2] [2 2] [2 0] [2] topA(1(),T1(x),T2(y)) = [0 0]x + [1 0]y + [0] >= [0 0]x + [0 0]y + [0] = topB(1(),T1(x),S2(y)) [2 2] [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)) [2 2] [2 0] [2 0] [2 2] [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)) [2 2] [2 0] [2 0] [2 2] [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 2] [2 0] [2] [2 2] [2 0] [2] topB(1(),T1(x),T2(y)) = [0 0]x + [0 0]y + [0] >= [0 0]x + [0 0]y + [0] = topB(1(),T1(x),S2(y)) [2 1] [2 0] [2 1] [2 1] [2 0] [2 1] topA(i,N1(x),y) = [0 0]i + [0 0]x + [1 0]y >= [0 0]i + [0 0]x + [1 0]y = topA(i,N1(C(x)),y) [2 2] [2 0] [2 0] [2 2] [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))) [2 1] [2 2] [2 1] [2 1] [2 2] [2 1] topA(i,T1(x),y) = [0 0]i + [0 0]x + [1 0]y >= [0 0]i + [0 0]x + [1 0]y = topA(i,T1(x),y) [2 2] [2 0] [2 0] [2 2] [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)) [2 2] [2 0] [2 0] [2 2] [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: 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) -> 3* S21(15) -> 14* S21(9) -> 20* N20(1) -> 1* topA0(1,1,1) -> 1* C1(15) -> 9* C1(9) -> 9* C1(1) -> 9* N21(9) -> 14* N21(15) -> 14* N21(1) -> 3* 11() -> 5* 00() -> 1* N11(1) -> 21* N11(9) -> 10* C0(1) -> 1* topB0(1,1,1) -> 1* 01() -> 18* T20(1) -> 1* D1(15) -> 15* D1(1) -> 15* D1(9) -> 1* T21(1) -> 17* T21(9) -> 17* T21(15) -> 17* topB1(18,21,17) -> 1* topB1(5,4,3) -> 1* topB1(5,4,14) -> 1* topB1(18,21,14) -> 1* topB1(18,4,17) -> 1* topB1(18,1,17) -> 1* topB1(1,1,14) -> 1* topB1(18,21,20) -> 1* topB1(18,21,3) -> 1* T11(1) -> 4* S20(1) -> 1* topA1(1,10,1) -> 1* 10() -> 1* T10(1) -> 1* D0(1) -> 1* 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