/export/starexec/sandbox2/solver/bin/starexec_run_ttt2 /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Proof: DP Processor: DPs: append#(cons(y,ys),x) -> append#(ys,x) p#(s(s(x))) -> p#(s(x)) inc#(s(x)) -> inc#(x) addLists#(xs,ys,zs) -> append#(zs,head(ys)) addLists#(xs,ys,zs) -> head#(ys) addLists#(xs,ys,zs) -> inc#(head(ys)) addLists#(xs,ys,zs) -> p#(head(xs)) addLists#(xs,ys,zs) -> tail#(ys) addLists#(xs,ys,zs) -> tail#(xs) addLists#(xs,ys,zs) -> head#(xs) addLists#(xs,ys,zs) -> isZero#(head(xs)) addLists#(xs,ys,zs) -> isEmpty#(ys) addLists#(xs,ys,zs) -> isEmpty#(xs) addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) addList#(xs,ys) -> addLists#(xs,ys,nil()) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) TDG Processor: DPs: append#(cons(y,ys),x) -> append#(ys,x) p#(s(s(x))) -> p#(s(x)) inc#(s(x)) -> inc#(x) addLists#(xs,ys,zs) -> append#(zs,head(ys)) addLists#(xs,ys,zs) -> head#(ys) addLists#(xs,ys,zs) -> inc#(head(ys)) addLists#(xs,ys,zs) -> p#(head(xs)) addLists#(xs,ys,zs) -> tail#(ys) addLists#(xs,ys,zs) -> tail#(xs) addLists#(xs,ys,zs) -> head#(xs) addLists#(xs,ys,zs) -> isZero#(head(xs)) addLists#(xs,ys,zs) -> isEmpty#(ys) addLists#(xs,ys,zs) -> isEmpty#(xs) addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) addList#(xs,ys) -> addLists#(xs,ys,nil()) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) graph: addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> isEmpty#(xs) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> isEmpty#(ys) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> isZero#(head(xs)) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> head#(xs) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> tail#(xs) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> tail#(ys) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> p#(head(xs)) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> inc#(head(ys)) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> head#(ys) addList#(xs,ys) -> addLists#(xs,ys,nil()) -> addLists#(xs,ys,zs) -> append#(zs,head(ys)) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> isEmpty#(xs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> isEmpty#(ys) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> isZero#(head(xs)) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> head#(xs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> tail#(xs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> tail#(ys) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> p#(head(xs)) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> inc#(head(ys)) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> head#(ys) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) -> addLists#(xs,ys,zs) -> append#(zs,head(ys)) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> isEmpty#(xs) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> isEmpty#(ys) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> isZero#(head(xs)) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> head#(xs) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> tail#(xs) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> tail#(ys) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> p#(head(xs)) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> inc#(head(ys)) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> head#(ys) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) -> addLists#(xs,ys,zs) -> append#(zs,head(ys)) addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) -> if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) -> if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) addLists#(xs,ys,zs) -> inc#(head(ys)) -> inc#(s(x)) -> inc#(x) addLists#(xs,ys,zs) -> p#(head(xs)) -> p#(s(s(x))) -> p#(s(x)) addLists#(xs,ys,zs) -> append#(zs,head(ys)) -> append#(cons(y,ys),x) -> append#(ys,x) inc#(s(x)) -> inc#(x) -> inc#(s(x)) -> inc#(x) p#(s(s(x))) -> p#(s(x)) -> p#(s(s(x))) -> p#(s(x)) append#(cons(y,ys),x) -> append#(ys,x) -> append#(cons(y,ys),x) -> append#(ys,x) SCC Processor: #sccs: 4 #rules: 6 #arcs: 41/289 DPs: addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Usable Rule Processor: DPs: addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)),zs, append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs,ys,zs2) TRS: append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) head(cons(x,xs)) -> x inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) tail(cons(x,xs)) -> xs tail(nil()) -> nil() p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() isZero(0()) -> true() isZero(s(x)) -> false() isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() Arctic Interpretation Processor: dimension: 1 usable rules: head(cons(x,xs)) -> x inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) tail(cons(x,xs)) -> xs tail(nil()) -> nil() p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() isZero(0()) -> true() isZero(s(x)) -> false() interpretation: [true] = 1, [head](x0) = x0, [isEmpty](x0) = 1x0 + 7, [nil] = 0, [0] = 6, [append](x0, x1) = 4x0 + x1 + 0, [cons](x0, x1) = x0 + 3x1 + -2, [s](x0) = x0 + 4, [if#](x0, x1, x2, x3, x4, x5, x6, x7, x8) = x2 + x3 + -4x4 + -3x5 + -6x6 + -4, [inc](x0) = x0 + 0, [addLists#](x0, x1, x2) = -3x0 + -6x1 + 0, [p](x0) = x0, [tail](x0) = -3x0 + 0, [isZero](x0) = -4x0 + 0, [false] = 0 orientation: addLists#(xs,ys,zs) = -3xs + -6ys + 0 >= -3xs + -6ys + 0 = if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p ( head(xs)), tail (xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) = xs + -3xs2 + -4ys + -6ys2 + 0 >= -3xs2 + -6ys2 + 0 = addLists#(xs2,ys2,zs) if#(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) = xs + -3xs2 + -4ys + -6ys2 + 1 >= -3xs + -6ys + 0 = addLists#(xs,ys,zs2) append(nil(),x) = x + 4 >= x + 3 = cons(x,nil()) append(cons(y,ys),x) = x + 4y + 7ys + 2 >= 3x + y + 7ys + 3 = cons(y,append(ys,x)) head(cons(x,xs)) = x + 3xs + -2 >= x = x inc(s(x)) = x + 4 >= x + 4 = s(inc(x)) inc(0()) = 6 >= 6 = s(0()) tail(cons(x,xs)) = -3x + xs + 0 >= xs = xs tail(nil()) = 0 >= 0 = nil() p(s(s(x))) = x + 4 >= x + 4 = s(p(s(x))) p(s(0())) = 6 >= 6 = 0() p(0()) = 6 >= 6 = 0() isZero(0()) = 2 >= 1 = true() isZero(s(x)) = -4x + 0 >= 0 = false() isEmpty(cons(x,xs)) = 1x + 4xs + 7 >= 0 = false() isEmpty(nil()) = 7 >= 1 = true() problem: DPs: addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)),zs, append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) TRS: append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) head(cons(x,xs)) -> x inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) tail(cons(x,xs)) -> xs tail(nil()) -> nil() p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() isZero(0()) -> true() isZero(s(x)) -> false() isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() Restore Modifier: DPs: addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)),zs, append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)),zs, append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Usable Rule Processor: DPs: addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)), zs,append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists#(xs2,ys2,zs) TRS: append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) head(cons(x,xs)) -> x inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) tail(cons(x,xs)) -> xs tail(nil()) -> nil() p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() isZero(0()) -> true() isZero(s(x)) -> false() isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() Arctic Interpretation Processor: dimension: 1 usable rules: head(cons(x,xs)) -> x p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() isZero(0()) -> true() isZero(s(x)) -> false() isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() interpretation: [true] = 0, [head](x0) = x0, [isEmpty](x0) = 3x0, [nil] = 1, [0] = 0, [append](x0, x1) = x0 + -8x1 + 0, [cons](x0, x1) = 1x0 + 0, [s](x0) = 3x0 + 3, [if#](x0, x1, x2, x3, x4, x5, x6, x7, x8) = -10x0 + 2x2 + 3x5, [inc](x0) = 1x0 + 2, [addLists#](x0, x1, x2) = 2x0 + 4, [p](x0) = -2x0 + 0, [tail](x0) = -1x0 + 0, [isZero](x0) = x0, [false] = 3 orientation: addLists#(xs,ys,zs) = 2xs + 4 >= 2xs + 4 = if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p ( head(xs)), tail (xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if#(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) = 3xs2 + 5 >= 2xs2 + 4 = addLists#(xs2,ys2,zs) append(nil(),x) = -8x + 1 >= 1x + 0 = cons(x,nil()) append(cons(y,ys),x) = -8x + 1y + 0 >= 1y + 0 = cons(y,append(ys,x)) head(cons(x,xs)) = 1x + 0 >= x = x inc(s(x)) = 4x + 4 >= 4x + 5 = s(inc(x)) inc(0()) = 2 >= 3 = s(0()) tail(cons(x,xs)) = x + 0 >= xs = xs tail(nil()) = 0 >= 1 = nil() p(s(s(x))) = 4x + 4 >= 4x + 4 = s(p(s(x))) p(s(0())) = 1 >= 0 = 0() p(0()) = 0 >= 0 = 0() isZero(0()) = 0 >= 0 = true() isZero(s(x)) = 3x + 3 >= 3 = false() isEmpty(cons(x,xs)) = 4x + 3 >= 3 = false() isEmpty(nil()) = 4 >= 0 = true() problem: DPs: addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)), zs,append(zs,head(ys))) TRS: append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) head(cons(x,xs)) -> x inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) tail(cons(x,xs)) -> xs tail(nil()) -> nil() p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() isZero(0()) -> true() isZero(s(x)) -> false() isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() Restore Modifier: DPs: addLists#(xs,ys,zs) -> if#(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)), zs,append(zs,head(ys))) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)), zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) SCC Processor: #sccs: 0 #rules: 0 #arcs: 4/1 DPs: p#(s(s(x))) -> p#(s(x)) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Subterm Criterion Processor: simple projection: pi(p#) = 0 problem: DPs: TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)),zs, append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Qed DPs: inc#(s(x)) -> inc#(x) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Subterm Criterion Processor: simple projection: pi(inc#) = 0 problem: DPs: TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)),zs, append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Qed DPs: append#(cons(y,ys),x) -> append#(ys,x) TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys),cons(p(head(xs)),tail(xs)), cons(inc(head(ys)),tail(ys)),zs,append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Subterm Criterion Processor: simple projection: pi(append#) = 0 problem: DPs: TRS: isEmpty(cons(x,xs)) -> false() isEmpty(nil()) -> true() isZero(0()) -> true() isZero(s(x)) -> false() head(cons(x,xs)) -> x tail(cons(x,xs)) -> xs tail(nil()) -> nil() append(nil(),x) -> cons(x,nil()) append(cons(y,ys),x) -> cons(y,append(ys,x)) p(s(s(x))) -> s(p(s(x))) p(s(0())) -> 0() p(0()) -> 0() inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) addLists(xs,ys,zs) -> if(isEmpty(xs),isEmpty(ys),isZero(head(xs)),tail(xs),tail(ys), cons(p(head(xs)),tail(xs)),cons(inc(head(ys)),tail(ys)),zs, append(zs,head(ys))) if(true(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> zs if(true(),false(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),true(),b,xs,ys,xs2,ys2,zs,zs2) -> differentLengthError() if(false(),false(),false(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs2,ys2,zs) if(false(),false(),true(),xs,ys,xs2,ys2,zs,zs2) -> addLists(xs,ys,zs2) addList(xs,ys) -> addLists(xs,ys,nil()) Qed