YES Problem: app(app(app(compose(),f),g),x) -> app(g,app(f,x)) app(reverse(),l) -> app(app(reverse2(),l),nil()) app(app(reverse2(),nil()),l) -> l app(app(reverse2(),app(app(cons(),x),xs)),l) -> app(app(reverse2(),xs),app(app(cons(),x),l)) app(hd(),app(app(cons(),x),xs)) -> x app(tl(),app(app(cons(),x),xs)) -> xs last() -> app(app(compose(),hd()),reverse()) init() -> app(app(compose(),reverse()),app(app(compose(),tl()),reverse())) Proof: Extended Uncurrying Processor: application symbol: app symbol table: init ==> init0/0 last ==> last0/0 tl ==> tl0/0 tl1/1 hd ==> hd0/0 hd1/1 cons ==> cons0/0 cons1/1 cons2/2 nil ==> nil0/0 reverse2 ==> reverse20/0 reverse21/1 reverse22/2 reverse ==> reverse0/0 reverse1/1 compose ==> compose0/0 compose1/1 compose2/2 compose3/3 uncurry-rules: app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) app(compose1(x5),x6) -> compose2(x5,x6) app(compose0(),x5) -> compose1(x5) app(reverse0(),x9) -> reverse1(x9) app(reverse21(x11),x12) -> reverse22(x11,x12) app(reverse20(),x11) -> reverse21(x11) app(cons1(x15),x16) -> cons2(x15,x16) app(cons0(),x15) -> cons1(x15) app(hd0(),x18) -> hd1(x18) app(tl0(),x20) -> tl1(x20) eta-rules: problem: compose3(f,g,x) -> app(g,app(f,x)) reverse1(l) -> reverse22(l,nil0()) reverse22(nil0(),l) -> l reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) hd1(cons2(x,xs)) -> x tl1(cons2(x,xs)) -> xs last0() -> compose2(hd0(),reverse0()) init0() -> compose2(reverse0(),compose2(tl0(),reverse0())) app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) app(compose1(x5),x6) -> compose2(x5,x6) app(compose0(),x5) -> compose1(x5) app(reverse0(),x9) -> reverse1(x9) app(reverse21(x11),x12) -> reverse22(x11,x12) app(reverse20(),x11) -> reverse21(x11) app(cons1(x15),x16) -> cons2(x15,x16) app(cons0(),x15) -> cons1(x15) app(hd0(),x18) -> hd1(x18) app(tl0(),x20) -> tl1(x20) Matrix Interpretation Processor: dim=3 interpretation: [reverse22](x0, x1) = x0 + x1 , [1] [reverse1](x0) = x0 + [0] [1], [1 1 1] [app](x0, x1) = [0 1 1]x0 + x1 [0 1 1] , [1] [reverse20] = [0] [0], [cons1](x0) = x0 , [tl1](x0) = x0 , [0] [nil0] = [0] [1], [1] [reverse21](x0) = x0 + [0] [0], [0] [last0] = [1] [0], [1 1 1] [cons2](x0, x1) = [0 1 0]x0 + x1 [0 0 1] , [1] [init0] = [1] [1], [0] [compose0] = [0] [1], [0] [cons0] = [0] [0], [0] [tl0] = [0] [0], [0] [reverse0] = [1] [0], [1 0 0] [compose2](x0, x1) = [0 0 0]x0 + x1 [0 1 1] , [0] [hd0] = [0] [0], [hd1](x0) = x0 , [0] [compose1](x0) = x0 + [1] [0], [1 1 1] [1 1 1] [compose3](x0, x1, x2) = [0 1 1]x0 + [0 1 1]x1 + x2 [0 1 1] [0 1 1] orientation: [1 1 1] [1 1 1] [1 1 1] [1 1 1] compose3(f,g,x) = [0 1 1]f + [0 1 1]g + x >= [0 1 1]f + [0 1 1]g + x = app(g,app(f,x)) [0 1 1] [0 1 1] [0 1 1] [0 1 1] [1] [0] reverse1(l) = l + [0] >= l + [0] = reverse22(l,nil0()) [1] [1] [0] reverse22(nil0(),l) = l + [0] >= l = l [1] [1 1 1] [1 1 1] reverse22(cons2(x,xs),l) = l + [0 1 0]x + xs >= l + [0 1 0]x + xs = reverse22(xs,cons2(x,l)) [0 0 1] [0 0 1] [1 1 1] hd1(cons2(x,xs)) = [0 1 0]x + xs >= x = x [0 0 1] [1 1 1] tl1(cons2(x,xs)) = [0 1 0]x + xs >= xs = xs [0 0 1] [0] [0] last0() = [1] >= [1] = compose2(hd0(),reverse0()) [0] [0] [1] [0] init0() = [1] >= [1] = compose2(reverse0(),compose2(tl0(),reverse0())) [1] [1] [1 1 1] [1 1 1] [1 1 1] [1 1 1] app(compose2(x5,x6),x7) = [0 1 1]x5 + [0 1 1]x6 + x7 >= [0 1 1]x5 + [0 1 1]x6 + x7 = compose3(x5,x6,x7) [0 1 1] [0 1 1] [0 1 1] [0 1 1] [1 1 1] [1] [1 0 0] app(compose1(x5),x6) = [0 1 1]x5 + x6 + [1] >= [0 0 0]x5 + x6 = compose2(x5,x6) [0 1 1] [1] [0 1 1] [1] [0] app(compose0(),x5) = x5 + [1] >= x5 + [1] = compose1(x5) [1] [0] [1] [1] app(reverse0(),x9) = x9 + [1] >= x9 + [0] = reverse1(x9) [1] [1] [1 1 1] [1] app(reverse21(x11),x12) = [0 1 1]x11 + x12 + [0] >= x11 + x12 = reverse22(x11,x12) [0 1 1] [0] [1] [1] app(reverse20(),x11) = x11 + [0] >= x11 + [0] = reverse21(x11) [0] [0] [1 1 1] [1 1 1] app(cons1(x15),x16) = [0 1 1]x15 + x16 >= [0 1 0]x15 + x16 = cons2(x15,x16) [0 1 1] [0 0 1] app(cons0(),x15) = x15 >= x15 = cons1(x15) app(hd0(),x18) = x18 >= x18 = hd1(x18) app(tl0(),x20) = x20 >= x20 = tl1(x20) problem: compose3(f,g,x) -> app(g,app(f,x)) reverse22(nil0(),l) -> l reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) hd1(cons2(x,xs)) -> x tl1(cons2(x,xs)) -> xs last0() -> compose2(hd0(),reverse0()) app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) app(reverse0(),x9) -> reverse1(x9) app(reverse20(),x11) -> reverse21(x11) app(cons1(x15),x16) -> cons2(x15,x16) app(cons0(),x15) -> cons1(x15) app(hd0(),x18) -> hd1(x18) app(tl0(),x20) -> tl1(x20) Matrix Interpretation Processor: dim=3 interpretation: [reverse22](x0, x1) = x0 + x1 , [reverse1](x0) = x0 , [1 1 0] [app](x0, x1) = [0 1 1]x0 + x1 [0 0 1] , [1] [reverse20] = [0] [0], [0] [cons1](x0) = x0 + [1] [0], [tl1](x0) = x0 , [1] [nil0] = [0] [0], [reverse21](x0) = x0 , [1] [last0] = [0] [1], [1 1 0] [0] [cons2](x0, x1) = [0 1 0]x0 + x1 + [1] [0 0 1] [0], [0] [cons0] = [1] [0], [1] [tl0] = [0] [0], [0] [reverse0] = [0] [0], [1 0 0] [1 0 1] [compose2](x0, x1) = [0 1 0]x0 + [0 1 0]x1 [1 0 1] [1 0 1] , [1] [hd0] = [0] [0], [hd1](x0) = x0 , [1 1 0] [1 1 0] [compose3](x0, x1, x2) = [0 1 1]x0 + [0 1 1]x1 + x2 [1 0 1] [0 0 1] orientation: [1 1 0] [1 1 0] [1 1 0] [1 1 0] compose3(f,g,x) = [0 1 1]f + [0 1 1]g + x >= [0 1 1]f + [0 1 1]g + x = app(g,app(f,x)) [1 0 1] [0 0 1] [0 0 1] [0 0 1] [1] reverse22(nil0(),l) = l + [0] >= l = l [0] [1 1 0] [0] [1 1 0] [0] reverse22(cons2(x,xs),l) = l + [0 1 0]x + xs + [1] >= l + [0 1 0]x + xs + [1] = reverse22(xs,cons2(x,l)) [0 0 1] [0] [0 0 1] [0] [1 1 0] [0] hd1(cons2(x,xs)) = [0 1 0]x + xs + [1] >= x = x [0 0 1] [0] [1 1 0] [0] tl1(cons2(x,xs)) = [0 1 0]x + xs + [1] >= xs = xs [0 0 1] [0] [1] [1] last0() = [0] >= [0] = compose2(hd0(),reverse0()) [1] [1] [1 1 0] [1 1 1] [1 1 0] [1 1 0] app(compose2(x5,x6),x7) = [1 1 1]x5 + [1 1 1]x6 + x7 >= [0 1 1]x5 + [0 1 1]x6 + x7 = compose3(x5,x6,x7) [1 0 1] [1 0 1] [1 0 1] [0 0 1] app(reverse0(),x9) = x9 >= x9 = reverse1(x9) [1] app(reverse20(),x11) = x11 + [0] >= x11 = reverse21(x11) [0] [1 1 0] [1] [1 1 0] [0] app(cons1(x15),x16) = [0 1 1]x15 + x16 + [1] >= [0 1 0]x15 + x16 + [1] = cons2(x15,x16) [0 0 1] [0] [0 0 1] [0] [1] [0] app(cons0(),x15) = x15 + [1] >= x15 + [1] = cons1(x15) [0] [0] [1] app(hd0(),x18) = x18 + [0] >= x18 = hd1(x18) [0] [1] app(tl0(),x20) = x20 + [0] >= x20 = tl1(x20) [0] problem: compose3(f,g,x) -> app(g,app(f,x)) reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) hd1(cons2(x,xs)) -> x tl1(cons2(x,xs)) -> xs last0() -> compose2(hd0(),reverse0()) app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) app(reverse0(),x9) -> reverse1(x9) Matrix Interpretation Processor: dim=3 interpretation: [1 0 1] [1 0 0] [0] [reverse22](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [1] [0 1 1] [0 0 0] [0], [1 0 0] [0] [reverse1](x0) = [0 0 0]x0 + [0] [0 0 0] [1], [1 0 0] [1 0 0] [app](x0, x1) = [0 1 1]x0 + [0 0 0]x1 [1 0 0] [0 0 0] , [1 0 0] [tl1](x0) = [0 0 1]x0 [1 0 1] , [1] [last0] = [1] [1], [1 0 0] [1 0 0] [1] [cons2](x0, x1) = [0 1 1]x0 + [0 0 0]x1 + [0] [0 0 0] [0 1 1] [0], [1] [reverse0] = [1] [0], [1 0 1] [1 0 1] [compose2](x0, x1) = [0 0 0]x0 + [1 0 1]x1 [1 0 0] [0 1 0] , [0] [hd0] = [0] [0], [1 0 0] [hd1](x0) = [0 1 0]x0 [0 1 0] , [1 0 0] [1 0 0] [1 0 0] [compose3](x0, x1, x2) = [1 0 0]x0 + [0 1 1]x1 + [0 0 0]x2 [1 0 1] [1 0 0] [0 0 0] orientation: [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] compose3(f,g,x) = [1 0 0]f + [0 1 1]g + [0 0 0]x >= [0 0 0]f + [0 1 1]g + [0 0 0]x = app(g,app(f,x)) [1 0 1] [1 0 0] [0 0 0] [0 0 0] [1 0 0] [0 0 0] [1 0 0] [1 0 0] [1 1 1] [1] [1 0 0] [1 0 0] [1 0 1] [1] reverse22(cons2(x,xs),l) = [0 0 0]l + [0 0 0]x + [0 0 0]xs + [1] >= [0 0 0]l + [0 0 0]x + [0 0 0]xs + [1] = reverse22(xs,cons2(x,l)) [0 0 0] [0 1 1] [0 1 1] [0] [0 0 0] [0 0 0] [0 1 1] [0] [1 0 0] [1 0 0] [1] hd1(cons2(x,xs)) = [0 1 1]x + [0 0 0]xs + [0] >= x = x [0 1 1] [0 0 0] [0] [1 0 0] [1 0 0] [1] tl1(cons2(x,xs)) = [0 0 0]x + [0 1 1]xs + [0] >= xs = xs [1 0 0] [1 1 1] [1] [1] [1] last0() = [1] >= [1] = compose2(hd0(),reverse0()) [1] [1] [1 0 1] [1 0 1] [1 0 0] [1 0 0] [1 0 0] [1 0 0] app(compose2(x5,x6),x7) = [1 0 0]x5 + [1 1 1]x6 + [0 0 0]x7 >= [1 0 0]x5 + [0 1 1]x6 + [0 0 0]x7 = compose3(x5,x6,x7) [1 0 1] [1 0 1] [0 0 0] [1 0 1] [1 0 0] [0 0 0] [1 0 0] [1] [1 0 0] [0] app(reverse0(),x9) = [0 0 0]x9 + [1] >= [0 0 0]x9 + [0] = reverse1(x9) [0 0 0] [1] [0 0 0] [1] problem: compose3(f,g,x) -> app(g,app(f,x)) reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) last0() -> compose2(hd0(),reverse0()) app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) Matrix Interpretation Processor: dim=3 interpretation: [1 1 0] [1 0 0] [reverse22](x0, x1) = [0 0 1]x0 + [0 0 1]x1 [0 0 1] [1 0 0] , [1 0 0] [1 1 0] [0] [app](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [1] [0 1 1] [1 1 0] [0], [1] [last0] = [1] [0], [1 1 0] [0] [cons2](x0, x1) = [0 0 0]x0 + x1 + [1] [1 1 0] [0], [0] [reverse0] = [0] [0], [1 0 0] [1 0 1] [1] [compose2](x0, x1) = [0 1 0]x0 + [0 0 0]x1 + [1] [1 0 0] [0 1 1] [0], [0] [hd0] = [0] [0], [1 0 0] [1 0 0] [1 1 0] [1] [compose3](x0, x1, x2) = [0 0 0]x0 + [0 0 0]x1 + [0 0 0]x2 + [1] [1 0 0] [0 1 1] [1 1 0] [1] orientation: [1 0 0] [1 0 0] [1 1 0] [1] [1 0 0] [1 0 0] [1 1 0] [1] compose3(f,g,x) = [0 0 0]f + [0 0 0]g + [0 0 0]x + [1] >= [0 0 0]f + [0 0 0]g + [0 0 0]x + [1] = app(g,app(f,x)) [1 0 0] [0 1 1] [1 1 0] [1] [1 0 0] [0 1 1] [1 1 0] [1] [1 0 0] [1 1 0] [1 1 0] [1] [1 0 0] [1 1 0] [1 1 0] reverse22(cons2(x,xs),l) = [0 0 1]l + [1 1 0]x + [0 0 1]xs + [0] >= [0 0 1]l + [1 1 0]x + [0 0 1]xs = reverse22(xs,cons2(x,l)) [1 0 0] [1 1 0] [0 0 1] [0] [1 0 0] [1 1 0] [0 0 1] [1] [1] last0() = [1] >= [1] = compose2(hd0(),reverse0()) [0] [0] [1 0 0] [1 0 1] [1 1 0] [1] [1 0 0] [1 0 0] [1 1 0] [1] app(compose2(x5,x6),x7) = [0 0 0]x5 + [0 0 0]x6 + [0 0 0]x7 + [1] >= [0 0 0]x5 + [0 0 0]x6 + [0 0 0]x7 + [1] = compose3(x5,x6,x7) [1 1 0] [0 1 1] [1 1 0] [1] [1 0 0] [0 1 1] [1 1 0] [1] problem: compose3(f,g,x) -> app(g,app(f,x)) last0() -> compose2(hd0(),reverse0()) app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) Matrix Interpretation Processor: dim=3 interpretation: [1 0 1] [1 0 0] [app](x0, x1) = [0 1 0]x0 + [0 0 0]x1 [1 0 0] [0 0 0] , [1] [last0] = [0] [1], [0] [reverse0] = [0] [0], [1 0 1] [1 0 0] [0] [compose2](x0, x1) = [0 0 1]x0 + [0 1 1]x1 + [0] [0 0 0] [0 0 1] [1], [0] [hd0] = [0] [0], [1 0 1] [1 0 1] [1 0 0] [compose3](x0, x1, x2) = [0 0 0]x0 + [0 1 0]x1 + [0 0 0]x2 [0 0 0] [1 0 0] [0 0 0] orientation: [1 0 1] [1 0 1] [1 0 0] [1 0 1] [1 0 1] [1 0 0] compose3(f,g,x) = [0 0 0]f + [0 1 0]g + [0 0 0]x >= [0 0 0]f + [0 1 0]g + [0 0 0]x = app(g,app(f,x)) [0 0 0] [1 0 0] [0 0 0] [0 0 0] [1 0 0] [0 0 0] [1] [0] last0() = [0] >= [0] = compose2(hd0(),reverse0()) [1] [1] [1 0 1] [1 0 1] [1 0 0] [1] [1 0 1] [1 0 1] [1 0 0] app(compose2(x5,x6),x7) = [0 0 1]x5 + [0 1 1]x6 + [0 0 0]x7 + [0] >= [0 0 0]x5 + [0 1 0]x6 + [0 0 0]x7 = compose3(x5,x6,x7) [1 0 1] [1 0 0] [0 0 0] [0] [0 0 0] [1 0 0] [0 0 0] problem: compose3(f,g,x) -> app(g,app(f,x)) Matrix Interpretation Processor: dim=3 interpretation: [1 0 0] [1 0 0] [app](x0, x1) = [0 0 0]x0 + [0 0 1]x1 [0 0 0] [0 0 1] , [1 0 0] [1 0 0] [1 0 0] [1] [compose3](x0, x1, x2) = [0 0 0]x0 + [0 0 0]x1 + [0 0 1]x2 + [0] [0 0 0] [0 0 0] [0 0 1] [0] orientation: [1 0 0] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1 0 0] compose3(f,g,x) = [0 0 0]f + [0 0 0]g + [0 0 1]x + [0] >= [0 0 0]f + [0 0 0]g + [0 0 1]x = app(g,app(f,x)) [0 0 0] [0 0 0] [0 0 1] [0] [0 0 0] [0 0 0] [0 0 1] problem: Qed