/export/starexec/sandbox2/solver/bin/starexec_run_ttt2 /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Proof: DP Processor: DPs: app#(cons(x,l),k) -> app#(l,k) sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(plus(cons(0(),x),cons(y,l))) -> pred#(sum(cons(s(x),cons(y,l)))) plus#(s(x),s(y)) -> id#(y) plus#(s(x),s(y)) -> id#(x) plus#(s(x),s(y)) -> not#(gt(x,y)) plus#(s(x),s(y)) -> if#(not(gt(x,y)),id(x),id(y)) plus#(s(x),s(y)) -> gt#(x,y) plus#(s(x),s(y)) -> if#(gt(x,y),x,y) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(s(x),x) -> id#(x) plus#(s(x),x) -> gt#(x,x) plus#(s(x),x) -> if#(gt(x,x),id(x),id(x)) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) plus#(id(x),s(y)) -> gt#(s(y),y) plus#(id(x),s(y)) -> if#(gt(s(y),y),y,s(y)) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) not#(x) -> if#(x,false(),true()) gt#(s(x),s(y)) -> gt#(x,y) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) TDG Processor: DPs: app#(cons(x,l),k) -> app#(l,k) sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(plus(cons(0(),x),cons(y,l))) -> pred#(sum(cons(s(x),cons(y,l)))) plus#(s(x),s(y)) -> id#(y) plus#(s(x),s(y)) -> id#(x) plus#(s(x),s(y)) -> not#(gt(x,y)) plus#(s(x),s(y)) -> if#(not(gt(x,y)),id(x),id(y)) plus#(s(x),s(y)) -> gt#(x,y) plus#(s(x),s(y)) -> if#(gt(x,y),x,y) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(s(x),x) -> id#(x) plus#(s(x),x) -> gt#(x,x) plus#(s(x),x) -> if#(gt(x,x),id(x),id(x)) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) plus#(id(x),s(y)) -> gt#(s(y),y) plus#(id(x),s(y)) -> if#(gt(s(y),y),y,s(y)) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) not#(x) -> if#(x,false(),true()) gt#(s(x),s(y)) -> gt#(x,y) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) graph: gt#(s(x),s(y)) -> gt#(x,y) -> gt#(s(x),s(y)) -> gt#(x,y) plus#(id(x),s(y)) -> gt#(s(y),y) -> gt#(s(x),s(y)) -> gt#(x,y) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(id(x),s(y)) -> if#(gt(s(y),y),y,s(y)) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(id(x),s(y)) -> gt#(s(y),y) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),x) -> if#(gt(x,x),id(x),id(x)) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),x) -> gt#(x,x) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),x) -> id#(x) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),s(y)) -> if#(gt(x,y),x,y) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),s(y)) -> gt#(x,y) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),s(y)) -> if#(not(gt(x,y)),id(x),id(y)) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),s(y)) -> not#(gt(x,y)) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),s(y)) -> id#(x) plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) -> plus#(s(x),s(y)) -> id#(y) plus#(s(x),s(y)) -> gt#(x,y) -> gt#(s(x),s(y)) -> gt#(x,y) plus#(s(x),s(y)) -> not#(gt(x,y)) -> not#(x) -> if#(x,false(),true()) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(id(x),s(y)) -> if#(gt(s(y),y),y,s(y)) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(id(x),s(y)) -> gt#(s(y),y) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),x) -> if#(gt(x,x),id(x),id(x)) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),x) -> gt#(x,x) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),x) -> id#(x) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),s(y)) -> if#(gt(x,y),x,y) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),s(y)) -> gt#(x,y) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),s(y)) -> if#(not(gt(x,y)),id(x),id(y)) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),s(y)) -> not#(gt(x,y)) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),s(y)) -> id#(x) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) -> plus#(s(x),s(y)) -> id#(y) plus#(s(x),x) -> gt#(x,x) -> gt#(s(x),s(y)) -> gt#(x,y) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(id(x),s(y)) -> if#(gt(s(y),y),y,s(y)) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(id(x),s(y)) -> gt#(s(y),y) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),x) -> if#(gt(x,x),id(x),id(x)) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),x) -> gt#(x,x) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),x) -> id#(x) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),s(y)) -> if#(gt(x,y),x,y) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),s(y)) -> gt#(x,y) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),s(y)) -> if#(not(gt(x,y)),id(x),id(y)) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),s(y)) -> not#(gt(x,y)) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),s(y)) -> id#(x) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) -> plus#(s(x),s(y)) -> id#(y) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(plus(cons(0(),x),cons(y,l))) -> pred#(sum(cons(s(x),cons(y,l)))) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(id(x),s(y)) -> if#(gt(s(y),y),y,s(y)) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(id(x),s(y)) -> gt#(s(y),y) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),x) -> if#(gt(x,x),id(x),id(x)) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),x) -> gt#(x,x) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),x) -> id#(x) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),s(y)) -> if#(gt(x,y),x,y) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),s(y)) -> gt#(x,y) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),s(y)) -> if#(not(gt(x,y)),id(x),id(y)) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),s(y)) -> not#(gt(x,y)) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),s(y)) -> id#(x) sum#(cons(x,cons(y,l))) -> plus#(x,y) -> plus#(s(x),s(y)) -> id#(y) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(plus(cons(0(),x),cons(y,l))) -> pred#(sum(cons(s(x),cons(y,l)))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(plus(cons(0(),x),cons(y,l))) -> pred#(sum(cons(s(x),cons(y,l)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(plus(cons(0(),x),cons(y,l))) -> pred#(sum(cons(s(x),cons(y,l)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(cons(x,cons(y,l))) -> plus#(x,y) sum#(app(l,cons(x,cons(y,k)))) -> app#(l,sum(cons(x,cons(y,k)))) -> app#(cons(x,l),k) -> app#(l,k) app#(cons(x,l),k) -> app#(l,k) -> app#(cons(x,l),k) -> app#(l,k) SCC Processor: #sccs: 4 #rules: 9 #arcs: 91/576 DPs: sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) EDG Processor: DPs: sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) graph: sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(cons(x,cons(y,k))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) -> sum#(plus(cons(0(),x),cons(y,l))) -> sum#(cons(s(x),cons(y,l))) SCC Processor: #sccs: 2 #rules: 2 #arcs: 7/16 DPs: sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Usable Rule Processor: DPs: sum#(app(l,cons(x,cons(y,k)))) -> sum#(app(l,sum(cons(x,cons(y,k))))) TRS: sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(cons(x,nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) if(true(),x,y) -> x if(false(),x,y) -> y app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) Matrix Interpretation Processor: dim=1 usable rules: sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(cons(x,nil())) -> cons(x,nil()) app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) interpretation: [plus](x0, x1) = 3, [gt](x0, x1) = 2x0 + 1, [app](x0, x1) = x0 + x1 + 1, [sum](x0) = 1, [sum#](x0) = 5x0 + 2, [not](x0) = 2x0 + 7, [nil] = 0, [false] = 1, [zero] = 0, [id](x0) = 2, [if](x0, x1, x2) = x0 + 4x1 + 7, [true] = 2, [s](x0) = 2x0 + 6, [cons](x0, x1) = x1 + 1 orientation: sum#(app(l,cons(x,cons(y,k)))) = 5k + 5l + 17 >= 5l + 12 = sum#(app(l,sum(cons(x,cons(y,k))))) sum(cons(x,cons(y,l))) = 1 >= 1 = sum(cons(plus(x,y),l)) sum(cons(x,nil())) = 1 >= 1 = cons(x,nil()) plus(s(x),s(y)) = 3 >= 30 = s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) = 3 >= 3 = plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) = 3 >= y = y plus(id(x),s(y)) = 3 >= 12 = s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) = 2 >= x = x not(x) = 2x + 7 >= x + 11 = if(x,false(),true()) gt(s(x),zero()) = 4x + 13 >= 2 = true() gt(zero(),y) = 1 >= 1 = false() gt(s(x),s(y)) = 4x + 13 >= 2x + 1 = gt(x,y) if(true(),x,y) = 4x + 9 >= x = x if(false(),x,y) = 4x + 8 >= y = y app(nil(),k) = k + 1 >= k = k app(l,nil()) = l + 1 >= l = l app(cons(x,l),k) = k + l + 2 >= k + l + 2 = cons(x,app(l,k)) problem: DPs: TRS: sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(cons(x,nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) if(true(),x,y) -> x if(false(),x,y) -> y app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) Qed DPs: sum#(cons(x,cons(y,l))) -> sum#(cons(plus(x,y),l)) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Subterm Criterion Processor: simple projection: pi(cons) = [1,1] pi(if) = [1,1,2,2,2] pi(id) = [0,0,0] pi(sum#) = [0,0] problem: DPs: TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Qed DPs: app#(cons(x,l),k) -> app#(l,k) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Subterm Criterion Processor: simple projection: pi(app#) = 0 problem: DPs: TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Qed DPs: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Usable Rule Processor: DPs: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(s(x),x) -> plus#(if(gt(x,x),id(x),id(x)),s(x)) TRS: gt(s(x),zero()) -> true() gt(s(x),s(y)) -> gt(x,y) gt(zero(),y) -> false() if(true(),x,y) -> x if(false(),x,y) -> y id(x) -> x not(x) -> if(x,false(),true()) Arctic Interpretation Processor: dimension: 1 usable rules: gt(s(x),zero()) -> true() gt(s(x),s(y)) -> gt(x,y) gt(zero(),y) -> false() if(true(),x,y) -> x if(false(),x,y) -> y id(x) -> x not(x) -> if(x,false(),true()) interpretation: [gt](x0, x1) = 2x1 + 1, [plus#](x0, x1) = 2x0 + x1 + 0, [not](x0) = 2x0 + 1, [false] = 0, [zero] = 2, [id](x0) = x0 + 1, [if](x0, x1, x2) = x0 + x1 + x2 + 0, [true] = 0, [s](x0) = 4x0 + 2 orientation: plus#(id(x),s(y)) = 2x + 4y + 3 >= 2x + 4y + 2 = plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) = 6x + 4y + 4 >= 2x + 4y + 3 = plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) plus#(s(x),x) = 6x + 4 >= 4x + 3 = plus#(if(gt(x,x),id(x),id(x)),s(x)) gt(s(x),zero()) = 4 >= 0 = true() gt(s(x),s(y)) = 6y + 4 >= 2y + 1 = gt(x,y) gt(zero(),y) = 2y + 1 >= 0 = false() if(true(),x,y) = x + y + 0 >= x = x if(false(),x,y) = x + y + 0 >= y = y id(x) = x + 1 >= x = x not(x) = 2x + 1 >= x + 0 = if(x,false(),true()) problem: DPs: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) TRS: gt(s(x),zero()) -> true() gt(s(x),s(y)) -> gt(x,y) gt(zero(),y) -> false() if(true(),x,y) -> x if(false(),x,y) -> y id(x) -> x not(x) -> if(x,false(),true()) Restore Modifier: DPs: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Usable Rule Processor: DPs: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) -> plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) TRS: gt(s(x),zero()) -> true() gt(s(x),s(y)) -> gt(x,y) gt(zero(),y) -> false() if(true(),x,y) -> x if(false(),x,y) -> y id(x) -> x not(x) -> if(x,false(),true()) Arctic Interpretation Processor: dimension: 1 usable rules: if(true(),x,y) -> x if(false(),x,y) -> y id(x) -> x interpretation: [gt](x0, x1) = x0 + 4x1 + 3, [plus#](x0, x1) = x0 + x1, [not](x0) = 2, [false] = 1, [zero] = 1, [id](x0) = x0, [if](x0, x1, x2) = x1 + x2, [true] = 5, [s](x0) = 1x0 orientation: plus#(id(x),s(y)) = x + 1y >= x + 1y = plus#(x,if(gt(s(y),y),y,s(y))) plus#(s(x),s(y)) = 1x + 1y >= x + y = plus#(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))) gt(s(x),zero()) = 1x + 5 >= 5 = true() gt(s(x),s(y)) = 1x + 5y + 3 >= x + 4y + 3 = gt(x,y) gt(zero(),y) = 4y + 3 >= 1 = false() if(true(),x,y) = x + y >= x = x if(false(),x,y) = x + y >= y = y id(x) = x >= x = x not(x) = 2 >= 5 = if(x,false(),true()) problem: DPs: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) TRS: gt(s(x),zero()) -> true() gt(s(x),s(y)) -> gt(x,y) gt(zero(),y) -> false() if(true(),x,y) -> x if(false(),x,y) -> y id(x) -> x not(x) -> if(x,false(),true()) Restore Modifier: DPs: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Size-Change Termination Processor: DPs: TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) The DP: plus#(id(x),s(y)) -> plus#(x,if(gt(s(y),y),y,s(y))) has the edges: 0 > 0 Qed DPs: gt#(s(x),s(y)) -> gt#(x,y) TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Subterm Criterion Processor: simple projection: pi(gt#) = 0 problem: DPs: TRS: app(nil(),k) -> k app(l,nil()) -> l app(cons(x,l),k) -> cons(x,app(l,k)) sum(cons(x,nil())) -> cons(x,nil()) sum(cons(x,cons(y,l))) -> sum(cons(plus(x,y),l)) sum(app(l,cons(x,cons(y,k)))) -> sum(app(l,sum(cons(x,cons(y,k))))) sum(plus(cons(0(),x),cons(y,l))) -> pred(sum(cons(s(x),cons(y,l)))) pred(cons(s(x),nil())) -> cons(x,nil()) plus(s(x),s(y)) -> s(s(plus(if(gt(x,y),x,y),if(not(gt(x,y)),id(x),id(y))))) plus(s(x),x) -> plus(if(gt(x,x),id(x),id(x)),s(x)) plus(zero(),y) -> y plus(id(x),s(y)) -> s(plus(x,if(gt(s(y),y),y,s(y)))) id(x) -> x if(true(),x,y) -> x if(false(),x,y) -> y not(x) -> if(x,false(),true()) gt(s(x),zero()) -> true() gt(zero(),y) -> false() gt(s(x),s(y)) -> gt(x,y) Qed