/export/starexec/sandbox/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- 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=1 interpretation: [init0] = 5, [last0] = 6, [tl1](x0) = x0 + 3, [tl0] = 1, [hd1](x0) = x0 + 6, [hd0] = 4, [cons2](x0, x1) = x0 + x1 + 2, [cons1](x0) = x0, [cons0] = 1, [nil0] = 0, [reverse22](x0, x1) = x0 + x1 + 2, [reverse21](x0) = x0 + 2, [reverse20] = 0, [reverse1](x0) = x0 + 2, [reverse0] = 0, [compose3](x0, x1, x2) = x0 + x1 + x2 + 4, [compose2](x0, x1) = x0 + x1 + 2, [compose1](x0) = x0 + 2, [compose0] = 0, [app](x0, x1) = x0 + x1 + 2 orientation: compose3(f,g,x) = f + g + x + 4 >= f + g + x + 4 = app(g,app(f,x)) reverse1(l) = l + 2 >= l + 2 = reverse22(l,nil0()) reverse22(nil0(),l) = l + 2 >= l = l reverse22(cons2(x,xs),l) = l + x + xs + 4 >= l + x + xs + 4 = reverse22(xs,cons2(x,l)) hd1(cons2(x,xs)) = x + xs + 8 >= x = x tl1(cons2(x,xs)) = x + xs + 5 >= xs = xs last0() = 6 >= 6 = compose2(hd0(),reverse0()) init0() = 5 >= 5 = compose2(reverse0(),compose2(tl0(),reverse0())) app(compose2(x5,x6),x7) = x5 + x6 + x7 + 4 >= x5 + x6 + x7 + 4 = compose3(x5,x6,x7) app(compose1(x5),x6) = x5 + x6 + 4 >= x5 + x6 + 2 = compose2(x5,x6) app(compose0(),x5) = x5 + 2 >= x5 + 2 = compose1(x5) app(reverse0(),x9) = x9 + 2 >= x9 + 2 = reverse1(x9) app(reverse21(x11),x12) = x11 + x12 + 4 >= x11 + x12 + 2 = reverse22(x11,x12) app(reverse20(),x11) = x11 + 2 >= x11 + 2 = reverse21(x11) app(cons1(x15),x16) = x15 + x16 + 2 >= x15 + x16 + 2 = cons2(x15,x16) app(cons0(),x15) = x15 + 3 >= x15 = cons1(x15) app(hd0(),x18) = x18 + 6 >= x18 + 6 = hd1(x18) app(tl0(),x20) = x20 + 3 >= x20 + 3 = tl1(x20) problem: compose3(f,g,x) -> app(g,app(f,x)) reverse1(l) -> reverse22(l,nil0()) reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) last0() -> compose2(hd0(),reverse0()) init0() -> compose2(reverse0(),compose2(tl0(),reverse0())) app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) app(compose0(),x5) -> compose1(x5) app(reverse0(),x9) -> reverse1(x9) app(reverse20(),x11) -> reverse21(x11) app(cons1(x15),x16) -> cons2(x15,x16) app(hd0(),x18) -> hd1(x18) app(tl0(),x20) -> tl1(x20) Matrix Interpretation Processor: dim=1 interpretation: [init0] = 0, [last0] = 0, [tl1](x0) = x0, [tl0] = 0, [hd1](x0) = x0, [hd0] = 0, [cons2](x0, x1) = 4x0 + x1 + 2, [cons1](x0) = 2x0 + 1, [nil0] = 0, [reverse22](x0, x1) = x0 + x1, [reverse21](x0) = x0, [reverse20] = 0, [reverse1](x0) = x0, [reverse0] = 0, [compose3](x0, x1, x2) = 2x0 + 2x1 + x2, [compose2](x0, x1) = x0 + x1, [compose1](x0) = x0, [compose0] = 1, [app](x0, x1) = 2x0 + x1 orientation: compose3(f,g,x) = 2f + 2g + x >= 2f + 2g + x = app(g,app(f,x)) reverse1(l) = l >= l = reverse22(l,nil0()) reverse22(cons2(x,xs),l) = l + 4x + xs + 2 >= l + 4x + xs + 2 = reverse22(xs,cons2(x,l)) last0() = 0 >= 0 = compose2(hd0(),reverse0()) init0() = 0 >= 0 = compose2(reverse0(),compose2(tl0(),reverse0())) app(compose2(x5,x6),x7) = 2x5 + 2x6 + x7 >= 2x5 + 2x6 + x7 = compose3(x5,x6,x7) app(compose0(),x5) = x5 + 2 >= x5 = compose1(x5) app(reverse0(),x9) = x9 >= x9 = reverse1(x9) app(reverse20(),x11) = x11 >= x11 = reverse21(x11) app(cons1(x15),x16) = 4x15 + x16 + 2 >= 4x15 + x16 + 2 = cons2(x15,x16) app(hd0(),x18) = x18 >= x18 = hd1(x18) app(tl0(),x20) = x20 >= x20 = tl1(x20) problem: compose3(f,g,x) -> app(g,app(f,x)) reverse1(l) -> reverse22(l,nil0()) reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) last0() -> compose2(hd0(),reverse0()) init0() -> compose2(reverse0(),compose2(tl0(),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(hd0(),x18) -> hd1(x18) app(tl0(),x20) -> tl1(x20) Matrix Interpretation Processor: dim=1 interpretation: [init0] = 0, [last0] = 5, [tl1](x0) = x0, [tl0] = 0, [hd1](x0) = x0, [hd0] = 5, [cons2](x0, x1) = x0 + x1 + 3, [cons1](x0) = 2x0 + 3, [nil0] = 0, [reverse22](x0, x1) = x0 + x1, [reverse21](x0) = x0, [reverse20] = 0, [reverse1](x0) = x0, [reverse0] = 0, [compose3](x0, x1, x2) = x0 + 2x1 + x2, [compose2](x0, x1) = x0 + 2x1, [app](x0, x1) = x0 + x1 orientation: compose3(f,g,x) = f + 2g + x >= f + g + x = app(g,app(f,x)) reverse1(l) = l >= l = reverse22(l,nil0()) reverse22(cons2(x,xs),l) = l + x + xs + 3 >= l + x + xs + 3 = reverse22(xs,cons2(x,l)) last0() = 5 >= 5 = compose2(hd0(),reverse0()) init0() = 0 >= 0 = compose2(reverse0(),compose2(tl0(),reverse0())) app(compose2(x5,x6),x7) = x5 + 2x6 + x7 >= x5 + 2x6 + x7 = compose3(x5,x6,x7) app(reverse0(),x9) = x9 >= x9 = reverse1(x9) app(reverse20(),x11) = x11 >= x11 = reverse21(x11) app(cons1(x15),x16) = 2x15 + x16 + 3 >= x15 + x16 + 3 = cons2(x15,x16) app(hd0(),x18) = x18 + 5 >= x18 = hd1(x18) app(tl0(),x20) = x20 >= x20 = tl1(x20) problem: compose3(f,g,x) -> app(g,app(f,x)) reverse1(l) -> reverse22(l,nil0()) reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) last0() -> compose2(hd0(),reverse0()) init0() -> compose2(reverse0(),compose2(tl0(),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(tl0(),x20) -> tl1(x20) Matrix Interpretation Processor: dim=3 interpretation: [1] [init0] = [1] [1], [1] [last0] = [1] [1], [1 0 0] [tl1](x0) = [0 0 0]x0 [0 0 0] , [0] [tl0] = [0] [0], [0] [hd0] = [1] [0], [1 0 0] [1 0 0] [cons2](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] , [1 0 0] [cons1](x0) = [0 0 0]x0 [0 0 0] , [0] [nil0] = [0] [0], [1 0 0] [1 0 0] [reverse22](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 1 0] , [1 0 0] [reverse21](x0) = [0 0 0]x0 [0 0 0] , [0] [reverse20] = [0] [0], [1 0 0] [1] [reverse1](x0) = [0 0 0]x0 + [0] [0 0 0] [0], [0] [reverse0] = [1] [0], [1 1 0] [1 1 0] [1 0 0] [compose3](x0, x1, x2) = [0 0 0]x0 + [0 0 0]x1 + [0 0 0]x2 [0 0 0] [0 0 0] [0 0 0] , [1 1 0] [1 0 0] [compose2](x0, x1) = [0 0 0]x0 + [0 1 0]x1 [0 0 0] [0 1 0] , [1 1 0] [1 0 0] [app](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] orientation: [1 1 0] [1 1 0] [1 0 0] [1 1 0] [1 1 0] [1 0 0] compose3(f,g,x) = [0 0 0]f + [0 0 0]g + [0 0 0]x >= [0 0 0]f + [0 0 0]g + [0 0 0]x = app(g,app(f,x)) [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [1 0 0] [1] [1 0 0] reverse1(l) = [0 0 0]l + [0] >= [0 0 0]l = reverse22(l,nil0()) [0 0 0] [0] [0 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] reverse22(cons2(x,xs),l) = [0 0 0]l + [0 0 0]x + [0 0 0]xs >= [0 0 0]l + [0 0 0]x + [0 0 0]xs = reverse22(xs,cons2(x,l)) [0 1 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [1] [1] last0() = [1] >= [1] = compose2(hd0(),reverse0()) [1] [1] [1] [1] init0() = [1] >= [1] = compose2(reverse0(),compose2(tl0(),reverse0())) [1] [1] [1 1 0] [1 1 0] [1 0 0] [1 1 0] [1 1 0] [1 0 0] app(compose2(x5,x6),x7) = [0 0 0]x5 + [0 0 0]x6 + [0 0 0]x7 >= [0 0 0]x5 + [0 0 0]x6 + [0 0 0]x7 = compose3(x5,x6,x7) [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [1 0 0] [1] [1 0 0] [1] app(reverse0(),x9) = [0 0 0]x9 + [0] >= [0 0 0]x9 + [0] = reverse1(x9) [0 0 0] [0] [0 0 0] [0] [1 0 0] [1 0 0] app(reverse20(),x11) = [0 0 0]x11 >= [0 0 0]x11 = reverse21(x11) [0 0 0] [0 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0 0] app(cons1(x15),x16) = [0 0 0]x15 + [0 0 0]x16 >= [0 0 0]x15 + [0 0 0]x16 = cons2(x15,x16) [0 0 0] [0 0 0] [0 0 0] [0 0 0] [1 0 0] [1 0 0] app(tl0(),x20) = [0 0 0]x20 >= [0 0 0]x20 = tl1(x20) [0 0 0] [0 0 0] problem: compose3(f,g,x) -> app(g,app(f,x)) reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) last0() -> compose2(hd0(),reverse0()) init0() -> compose2(reverse0(),compose2(tl0(),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(tl0(),x20) -> tl1(x20) Matrix Interpretation Processor: dim=3 interpretation: [1] [init0] = [1] [1], [1] [last0] = [1] [1], [1 0 0] [tl1](x0) = [0 0 1]x0 [0 0 0] , [0] [tl0] = [0] [0], [1] [hd0] = [0] [0], [1 0 0] [1 0 0] [cons2](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] , [1 0 0] [0] [cons1](x0) = [0 0 0]x0 + [1] [0 0 0] [0], [1 0 0] [1 0 0] [1] [reverse22](x0, x1) = [1 0 0]x0 + [0 0 0]x1 + [1] [0 0 0] [0 0 0] [0], [1 0 0] [0] [reverse21](x0) = [0 0 0]x0 + [1] [0 0 0] [1], [0] [reverse20] = [1] [0], [1 0 0] [reverse1](x0) = [0 0 1]x0 [0 0 0] , [0] [reverse0] = [0] [0], [1 1 0] [1 1 0] [1 0 0] [1] [compose3](x0, x1, x2) = [1 0 1]x0 + [0 1 1]x1 + [0 0 0]x2 + [1] [1 0 0] [0 0 1] [0 0 0] [1], [1 0 0] [1 1 0] [0] [compose2](x0, x1) = [0 1 1]x0 + [0 0 0]x1 + [1] [1 0 0] [0 1 1] [0], [1 1 0] [1 0 0] [0] [app](x0, x1) = [0 1 1]x0 + [0 0 1]x1 + [0] [0 0 1] [0 0 0] [1] orientation: [1 1 0] [1 1 0] [1 0 0] [1] [1 1 0] [1 1 0] [1 0 0] [0] compose3(f,g,x) = [1 0 1]f + [0 1 1]g + [0 0 0]x + [1] >= [0 0 1]f + [0 1 1]g + [0 0 0]x + [1] = app(g,app(f,x)) [1 0 0] [0 0 1] [0 0 0] [1] [0 0 0] [0 0 1] [0 0 0] [1] [1 0 0] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1 0 0] [1] reverse22(cons2(x,xs),l) = [0 0 0]l + [1 0 0]x + [1 0 0]xs + [1] >= [0 0 0]l + [0 0 0]x + [1 0 0]xs + [1] = reverse22(xs,cons2(x,l)) [0 0 0] [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0 0 0] [0] [1] [1] last0() = [1] >= [1] = compose2(hd0(),reverse0()) [1] [1] [1] [1] init0() = [1] >= [1] = compose2(reverse0(),compose2(tl0(),reverse0())) [1] [1] [1 1 1] [1 1 0] [1 0 0] [1] [1 1 0] [1 1 0] [1 0 0] [1] app(compose2(x5,x6),x7) = [1 1 1]x5 + [0 1 1]x6 + [0 0 1]x7 + [1] >= [1 0 1]x5 + [0 1 1]x6 + [0 0 0]x7 + [1] = compose3(x5,x6,x7) [1 0 0] [0 1 1] [0 0 0] [1] [1 0 0] [0 0 1] [0 0 0] [1] [1 0 0] [0] [1 0 0] app(reverse0(),x9) = [0 0 1]x9 + [0] >= [0 0 1]x9 = reverse1(x9) [0 0 0] [1] [0 0 0] [1 0 0] [1] [1 0 0] [0] app(reverse20(),x11) = [0 0 1]x11 + [1] >= [0 0 0]x11 + [1] = reverse21(x11) [0 0 0] [1] [0 0 0] [1] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] app(cons1(x15),x16) = [0 0 0]x15 + [0 0 1]x16 + [1] >= [0 0 0]x15 + [0 0 0]x16 = cons2(x15,x16) [0 0 0] [0 0 0] [1] [0 0 0] [0 0 0] [1 0 0] [0] [1 0 0] app(tl0(),x20) = [0 0 1]x20 + [0] >= [0 0 1]x20 = tl1(x20) [0 0 0] [1] [0 0 0] problem: reverse22(cons2(x,xs),l) -> reverse22(xs,cons2(x,l)) last0() -> compose2(hd0(),reverse0()) init0() -> compose2(reverse0(),compose2(tl0(),reverse0())) app(compose2(x5,x6),x7) -> compose3(x5,x6,x7) app(reverse0(),x9) -> reverse1(x9) app(tl0(),x20) -> tl1(x20) Matrix Interpretation Processor: dim=3 interpretation: [0] [init0] = [0] [0], [0] [last0] = [0] [0], [1 0 0] [tl1](x0) = [0 0 0]x0 [0 0 0] , [0] [tl0] = [0] [0], [0] [hd0] = [0] [0], [1 0 0] [1 0 0] [0] [cons2](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [0] [0 0 0] [0 0 1] [1], [1 0 1] [1 0 0] [reverse22](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] , [1 0 0] [reverse1](x0) = [0 0 0]x0 [0 0 0] , [0] [reverse0] = [0] [0], [1 0 0] [1 0 0] [1 0 0] [compose3](x0, x1, x2) = [0 0 0]x0 + [0 0 0]x1 + [0 0 0]x2 [0 0 0] [0 0 0] [0 0 0] , [1 0 0] [1 0 0] [compose2](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] , [1 0 0] [1 0 0] [1] [app](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [0] [0 0 0] [0 0 0] [0] orientation: [1 0 0] [1 0 0] [1 0 1] [1] [1 0 0] [1 0 0] [1 0 1] reverse22(cons2(x,xs),l) = [0 0 0]l + [0 0 0]x + [0 0 0]xs + [0] >= [0 0 0]l + [0 0 0]x + [0 0 0]xs = reverse22(xs,cons2(x,l)) [0 0 0] [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0 0 0] [0] [0] last0() = [0] >= [0] = compose2(hd0(),reverse0()) [0] [0] [0] [0] init0() = [0] >= [0] = compose2(reverse0(),compose2(tl0(),reverse0())) [0] [0] [1 0 0] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1 0 0] app(compose2(x5,x6),x7) = [0 0 0]x5 + [0 0 0]x6 + [0 0 0]x7 + [0] >= [0 0 0]x5 + [0 0 0]x6 + [0 0 0]x7 = compose3(x5,x6,x7) [0 0 0] [0 0 0] [0 0 0] [0] [0 0 0] [0 0 0] [0 0 0] [1 0 0] [1] [1 0 0] app(reverse0(),x9) = [0 0 0]x9 + [0] >= [0 0 0]x9 = reverse1(x9) [0 0 0] [0] [0 0 0] [1 0 0] [1] [1 0 0] app(tl0(),x20) = [0 0 0]x20 + [0] >= [0 0 0]x20 = tl1(x20) [0 0 0] [0] [0 0 0] problem: last0() -> compose2(hd0(),reverse0()) init0() -> compose2(reverse0(),compose2(tl0(),reverse0())) Matrix Interpretation Processor: dim=3 interpretation: [1] [init0] = [1] [0], [0] [last0] = [1] [0], [0] [tl0] = [0] [0], [0] [hd0] = [0] [0], [0] [reverse0] = [1] [0], [1 0 0] [1 0 0] [compose2](x0, x1) = [0 0 0]x0 + [0 1 0]x1 [0 0 0] [0 0 0] orientation: [0] [0] last0() = [1] >= [1] = compose2(hd0(),reverse0()) [0] [0] [1] [0] init0() = [1] >= [1] = compose2(reverse0(),compose2(tl0(),reverse0())) [0] [0] problem: last0() -> compose2(hd0(),reverse0()) Matrix Interpretation Processor: dim=3 interpretation: [1] [last0] = [0] [0], [0] [hd0] = [0] [0], [0] [reverse0] = [0] [0], [1 0 0] [1 0 0] [compose2](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] orientation: [1] [0] last0() = [0] >= [0] = compose2(hd0(),reverse0()) [0] [0] problem: Qed