YES Problem: f(x,y,w,w,a()) -> g1(x,x,y,w) f(x,y,w,a(),a()) -> g1(y,x,x,w) f(x,y,a(),a(),w) -> g2(x,y,y,w) f(x,y,a(),w,w) -> g2(y,y,x,w) g1(x,x,y,a()) -> h(x,y) g1(y,x,x,a()) -> h(x,y) g2(x,y,y,a()) -> h(x,y) g2(y,y,x,a()) -> h(x,y) h(x,x) -> x Proof: DP Processor: DPs: f#(x,y,w,w,a()) -> g1#(x,x,y,w) f#(x,y,w,a(),a()) -> g1#(y,x,x,w) f#(x,y,a(),a(),w) -> g2#(x,y,y,w) f#(x,y,a(),w,w) -> g2#(y,y,x,w) g1#(x,x,y,a()) -> h#(x,y) g1#(y,x,x,a()) -> h#(x,y) g2#(x,y,y,a()) -> h#(x,y) g2#(y,y,x,a()) -> h#(x,y) TRS: f(x,y,w,w,a()) -> g1(x,x,y,w) f(x,y,w,a(),a()) -> g1(y,x,x,w) f(x,y,a(),a(),w) -> g2(x,y,y,w) f(x,y,a(),w,w) -> g2(y,y,x,w) g1(x,x,y,a()) -> h(x,y) g1(y,x,x,a()) -> h(x,y) g2(x,y,y,a()) -> h(x,y) g2(y,y,x,a()) -> h(x,y) h(x,x) -> x Matrix Interpretation Processor: dim=3 interpretation: [h#](x0, x1) = [0], [g2#](x0, x1, x2, x3) = [1 0 0]x0 + [1 0 0]x2 + [1], [g1#](x0, x1, x2, x3) = [1 0 0]x3, [f#](x0, x1, x2, x3, x4) = [1 1 0]x0 + [1 0 0]x1 + [1 0 0]x2 + [0 1 0]x3 + [0 1 1]x4 + [1], [0 0 0] [1 0 0] [1] [h](x0, x1) = [0 1 0]x0 + [0 0 0]x1 + [0] [1 0 1] [1 0 0] [0], [1 0 0] [1 0 0] [1] [g2](x0, x1, x2, x3) = [0 1 0]x0 + [0 1 0]x2 + [0] [1 0 1] [1 0 1] [1], [1 0 0] [1 0 0] [0 1 0] [1] [g1](x0, x1, x2, x3) = [0 1 0]x0 + [0 1 0]x2 + [0 0 0]x3 + [1] [1 0 1] [1 0 1] [0 0 0] [1], [1 0 0] [1 0 0] [0 1 0] [1] [f](x0, x1, x2, x3, x4) = [0 1 0]x0 + [0 1 0]x1 + [0 0 0]x2 + [1] [1 0 1] [1 0 1] [0 0 0] [1], [1] [a] = [0] [0] orientation: f#(x,y,w,w,a()) = [1 1 0]w + [1 1 0]x + [1 0 0]y + [1] >= [1 0 0]w = g1#(x,x,y,w) f#(x,y,w,a(),a()) = [1 0 0]w + [1 1 0]x + [1 0 0]y + [1] >= [1 0 0]w = g1#(y,x,x,w) f#(x,y,a(),a(),w) = [0 1 1]w + [1 1 0]x + [1 0 0]y + [2] >= [1 0 0]x + [1 0 0]y + [1] = g2#(x,y,y,w) f#(x,y,a(),w,w) = [0 2 1]w + [1 1 0]x + [1 0 0]y + [2] >= [1 0 0]x + [1 0 0]y + [1] = g2#(y,y,x,w) g1#(x,x,y,a()) = [1] >= [0] = h#(x,y) g1#(y,x,x,a()) = [1] >= [0] = h#(x,y) g2#(x,y,y,a()) = [1 0 0]x + [1 0 0]y + [1] >= [0] = h#(x,y) g2#(y,y,x,a()) = [1 0 0]x + [1 0 0]y + [1] >= [0] = h#(x,y) [0 1 0] [1 0 0] [1 0 0] [1] [0 1 0] [1 0 0] [1 0 0] [1] f(x,y,w,w,a()) = [0 0 0]w + [0 1 0]x + [0 1 0]y + [1] >= [0 0 0]w + [0 1 0]x + [0 1 0]y + [1] = g1(x,x,y,w) [0 0 0] [1 0 1] [1 0 1] [1] [0 0 0] [1 0 1] [1 0 1] [1] [0 1 0] [1 0 0] [1 0 0] [1] [0 1 0] [1 0 0] [1 0 0] [1] f(x,y,w,a(),a()) = [0 0 0]w + [0 1 0]x + [0 1 0]y + [1] >= [0 0 0]w + [0 1 0]x + [0 1 0]y + [1] = g1(y,x,x,w) [0 0 0] [1 0 1] [1 0 1] [1] [0 0 0] [1 0 1] [1 0 1] [1] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1] f(x,y,a(),a(),w) = [0 1 0]x + [0 1 0]y + [1] >= [0 1 0]x + [0 1 0]y + [0] = g2(x,y,y,w) [1 0 1] [1 0 1] [1] [1 0 1] [1 0 1] [1] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1] f(x,y,a(),w,w) = [0 1 0]x + [0 1 0]y + [1] >= [0 1 0]x + [0 1 0]y + [0] = g2(y,y,x,w) [1 0 1] [1 0 1] [1] [1 0 1] [1 0 1] [1] [1 0 0] [1 0 0] [1] [0 0 0] [1 0 0] [1] g1(x,x,y,a()) = [0 1 0]x + [0 1 0]y + [1] >= [0 1 0]x + [0 0 0]y + [0] = h(x,y) [1 0 1] [1 0 1] [1] [1 0 1] [1 0 0] [0] [1 0 0] [1 0 0] [1] [0 0 0] [1 0 0] [1] g1(y,x,x,a()) = [0 1 0]x + [0 1 0]y + [1] >= [0 1 0]x + [0 0 0]y + [0] = h(x,y) [1 0 1] [1 0 1] [1] [1 0 1] [1 0 0] [0] [1 0 0] [1 0 0] [1] [0 0 0] [1 0 0] [1] g2(x,y,y,a()) = [0 1 0]x + [0 1 0]y + [0] >= [0 1 0]x + [0 0 0]y + [0] = h(x,y) [1 0 1] [1 0 1] [1] [1 0 1] [1 0 0] [0] [1 0 0] [1 0 0] [1] [0 0 0] [1 0 0] [1] g2(y,y,x,a()) = [0 1 0]x + [0 1 0]y + [0] >= [0 1 0]x + [0 0 0]y + [0] = h(x,y) [1 0 1] [1 0 1] [1] [1 0 1] [1 0 0] [0] [1 0 0] [1] h(x,x) = [0 1 0]x + [0] >= x = x [2 0 1] [0] problem: DPs: TRS: f(x,y,w,w,a()) -> g1(x,x,y,w) f(x,y,w,a(),a()) -> g1(y,x,x,w) f(x,y,a(),a(),w) -> g2(x,y,y,w) f(x,y,a(),w,w) -> g2(y,y,x,w) g1(x,x,y,a()) -> h(x,y) g1(y,x,x,a()) -> h(x,y) g2(x,y,y,a()) -> h(x,y) g2(y,y,x,a()) -> h(x,y) h(x,x) -> x Qed