MAYBE * Step 1: DependencyPairs MAYBE + Considered Problem: - Strict TRS: activate(X) -> X activate(n__from(X)) -> from(X) activate(n__zWquot(X1,X2)) -> zWquot(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) minus(X,0()) -> 0() minus(s(X),s(Y)) -> minus(X,Y) quot(0(),s(Y)) -> 0() quot(s(X),s(Y)) -> s(quot(minus(X,Y),s(Y))) sel(0(),cons(X,XS)) -> X sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) zWquot(X1,X2) -> n__zWquot(X1,X2) zWquot(XS,nil()) -> nil() zWquot(cons(X,XS),cons(Y,YS)) -> cons(quot(X,Y),n__zWquot(activate(XS),activate(YS))) zWquot(nil(),XS) -> nil() - Signature: {activate/1,from/1,minus/2,quot/2,sel/2,zWquot/2} / {0/0,cons/2,n__from/1,n__zWquot/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,from,minus,quot,sel,zWquot} and constructors {0 ,cons,n__from,n__zWquot,nil,s} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs activate#(X) -> c_1() activate#(n__from(X)) -> c_2(from#(X)) activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) from#(X) -> c_4() from#(X) -> c_5() minus#(X,0()) -> c_6() minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) quot#(0(),s(Y)) -> c_8() quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) zWquot#(X1,X2) -> c_12() zWquot#(XS,nil()) -> c_13() zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) zWquot#(nil(),XS) -> c_15() Weak DPs and mark the set of starting terms. * Step 2: UsableRules MAYBE + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__from(X)) -> c_2(from#(X)) activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) from#(X) -> c_4() from#(X) -> c_5() minus#(X,0()) -> c_6() minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) quot#(0(),s(Y)) -> c_8() quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) zWquot#(X1,X2) -> c_12() zWquot#(XS,nil()) -> c_13() zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) zWquot#(nil(),XS) -> c_15() - Weak TRS: activate(X) -> X activate(n__from(X)) -> from(X) activate(n__zWquot(X1,X2)) -> zWquot(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) minus(X,0()) -> 0() minus(s(X),s(Y)) -> minus(X,Y) quot(0(),s(Y)) -> 0() quot(s(X),s(Y)) -> s(quot(minus(X,Y),s(Y))) sel(0(),cons(X,XS)) -> X sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) zWquot(X1,X2) -> n__zWquot(X1,X2) zWquot(XS,nil()) -> nil() zWquot(cons(X,XS),cons(Y,YS)) -> cons(quot(X,Y),n__zWquot(activate(XS),activate(YS))) zWquot(nil(),XS) -> nil() - Signature: {activate/1,from/1,minus/2,quot/2,sel/2,zWquot/2,activate#/1,from#/1,minus#/2,quot#/2,sel#/2 ,zWquot#/2} / {0/0,cons/2,n__from/1,n__zWquot/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/0,c_5/0,c_6/0,c_7/1,c_8/0 ,c_9/2,c_10/0,c_11/2,c_12/0,c_13/0,c_14/3,c_15/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,from#,minus#,quot#,sel# ,zWquot#} and constructors {0,cons,n__from,n__zWquot,nil,s} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: activate(X) -> X activate(n__from(X)) -> from(X) activate(n__zWquot(X1,X2)) -> zWquot(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) minus(X,0()) -> 0() minus(s(X),s(Y)) -> minus(X,Y) quot(0(),s(Y)) -> 0() quot(s(X),s(Y)) -> s(quot(minus(X,Y),s(Y))) zWquot(X1,X2) -> n__zWquot(X1,X2) zWquot(XS,nil()) -> nil() zWquot(cons(X,XS),cons(Y,YS)) -> cons(quot(X,Y),n__zWquot(activate(XS),activate(YS))) zWquot(nil(),XS) -> nil() activate#(X) -> c_1() activate#(n__from(X)) -> c_2(from#(X)) activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) from#(X) -> c_4() from#(X) -> c_5() minus#(X,0()) -> c_6() minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) quot#(0(),s(Y)) -> c_8() quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) zWquot#(X1,X2) -> c_12() zWquot#(XS,nil()) -> c_13() zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) zWquot#(nil(),XS) -> c_15() * Step 3: PredecessorEstimation MAYBE + Considered Problem: - Strict DPs: activate#(X) -> c_1() activate#(n__from(X)) -> c_2(from#(X)) activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) from#(X) -> c_4() from#(X) -> c_5() minus#(X,0()) -> c_6() minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) quot#(0(),s(Y)) -> c_8() quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) sel#(0(),cons(X,XS)) -> c_10() sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) zWquot#(X1,X2) -> c_12() zWquot#(XS,nil()) -> c_13() zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) zWquot#(nil(),XS) -> c_15() - Weak TRS: activate(X) -> X activate(n__from(X)) -> from(X) activate(n__zWquot(X1,X2)) -> zWquot(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) minus(X,0()) -> 0() minus(s(X),s(Y)) -> minus(X,Y) quot(0(),s(Y)) -> 0() quot(s(X),s(Y)) -> s(quot(minus(X,Y),s(Y))) zWquot(X1,X2) -> n__zWquot(X1,X2) zWquot(XS,nil()) -> nil() zWquot(cons(X,XS),cons(Y,YS)) -> cons(quot(X,Y),n__zWquot(activate(XS),activate(YS))) zWquot(nil(),XS) -> nil() - Signature: {activate/1,from/1,minus/2,quot/2,sel/2,zWquot/2,activate#/1,from#/1,minus#/2,quot#/2,sel#/2 ,zWquot#/2} / {0/0,cons/2,n__from/1,n__zWquot/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/0,c_5/0,c_6/0,c_7/1,c_8/0 ,c_9/2,c_10/0,c_11/2,c_12/0,c_13/0,c_14/3,c_15/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,from#,minus#,quot#,sel# ,zWquot#} and constructors {0,cons,n__from,n__zWquot,nil,s} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,4,5,6,8,10,12,13,15} by application of Pre({1,4,5,6,8,10,12,13,15}) = {2,3,7,9,11,14}. Here rules are labelled as follows: 1: activate#(X) -> c_1() 2: activate#(n__from(X)) -> c_2(from#(X)) 3: activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) 4: from#(X) -> c_4() 5: from#(X) -> c_5() 6: minus#(X,0()) -> c_6() 7: minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) 8: quot#(0(),s(Y)) -> c_8() 9: quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) 10: sel#(0(),cons(X,XS)) -> c_10() 11: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) 12: zWquot#(X1,X2) -> c_12() 13: zWquot#(XS,nil()) -> c_13() 14: zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) 15: zWquot#(nil(),XS) -> c_15() * Step 4: PredecessorEstimation MAYBE + Considered Problem: - Strict DPs: activate#(n__from(X)) -> c_2(from#(X)) activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) - Weak DPs: activate#(X) -> c_1() from#(X) -> c_4() from#(X) -> c_5() minus#(X,0()) -> c_6() quot#(0(),s(Y)) -> c_8() sel#(0(),cons(X,XS)) -> c_10() zWquot#(X1,X2) -> c_12() zWquot#(XS,nil()) -> c_13() zWquot#(nil(),XS) -> c_15() - Weak TRS: activate(X) -> X activate(n__from(X)) -> from(X) activate(n__zWquot(X1,X2)) -> zWquot(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) minus(X,0()) -> 0() minus(s(X),s(Y)) -> minus(X,Y) quot(0(),s(Y)) -> 0() quot(s(X),s(Y)) -> s(quot(minus(X,Y),s(Y))) zWquot(X1,X2) -> n__zWquot(X1,X2) zWquot(XS,nil()) -> nil() zWquot(cons(X,XS),cons(Y,YS)) -> cons(quot(X,Y),n__zWquot(activate(XS),activate(YS))) zWquot(nil(),XS) -> nil() - Signature: {activate/1,from/1,minus/2,quot/2,sel/2,zWquot/2,activate#/1,from#/1,minus#/2,quot#/2,sel#/2 ,zWquot#/2} / {0/0,cons/2,n__from/1,n__zWquot/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/0,c_5/0,c_6/0,c_7/1,c_8/0 ,c_9/2,c_10/0,c_11/2,c_12/0,c_13/0,c_14/3,c_15/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,from#,minus#,quot#,sel# ,zWquot#} and constructors {0,cons,n__from,n__zWquot,nil,s} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1} by application of Pre({1}) = {5,6}. Here rules are labelled as follows: 1: activate#(n__from(X)) -> c_2(from#(X)) 2: activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) 3: minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) 4: quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) 5: sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) 6: zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) 7: activate#(X) -> c_1() 8: from#(X) -> c_4() 9: from#(X) -> c_5() 10: minus#(X,0()) -> c_6() 11: quot#(0(),s(Y)) -> c_8() 12: sel#(0(),cons(X,XS)) -> c_10() 13: zWquot#(X1,X2) -> c_12() 14: zWquot#(XS,nil()) -> c_13() 15: zWquot#(nil(),XS) -> c_15() * Step 5: RemoveWeakSuffixes MAYBE + Considered Problem: - Strict DPs: activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) - Weak DPs: activate#(X) -> c_1() activate#(n__from(X)) -> c_2(from#(X)) from#(X) -> c_4() from#(X) -> c_5() minus#(X,0()) -> c_6() quot#(0(),s(Y)) -> c_8() sel#(0(),cons(X,XS)) -> c_10() zWquot#(X1,X2) -> c_12() zWquot#(XS,nil()) -> c_13() zWquot#(nil(),XS) -> c_15() - Weak TRS: activate(X) -> X activate(n__from(X)) -> from(X) activate(n__zWquot(X1,X2)) -> zWquot(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) minus(X,0()) -> 0() minus(s(X),s(Y)) -> minus(X,Y) quot(0(),s(Y)) -> 0() quot(s(X),s(Y)) -> s(quot(minus(X,Y),s(Y))) zWquot(X1,X2) -> n__zWquot(X1,X2) zWquot(XS,nil()) -> nil() zWquot(cons(X,XS),cons(Y,YS)) -> cons(quot(X,Y),n__zWquot(activate(XS),activate(YS))) zWquot(nil(),XS) -> nil() - Signature: {activate/1,from/1,minus/2,quot/2,sel/2,zWquot/2,activate#/1,from#/1,minus#/2,quot#/2,sel#/2 ,zWquot#/2} / {0/0,cons/2,n__from/1,n__zWquot/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/0,c_5/0,c_6/0,c_7/1,c_8/0 ,c_9/2,c_10/0,c_11/2,c_12/0,c_13/0,c_14/3,c_15/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,from#,minus#,quot#,sel# ,zWquot#} and constructors {0,cons,n__from,n__zWquot,nil,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) -->_1 zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)):5 -->_1 zWquot#(nil(),XS) -> c_15():15 -->_1 zWquot#(XS,nil()) -> c_13():14 -->_1 zWquot#(X1,X2) -> c_12():13 2:S:minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) -->_1 minus#(X,0()) -> c_6():10 -->_1 minus#(s(X),s(Y)) -> c_7(minus#(X,Y)):2 3:S:quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) -->_1 quot#(0(),s(Y)) -> c_8():11 -->_2 minus#(X,0()) -> c_6():10 -->_1 quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)):3 -->_2 minus#(s(X),s(Y)) -> c_7(minus#(X,Y)):2 4:S:sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) -->_2 activate#(n__from(X)) -> c_2(from#(X)):7 -->_1 sel#(0(),cons(X,XS)) -> c_10():12 -->_2 activate#(X) -> c_1():6 -->_1 sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)):4 -->_2 activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)):1 5:S:zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) -->_3 activate#(n__from(X)) -> c_2(from#(X)):7 -->_2 activate#(n__from(X)) -> c_2(from#(X)):7 -->_1 quot#(0(),s(Y)) -> c_8():11 -->_3 activate#(X) -> c_1():6 -->_2 activate#(X) -> c_1():6 -->_1 quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)):3 -->_3 activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)):1 -->_2 activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)):1 6:W:activate#(X) -> c_1() 7:W:activate#(n__from(X)) -> c_2(from#(X)) -->_1 from#(X) -> c_5():9 -->_1 from#(X) -> c_4():8 8:W:from#(X) -> c_4() 9:W:from#(X) -> c_5() 10:W:minus#(X,0()) -> c_6() 11:W:quot#(0(),s(Y)) -> c_8() 12:W:sel#(0(),cons(X,XS)) -> c_10() 13:W:zWquot#(X1,X2) -> c_12() 14:W:zWquot#(XS,nil()) -> c_13() 15:W:zWquot#(nil(),XS) -> c_15() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 12: sel#(0(),cons(X,XS)) -> c_10() 13: zWquot#(X1,X2) -> c_12() 14: zWquot#(XS,nil()) -> c_13() 15: zWquot#(nil(),XS) -> c_15() 10: minus#(X,0()) -> c_6() 6: activate#(X) -> c_1() 11: quot#(0(),s(Y)) -> c_8() 7: activate#(n__from(X)) -> c_2(from#(X)) 8: from#(X) -> c_4() 9: from#(X) -> c_5() * Step 6: Failure MAYBE + Considered Problem: - Strict DPs: activate#(n__zWquot(X1,X2)) -> c_3(zWquot#(X1,X2)) minus#(s(X),s(Y)) -> c_7(minus#(X,Y)) quot#(s(X),s(Y)) -> c_9(quot#(minus(X,Y),s(Y)),minus#(X,Y)) sel#(s(N),cons(X,XS)) -> c_11(sel#(N,activate(XS)),activate#(XS)) zWquot#(cons(X,XS),cons(Y,YS)) -> c_14(quot#(X,Y),activate#(XS),activate#(YS)) - Weak TRS: activate(X) -> X activate(n__from(X)) -> from(X) activate(n__zWquot(X1,X2)) -> zWquot(X1,X2) from(X) -> cons(X,n__from(s(X))) from(X) -> n__from(X) minus(X,0()) -> 0() minus(s(X),s(Y)) -> minus(X,Y) quot(0(),s(Y)) -> 0() quot(s(X),s(Y)) -> s(quot(minus(X,Y),s(Y))) zWquot(X1,X2) -> n__zWquot(X1,X2) zWquot(XS,nil()) -> nil() zWquot(cons(X,XS),cons(Y,YS)) -> cons(quot(X,Y),n__zWquot(activate(XS),activate(YS))) zWquot(nil(),XS) -> nil() - Signature: {activate/1,from/1,minus/2,quot/2,sel/2,zWquot/2,activate#/1,from#/1,minus#/2,quot#/2,sel#/2 ,zWquot#/2} / {0/0,cons/2,n__from/1,n__zWquot/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/0,c_5/0,c_6/0,c_7/1,c_8/0 ,c_9/2,c_10/0,c_11/2,c_12/0,c_13/0,c_14/3,c_15/0} - Obligation: innermost runtime complexity wrt. defined symbols {activate#,from#,minus#,quot#,sel# ,zWquot#} and constructors {0,cons,n__from,n__zWquot,nil,s} + Applied Processor: EmptyProcessor + Details: The problem is still open. MAYBE