YES Problem: strict: topB(i,N1(),y) -> topA(1(),T1(),y) topA(i,x,N2()) -> topB(0(),x,T2()) topB(i,S1(),y) -> topA(i,N1(),y) topA(i,x,S2()) -> topB(i,x,N2()) topA(i,N1(),T2()) -> topB(i,N1(),S2()) topA(1(),T1(),T2()) -> topB(1(),T1(),S2()) weak: topA(i,N1(),y) -> topA(1(),T1(),y) topB(i,x,N2()) -> topB(0(),x,T2()) topA(i,S1(),y) -> topA(i,N1(),y) topB(i,x,S2()) -> topB(i,x,N2()) topB(i,N1(),T2()) -> topB(i,N1(),S2()) topB(1(),T1(),T2()) -> topB(1(),T1(),S2()) Proof: Matrix Interpretation Processor: dim=2 interpretation: [1 0] [2 2] [1 0] [topA](x0, x1, x2) = [0 0]x0 + [1 2]x1 + [0 0]x2, [0] [S1] = [1], [1 0] [1 2] [2 0] [topB](x0, x1, x2) = [0 0]x0 + [0 2]x1 + [1 0]x2, [0] [T1] = [0], [0] [N2] = [0], [1] [N1] = [0], [0] [T2] = [0], [0] [S2] = [0], [0] [0] = [0], [0] [1] = [0] orientation: [1 0] [2 0] [1] [1 0] topB(i,N1(),y) = [0 0]i + [1 0]y + [0] >= [0 0]y = topA(1(),T1(),y) [1 0] [2 2] [1 2] topA(i,x,N2()) = [0 0]i + [1 2]x >= [0 2]x = topB(0(),x,T2()) [1 0] [2 0] [2] [1 0] [1 0] [2] topB(i,S1(),y) = [0 0]i + [1 0]y + [2] >= [0 0]i + [0 0]y + [1] = topA(i,N1(),y) [1 0] [2 2] [1 0] [1 2] topA(i,x,S2()) = [0 0]i + [1 2]x >= [0 0]i + [0 2]x = topB(i,x,N2()) [1 0] [2] [1 0] [1] topA(i,N1(),T2()) = [0 0]i + [1] >= [0 0]i + [0] = topB(i,N1(),S2()) [0] [0] topA(1(),T1(),T2()) = [0] >= [0] = topB(1(),T1(),S2()) [1 0] [1 0] [2] [1 0] topA(i,N1(),y) = [0 0]i + [0 0]y + [1] >= [0 0]y = topA(1(),T1(),y) [1 0] [1 2] [1 2] topB(i,x,N2()) = [0 0]i + [0 2]x >= [0 2]x = topB(0(),x,T2()) [1 0] [1 0] [2] [1 0] [1 0] [2] topA(i,S1(),y) = [0 0]i + [0 0]y + [2] >= [0 0]i + [0 0]y + [1] = topA(i,N1(),y) [1 0] [1 2] [1 0] [1 2] topB(i,x,S2()) = [0 0]i + [0 2]x >= [0 0]i + [0 2]x = topB(i,x,N2()) [1 0] [1] [1 0] [1] topB(i,N1(),T2()) = [0 0]i + [0] >= [0 0]i + [0] = topB(i,N1(),S2()) [0] [0] topB(1(),T1(),T2()) = [0] >= [0] = topB(1(),T1(),S2()) problem: strict: topA(i,x,N2()) -> topB(0(),x,T2()) topB(i,S1(),y) -> topA(i,N1(),y) topA(i,x,S2()) -> topB(i,x,N2()) topA(1(),T1(),T2()) -> topB(1(),T1(),S2()) weak: topB(i,x,N2()) -> topB(0(),x,T2()) topA(i,S1(),y) -> topA(i,N1(),y) topB(i,x,S2()) -> topB(i,x,N2()) topB(i,N1(),T2()) -> topB(i,N1(),S2()) topB(1(),T1(),T2()) -> topB(1(),T1(),S2()) Matrix Interpretation Processor: dim=2 interpretation: [2 0] [3 2] [1 2] [1] [topA](x0, x1, x2) = [0 0]x0 + [1 0]x1 + [0 0]x2 + [0], [0] [S1] = [1], [2 0] [2 2] [2 3] [topB](x0, x1, x2) = [0 0]x0 + [0 0]x1 + [0 0]x2, [0] [T1] = [0], [0] [N2] = [1], [0] [N1] = [0], [0] [T2] = [1], [0] [S2] = [1], [0] [0] = [0], [0] [1] = [0] orientation: [2 0] [3 2] [3] [2 2] [3] topA(i,x,N2()) = [0 0]i + [1 0]x + [0] >= [0 0]x + [0] = topB(0(),x,T2()) [2 0] [2 3] [2] [2 0] [1 2] [1] topB(i,S1(),y) = [0 0]i + [0 0]y + [0] >= [0 0]i + [0 0]y + [0] = topA(i,N1(),y) [2 0] [3 2] [3] [2 0] [2 2] [3] topA(i,x,S2()) = [0 0]i + [1 0]x + [0] >= [0 0]i + [0 0]x + [0] = topB(i,x,N2()) [3] [3] topA(1(),T1(),T2()) = [0] >= [0] = topB(1(),T1(),S2()) [2 0] [2 2] [3] [2 2] [3] topB(i,x,N2()) = [0 0]i + [0 0]x + [0] >= [0 0]x + [0] = topB(0(),x,T2()) [2 0] [1 2] [3] [2 0] [1 2] [1] topA(i,S1(),y) = [0 0]i + [0 0]y + [0] >= [0 0]i + [0 0]y + [0] = topA(i,N1(),y) [2 0] [2 2] [3] [2 0] [2 2] [3] topB(i,x,S2()) = [0 0]i + [0 0]x + [0] >= [0 0]i + [0 0]x + [0] = topB(i,x,N2()) [2 0] [3] [2 0] [3] topB(i,N1(),T2()) = [0 0]i + [0] >= [0 0]i + [0] = topB(i,N1(),S2()) [3] [3] topB(1(),T1(),T2()) = [0] >= [0] = topB(1(),T1(),S2()) problem: strict: topA(i,x,N2()) -> topB(0(),x,T2()) topA(i,x,S2()) -> topB(i,x,N2()) topA(1(),T1(),T2()) -> topB(1(),T1(),S2()) weak: topB(i,x,N2()) -> topB(0(),x,T2()) topB(i,x,S2()) -> topB(i,x,N2()) topB(i,N1(),T2()) -> topB(i,N1(),S2()) topB(1(),T1(),T2()) -> topB(1(),T1(),S2()) Matrix Interpretation Processor: dim=2 interpretation: [1 1] [2 2] [0] [topA](x0, x1, x2) = [2 0]x0 + [2 0]x1 + x2 + [1], [1 0] [2 0] [1 1] [topB](x0, x1, x2) = [1 0]x0 + [0 0]x1 + [0 0]x2, [0] [T1] = [1], [2] [N2] = [0], [0] [N1] = [0], [0] [T2] = [2], [2] [S2] = [0], [0] [0] = [0], [0] [1] = [1] orientation: [1 1] [2 2] [2] [2 0] [2] topA(i,x,N2()) = [2 0]i + [2 0]x + [1] >= [0 0]x + [0] = topB(0(),x,T2()) [1 1] [2 2] [2] [1 0] [2 0] [2] topA(i,x,S2()) = [2 0]i + [2 0]x + [1] >= [1 0]i + [0 0]x + [0] = topB(i,x,N2()) [3] [2] topA(1(),T1(),T2()) = [3] >= [0] = topB(1(),T1(),S2()) [1 0] [2 0] [2] [2 0] [2] topB(i,x,N2()) = [1 0]i + [0 0]x + [0] >= [0 0]x + [0] = topB(0(),x,T2()) [1 0] [2 0] [2] [1 0] [2 0] [2] topB(i,x,S2()) = [1 0]i + [0 0]x + [0] >= [1 0]i + [0 0]x + [0] = topB(i,x,N2()) [1 0] [2] [1 0] [2] topB(i,N1(),T2()) = [1 0]i + [0] >= [1 0]i + [0] = topB(i,N1(),S2()) [2] [2] topB(1(),T1(),T2()) = [0] >= [0] = topB(1(),T1(),S2()) problem: strict: topA(i,x,N2()) -> topB(0(),x,T2()) topA(i,x,S2()) -> topB(i,x,N2()) weak: topB(i,x,N2()) -> topB(0(),x,T2()) topB(i,x,S2()) -> topB(i,x,N2()) topB(i,N1(),T2()) -> topB(i,N1(),S2()) topB(1(),T1(),T2()) -> topB(1(),T1(),S2()) Matrix Interpretation Processor: dim=5 interpretation: [1 0 0 1 1] [1 0 1 0 1] [1 1 0 0 0] [0] [0 0 0 0 0] [0 0 0 1 0] [0 1 0 0 0] [0] [topA](x0, x1, x2) = [1 1 0 0 0]x0 + [1 1 0 1 0]x1 + [0 1 0 0 0]x2 + [1] [0 1 0 0 1] [0 1 0 1 1] [0 0 0 0 0] [0] [1 0 0 0 0] [0 1 1 1 0] [0 0 0 0 0] [0], [1 0 0 1 1] [1 0 1 0 0] [1 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [topB](x0, x1, x2) = [0 1 0 0 0]x0 + [0 1 0 1 0]x1 + [0 0 0 0 0]x2 [0 0 0 0 0] [0 1 0 1 1] [0 0 0 0 0] [0 0 0 0 0] [0 0 1 1 0] [0 0 0 0 0] , [0] [1] [T1] = [1] [1] [1], [0] [0] [N2] = [0] [0] [0], [0] [0] [N1] = [0] [1] [1], [0] [0] [T2] = [0] [0] [0], [0] [1] [S2] = [0] [0] [0], [0] [0] [0] = [0] [0] [0], [0] [1] [1] = [0] [1] [1] orientation: [1 0 0 1 1] [1 0 1 0 1] [0] [1 0 1 0 0] [0 0 0 0 0] [0 0 0 1 0] [0] [0 0 0 0 0] topA(i,x,N2()) = [1 1 0 0 0]i + [1 1 0 1 0]x + [1] >= [0 1 0 1 0]x = topB(0(),x,T2()) [0 1 0 0 1] [0 1 0 1 1] [0] [0 1 0 1 1] [1 0 0 0 0] [0 1 1 1 0] [0] [0 0 1 1 0] [1 0 0 1 1] [1 0 1 0 1] [1] [1 0 0 1 1] [1 0 1 0 0] [0 0 0 0 0] [0 0 0 1 0] [1] [0 0 0 0 0] [0 0 0 0 0] topA(i,x,S2()) = [1 1 0 0 0]i + [1 1 0 1 0]x + [2] >= [0 1 0 0 0]i + [0 1 0 1 0]x = topB(i,x,N2()) [0 1 0 0 1] [0 1 0 1 1] [0] [0 0 0 0 0] [0 1 0 1 1] [1 0 0 0 0] [0 1 1 1 0] [0] [0 0 0 0 0] [0 0 1 1 0] [1 0 0 1 1] [1 0 1 0 0] [1 0 1 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] topB(i,x,N2()) = [0 1 0 0 0]i + [0 1 0 1 0]x >= [0 1 0 1 0]x = topB(0(),x,T2()) [0 0 0 0 0] [0 1 0 1 1] [0 1 0 1 1] [0 0 0 0 0] [0 0 1 1 0] [0 0 1 1 0] [1 0 0 1 1] [1 0 1 0 0] [1 0 0 1 1] [1 0 1 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] topB(i,x,S2()) = [0 1 0 0 0]i + [0 1 0 1 0]x >= [0 1 0 0 0]i + [0 1 0 1 0]x = topB(i,x,N2()) [0 0 0 0 0] [0 1 0 1 1] [0 0 0 0 0] [0 1 0 1 1] [0 0 0 0 0] [0 0 1 1 0] [0 0 0 0 0] [0 0 1 1 0] [1 0 0 1 1] [0] [1 0 0 1 1] [0] [0 0 0 0 0] [0] [0 0 0 0 0] [0] topB(i,N1(),T2()) = [0 1 0 0 0]i + [1] >= [0 1 0 0 0]i + [1] = topB(i,N1(),S2()) [0 0 0 0 0] [2] [0 0 0 0 0] [2] [0 0 0 0 0] [1] [0 0 0 0 0] [1] [3] [3] [0] [0] topB(1(),T1(),T2()) = [3] >= [3] = topB(1(),T1(),S2()) [3] [3] [2] [2] problem: strict: topA(i,x,N2()) -> topB(0(),x,T2()) weak: topB(i,x,N2()) -> topB(0(),x,T2()) topB(i,x,S2()) -> topB(i,x,N2()) topB(i,N1(),T2()) -> topB(i,N1(),S2()) topB(1(),T1(),T2()) -> topB(1(),T1(),S2()) Bounds Processor: bound: 1 enrichment: match-rt automaton: final states: {1} transitions: 01() -> 4* 00() -> 1* topB0(1,1,1) -> 1* N20() -> 1* topA0(1,1,1) -> 1* S20() -> 1* T21() -> 3* T20() -> 1* N21() -> 7* N10() -> 1* S21() -> 7* 10() -> 1* topB1(4,8,7) -> 1* topB1(4,1,3) -> 1* topB1(4,8,3) -> 1* T10() -> 1* N11() -> 8* problem: strict: weak: topB(i,x,N2()) -> topB(0(),x,T2()) topB(i,x,S2()) -> topB(i,x,N2()) topB(i,N1(),T2()) -> topB(i,N1(),S2()) topB(1(),T1(),T2()) -> topB(1(),T1(),S2()) Qed