MAYBE * Step 1: DependencyPairs MAYBE + Considered Problem: - Strict TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) <=(0(),y) -> true() <=(s(x),0()) -> false() <=(s(x),s(y)) -> <=(x,y) f(0(),y,0(),u) -> true() f(0(),y,s(z),u) -> false() f(s(x),0(),z,u) -> f(x,u,-(z,s(x)),u) f(s(x),s(y),z,u) -> if(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) if(false(),x,y) -> y if(true(),x,y) -> x perfectp(0()) -> false() perfectp(s(x)) -> f(x,s(0()),s(x),s(x)) - Signature: {-/2,<=/2,f/4,if/3,perfectp/1} / {0/0,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {-,<=,f,if,perfectp} and constructors {0,false,s,true} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs -#(x,0()) -> c_1() -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(0(),y) -> c_3() <=#(s(x),0()) -> c_4() <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(0(),y,0(),u) -> c_6() f#(0(),y,s(z),u) -> c_7() f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) if#(false(),x,y) -> c_10() if#(true(),x,y) -> c_11() perfectp#(0()) -> c_12() perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) Weak DPs and mark the set of starting terms. * Step 2: UsableRules MAYBE + Considered Problem: - Strict DPs: -#(x,0()) -> c_1() -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(0(),y) -> c_3() <=#(s(x),0()) -> c_4() <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(0(),y,0(),u) -> c_6() f#(0(),y,s(z),u) -> c_7() f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) if#(false(),x,y) -> c_10() if#(true(),x,y) -> c_11() perfectp#(0()) -> c_12() perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) - Weak TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) <=(0(),y) -> true() <=(s(x),0()) -> false() <=(s(x),s(y)) -> <=(x,y) f(0(),y,0(),u) -> true() f(0(),y,s(z),u) -> false() f(s(x),0(),z,u) -> f(x,u,-(z,s(x)),u) f(s(x),s(y),z,u) -> if(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) if(false(),x,y) -> y if(true(),x,y) -> x perfectp(0()) -> false() perfectp(s(x)) -> f(x,s(0()),s(x),s(x)) - Signature: {-/2,<=/2,f/4,if/3,perfectp/1,-#/2,<=#/2,f#/4,if#/3,perfectp#/1} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/0 ,c_4/0,c_5/1,c_6/0,c_7/0,c_8/2,c_9/5,c_10/0,c_11/0,c_12/0,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {-#,<=#,f#,if#,perfectp#} and constructors {0,false,s ,true} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) <=(0(),y) -> true() <=(s(x),0()) -> false() <=(s(x),s(y)) -> <=(x,y) f(0(),y,0(),u) -> true() f(0(),y,s(z),u) -> false() f(s(x),0(),z,u) -> f(x,u,-(z,s(x)),u) f(s(x),s(y),z,u) -> if(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) if(false(),x,y) -> y if(true(),x,y) -> x -#(x,0()) -> c_1() -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(0(),y) -> c_3() <=#(s(x),0()) -> c_4() <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(0(),y,0(),u) -> c_6() f#(0(),y,s(z),u) -> c_7() f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) if#(false(),x,y) -> c_10() if#(true(),x,y) -> c_11() perfectp#(0()) -> c_12() perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) * Step 3: PredecessorEstimation MAYBE + Considered Problem: - Strict DPs: -#(x,0()) -> c_1() -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(0(),y) -> c_3() <=#(s(x),0()) -> c_4() <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(0(),y,0(),u) -> c_6() f#(0(),y,s(z),u) -> c_7() f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) if#(false(),x,y) -> c_10() if#(true(),x,y) -> c_11() perfectp#(0()) -> c_12() perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) - Weak TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) <=(0(),y) -> true() <=(s(x),0()) -> false() <=(s(x),s(y)) -> <=(x,y) f(0(),y,0(),u) -> true() f(0(),y,s(z),u) -> false() f(s(x),0(),z,u) -> f(x,u,-(z,s(x)),u) f(s(x),s(y),z,u) -> if(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {-/2,<=/2,f/4,if/3,perfectp/1,-#/2,<=#/2,f#/4,if#/3,perfectp#/1} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/0 ,c_4/0,c_5/1,c_6/0,c_7/0,c_8/2,c_9/5,c_10/0,c_11/0,c_12/0,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {-#,<=#,f#,if#,perfectp#} and constructors {0,false,s ,true} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,3,4,6,7,10,11,12} by application of Pre({1,3,4,6,7,10,11,12}) = {2,5,8,9,13}. Here rules are labelled as follows: 1: -#(x,0()) -> c_1() 2: -#(s(x),s(y)) -> c_2(-#(x,y)) 3: <=#(0(),y) -> c_3() 4: <=#(s(x),0()) -> c_4() 5: <=#(s(x),s(y)) -> c_5(<=#(x,y)) 6: f#(0(),y,0(),u) -> c_6() 7: f#(0(),y,s(z),u) -> c_7() 8: f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) 9: f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) 10: if#(false(),x,y) -> c_10() 11: if#(true(),x,y) -> c_11() 12: perfectp#(0()) -> c_12() 13: perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) * Step 4: RemoveWeakSuffixes MAYBE + Considered Problem: - Strict DPs: -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) - Weak DPs: -#(x,0()) -> c_1() <=#(0(),y) -> c_3() <=#(s(x),0()) -> c_4() f#(0(),y,0(),u) -> c_6() f#(0(),y,s(z),u) -> c_7() if#(false(),x,y) -> c_10() if#(true(),x,y) -> c_11() perfectp#(0()) -> c_12() - Weak TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) <=(0(),y) -> true() <=(s(x),0()) -> false() <=(s(x),s(y)) -> <=(x,y) f(0(),y,0(),u) -> true() f(0(),y,s(z),u) -> false() f(s(x),0(),z,u) -> f(x,u,-(z,s(x)),u) f(s(x),s(y),z,u) -> if(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {-/2,<=/2,f/4,if/3,perfectp/1,-#/2,<=#/2,f#/4,if#/3,perfectp#/1} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/0 ,c_4/0,c_5/1,c_6/0,c_7/0,c_8/2,c_9/5,c_10/0,c_11/0,c_12/0,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {-#,<=#,f#,if#,perfectp#} and constructors {0,false,s ,true} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:-#(s(x),s(y)) -> c_2(-#(x,y)) -->_1 -#(x,0()) -> c_1():6 -->_1 -#(s(x),s(y)) -> c_2(-#(x,y)):1 2:S:<=#(s(x),s(y)) -> c_5(<=#(x,y)) -->_1 <=#(s(x),0()) -> c_4():8 -->_1 <=#(0(),y) -> c_3():7 -->_1 <=#(s(x),s(y)) -> c_5(<=#(x,y)):2 3:S:f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) -->_1 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 -->_1 f#(0(),y,s(z),u) -> c_7():10 -->_1 f#(0(),y,0(),u) -> c_6():9 -->_1 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_2 -#(s(x),s(y)) -> c_2(-#(x,y)):1 4:S:f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) -->_1 if#(true(),x,y) -> c_11():12 -->_1 if#(false(),x,y) -> c_10():11 -->_5 f#(0(),y,s(z),u) -> c_7():10 -->_5 f#(0(),y,0(),u) -> c_6():9 -->_2 <=#(s(x),0()) -> c_4():8 -->_2 <=#(0(),y) -> c_3():7 -->_4 -#(x,0()) -> c_1():6 -->_5 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 -->_3 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 -->_5 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_3 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_2 <=#(s(x),s(y)) -> c_5(<=#(x,y)):2 -->_4 -#(s(x),s(y)) -> c_2(-#(x,y)):1 5:S:perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) -->_1 f#(0(),y,s(z),u) -> c_7():10 -->_1 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 6:W:-#(x,0()) -> c_1() 7:W:<=#(0(),y) -> c_3() 8:W:<=#(s(x),0()) -> c_4() 9:W:f#(0(),y,0(),u) -> c_6() 10:W:f#(0(),y,s(z),u) -> c_7() 11:W:if#(false(),x,y) -> c_10() 12:W:if#(true(),x,y) -> c_11() 13:W:perfectp#(0()) -> c_12() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 13: perfectp#(0()) -> c_12() 9: f#(0(),y,0(),u) -> c_6() 10: f#(0(),y,s(z),u) -> c_7() 11: if#(false(),x,y) -> c_10() 12: if#(true(),x,y) -> c_11() 7: <=#(0(),y) -> c_3() 8: <=#(s(x),0()) -> c_4() 6: -#(x,0()) -> c_1() * Step 5: SimplifyRHS MAYBE + Considered Problem: - Strict DPs: -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) - Weak TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) <=(0(),y) -> true() <=(s(x),0()) -> false() <=(s(x),s(y)) -> <=(x,y) f(0(),y,0(),u) -> true() f(0(),y,s(z),u) -> false() f(s(x),0(),z,u) -> f(x,u,-(z,s(x)),u) f(s(x),s(y),z,u) -> if(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {-/2,<=/2,f/4,if/3,perfectp/1,-#/2,<=#/2,f#/4,if#/3,perfectp#/1} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/0 ,c_4/0,c_5/1,c_6/0,c_7/0,c_8/2,c_9/5,c_10/0,c_11/0,c_12/0,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {-#,<=#,f#,if#,perfectp#} and constructors {0,false,s ,true} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:-#(s(x),s(y)) -> c_2(-#(x,y)) -->_1 -#(s(x),s(y)) -> c_2(-#(x,y)):1 2:S:<=#(s(x),s(y)) -> c_5(<=#(x,y)) -->_1 <=#(s(x),s(y)) -> c_5(<=#(x,y)):2 3:S:f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) -->_1 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 -->_1 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_2 -#(s(x),s(y)) -> c_2(-#(x,y)):1 4:S:f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)) -->_5 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 -->_3 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 -->_5 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_3 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_2 <=#(s(x),s(y)) -> c_5(<=#(x,y)):2 -->_4 -#(s(x),s(y)) -> c_2(-#(x,y)):1 5:S:perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) -->_1 f#(s(x),s(y),z,u) -> c_9(if#(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) ,<=#(x,y) ,f#(s(x),-(y,x),z,u) ,-#(y,x) ,f#(x,u,z,u)):4 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)) * Step 6: UsableRules MAYBE + Considered Problem: - Strict DPs: -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)) perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) - Weak TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) <=(0(),y) -> true() <=(s(x),0()) -> false() <=(s(x),s(y)) -> <=(x,y) f(0(),y,0(),u) -> true() f(0(),y,s(z),u) -> false() f(s(x),0(),z,u) -> f(x,u,-(z,s(x)),u) f(s(x),s(y),z,u) -> if(<=(x,y),f(s(x),-(y,x),z,u),f(x,u,z,u)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {-/2,<=/2,f/4,if/3,perfectp/1,-#/2,<=#/2,f#/4,if#/3,perfectp#/1} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/0 ,c_4/0,c_5/1,c_6/0,c_7/0,c_8/2,c_9/4,c_10/0,c_11/0,c_12/0,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {-#,<=#,f#,if#,perfectp#} and constructors {0,false,s ,true} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)) perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) * Step 7: RemoveHeads MAYBE + Considered Problem: - Strict DPs: -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)) perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) - Weak TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) - Signature: {-/2,<=/2,f/4,if/3,perfectp/1,-#/2,<=#/2,f#/4,if#/3,perfectp#/1} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/0 ,c_4/0,c_5/1,c_6/0,c_7/0,c_8/2,c_9/4,c_10/0,c_11/0,c_12/0,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {-#,<=#,f#,if#,perfectp#} and constructors {0,false,s ,true} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:-#(s(x),s(y)) -> c_2(-#(x,y)) -->_1 -#(s(x),s(y)) -> c_2(-#(x,y)):1 2:S:<=#(s(x),s(y)) -> c_5(<=#(x,y)) -->_1 <=#(s(x),s(y)) -> c_5(<=#(x,y)):2 3:S:f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) -->_1 f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)):4 -->_1 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_2 -#(s(x),s(y)) -> c_2(-#(x,y)):1 4:S:f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)) -->_4 f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)):4 -->_2 f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)):4 -->_4 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_2 f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))):3 -->_1 <=#(s(x),s(y)) -> c_5(<=#(x,y)):2 -->_3 -#(s(x),s(y)) -> c_2(-#(x,y)):1 5:S:perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))) -->_1 f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)):4 Following roots of the dependency graph are removed, as the considered set of starting terms is closed under reduction with respect to these rules (modulo compound contexts). [(5,perfectp#(s(x)) -> c_13(f#(x,s(0()),s(x),s(x))))] * Step 8: Failure MAYBE + Considered Problem: - Strict DPs: -#(s(x),s(y)) -> c_2(-#(x,y)) <=#(s(x),s(y)) -> c_5(<=#(x,y)) f#(s(x),0(),z,u) -> c_8(f#(x,u,-(z,s(x)),u),-#(z,s(x))) f#(s(x),s(y),z,u) -> c_9(<=#(x,y),f#(s(x),-(y,x),z,u),-#(y,x),f#(x,u,z,u)) - Weak TRS: -(x,0()) -> x -(s(x),s(y)) -> -(x,y) - Signature: {-/2,<=/2,f/4,if/3,perfectp/1,-#/2,<=#/2,f#/4,if#/3,perfectp#/1} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/0 ,c_4/0,c_5/1,c_6/0,c_7/0,c_8/2,c_9/4,c_10/0,c_11/0,c_12/0,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {-#,<=#,f#,if#,perfectp#} and constructors {0,false,s ,true} + Applied Processor: EmptyProcessor + Details: The problem is still open. MAYBE