MAYBE * Step 1: DependencyPairs MAYBE + Considered Problem: - Strict TRS: assrewrite(exp) -> rewrite(exp) first(Op(x,y)) -> x first(Val(n)) -> Val(n) isOp(Op(x,y)) -> True() isOp(Val(n)) -> False() rewrite(Op(x,y)) -> rw(x,y) rewrite(Val(n)) -> Val(n) rw(Op(x,y),c) -> rw[Let](Op(x,y),c,rewrite(x)) rw(Val(n),c) -> Op(Val(n),rewrite(c)) second(Op(x,y)) -> y - Weak TRS: rw[Let](Op(x,y),c,a1) -> rw[Let][Let](Op(x,y),c,a1,rewrite(y)) rw[Let][Let](ab,c,a1,b1) -> rw[Let][Let][Let](c,a1,b1,rewrite(c)) rw[Let][Let][Let](c,a1,b1,c1) -> rw(a1,Op(b1,c1)) - Signature: {assrewrite/1,first/1,isOp/1,rewrite/1,rw/2,rw[Let]/3,rw[Let][Let]/4,rw[Let][Let][Let]/4 ,second/1} / {False/0,Op/2,True/0,Val/1} - Obligation: innermost runtime complexity wrt. defined symbols {assrewrite,first,isOp,rewrite,rw,rw[Let],rw[Let][Let] ,rw[Let][Let][Let],second} and constructors {False,Op,True,Val} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs assrewrite#(exp) -> c_1(rewrite#(exp)) first#(Op(x,y)) -> c_2() first#(Val(n)) -> c_3() isOp#(Op(x,y)) -> c_4() isOp#(Val(n)) -> c_5() rewrite#(Op(x,y)) -> c_6(rw#(x,y)) rewrite#(Val(n)) -> c_7() rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) rw#(Val(n),c) -> c_9(rewrite#(c)) second#(Op(x,y)) -> c_10() Weak DPs rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) and mark the set of starting terms. * Step 2: UsableRules MAYBE + Considered Problem: - Strict DPs: assrewrite#(exp) -> c_1(rewrite#(exp)) first#(Op(x,y)) -> c_2() first#(Val(n)) -> c_3() isOp#(Op(x,y)) -> c_4() isOp#(Val(n)) -> c_5() rewrite#(Op(x,y)) -> c_6(rw#(x,y)) rewrite#(Val(n)) -> c_7() rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) rw#(Val(n),c) -> c_9(rewrite#(c)) second#(Op(x,y)) -> c_10() - Weak DPs: rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) - Weak TRS: assrewrite(exp) -> rewrite(exp) first(Op(x,y)) -> x first(Val(n)) -> Val(n) isOp(Op(x,y)) -> True() isOp(Val(n)) -> False() rewrite(Op(x,y)) -> rw(x,y) rewrite(Val(n)) -> Val(n) rw(Op(x,y),c) -> rw[Let](Op(x,y),c,rewrite(x)) rw(Val(n),c) -> Op(Val(n),rewrite(c)) rw[Let](Op(x,y),c,a1) -> rw[Let][Let](Op(x,y),c,a1,rewrite(y)) rw[Let][Let](ab,c,a1,b1) -> rw[Let][Let][Let](c,a1,b1,rewrite(c)) rw[Let][Let][Let](c,a1,b1,c1) -> rw(a1,Op(b1,c1)) second(Op(x,y)) -> y - Signature: {assrewrite/1,first/1,isOp/1,rewrite/1,rw/2,rw[Let]/3,rw[Let][Let]/4,rw[Let][Let][Let]/4,second/1 ,assrewrite#/1,first#/1,isOp#/1,rewrite#/1,rw#/2,rw[Let]#/3,rw[Let][Let]#/4,rw[Let][Let][Let]#/4 ,second#/1} / {False/0,Op/2,True/0,Val/1,c_1/1,c_2/0,c_3/0,c_4/0,c_5/0,c_6/1,c_7/0,c_8/2,c_9/1,c_10/0,c_11/2 ,c_12/2,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {assrewrite#,first#,isOp#,rewrite#,rw#,rw[Let]# ,rw[Let][Let]#,rw[Let][Let][Let]#,second#} and constructors {False,Op,True,Val} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: rewrite(Op(x,y)) -> rw(x,y) rewrite(Val(n)) -> Val(n) rw(Op(x,y),c) -> rw[Let](Op(x,y),c,rewrite(x)) rw(Val(n),c) -> Op(Val(n),rewrite(c)) rw[Let](Op(x,y),c,a1) -> rw[Let][Let](Op(x,y),c,a1,rewrite(y)) rw[Let][Let](ab,c,a1,b1) -> rw[Let][Let][Let](c,a1,b1,rewrite(c)) rw[Let][Let][Let](c,a1,b1,c1) -> rw(a1,Op(b1,c1)) assrewrite#(exp) -> c_1(rewrite#(exp)) first#(Op(x,y)) -> c_2() first#(Val(n)) -> c_3() isOp#(Op(x,y)) -> c_4() isOp#(Val(n)) -> c_5() rewrite#(Op(x,y)) -> c_6(rw#(x,y)) rewrite#(Val(n)) -> c_7() rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) rw#(Val(n),c) -> c_9(rewrite#(c)) rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) second#(Op(x,y)) -> c_10() * Step 3: PredecessorEstimation MAYBE + Considered Problem: - Strict DPs: assrewrite#(exp) -> c_1(rewrite#(exp)) first#(Op(x,y)) -> c_2() first#(Val(n)) -> c_3() isOp#(Op(x,y)) -> c_4() isOp#(Val(n)) -> c_5() rewrite#(Op(x,y)) -> c_6(rw#(x,y)) rewrite#(Val(n)) -> c_7() rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) rw#(Val(n),c) -> c_9(rewrite#(c)) second#(Op(x,y)) -> c_10() - Weak DPs: rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) - Weak TRS: rewrite(Op(x,y)) -> rw(x,y) rewrite(Val(n)) -> Val(n) rw(Op(x,y),c) -> rw[Let](Op(x,y),c,rewrite(x)) rw(Val(n),c) -> Op(Val(n),rewrite(c)) rw[Let](Op(x,y),c,a1) -> rw[Let][Let](Op(x,y),c,a1,rewrite(y)) rw[Let][Let](ab,c,a1,b1) -> rw[Let][Let][Let](c,a1,b1,rewrite(c)) rw[Let][Let][Let](c,a1,b1,c1) -> rw(a1,Op(b1,c1)) - Signature: {assrewrite/1,first/1,isOp/1,rewrite/1,rw/2,rw[Let]/3,rw[Let][Let]/4,rw[Let][Let][Let]/4,second/1 ,assrewrite#/1,first#/1,isOp#/1,rewrite#/1,rw#/2,rw[Let]#/3,rw[Let][Let]#/4,rw[Let][Let][Let]#/4 ,second#/1} / {False/0,Op/2,True/0,Val/1,c_1/1,c_2/0,c_3/0,c_4/0,c_5/0,c_6/1,c_7/0,c_8/2,c_9/1,c_10/0,c_11/2 ,c_12/2,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {assrewrite#,first#,isOp#,rewrite#,rw#,rw[Let]# ,rw[Let][Let]#,rw[Let][Let][Let]#,second#} and constructors {False,Op,True,Val} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {2,3,4,5,10} by application of Pre({2,3,4,5,10}) = {}. Here rules are labelled as follows: 1: assrewrite#(exp) -> c_1(rewrite#(exp)) 2: first#(Op(x,y)) -> c_2() 3: first#(Val(n)) -> c_3() 4: isOp#(Op(x,y)) -> c_4() 5: isOp#(Val(n)) -> c_5() 6: rewrite#(Op(x,y)) -> c_6(rw#(x,y)) 7: rewrite#(Val(n)) -> c_7() 8: rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) 9: rw#(Val(n),c) -> c_9(rewrite#(c)) 10: second#(Op(x,y)) -> c_10() 11: rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) 12: rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) 13: rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) * Step 4: RemoveWeakSuffixes MAYBE + Considered Problem: - Strict DPs: assrewrite#(exp) -> c_1(rewrite#(exp)) rewrite#(Op(x,y)) -> c_6(rw#(x,y)) rewrite#(Val(n)) -> c_7() rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) rw#(Val(n),c) -> c_9(rewrite#(c)) - Weak DPs: first#(Op(x,y)) -> c_2() first#(Val(n)) -> c_3() isOp#(Op(x,y)) -> c_4() isOp#(Val(n)) -> c_5() rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) second#(Op(x,y)) -> c_10() - Weak TRS: rewrite(Op(x,y)) -> rw(x,y) rewrite(Val(n)) -> Val(n) rw(Op(x,y),c) -> rw[Let](Op(x,y),c,rewrite(x)) rw(Val(n),c) -> Op(Val(n),rewrite(c)) rw[Let](Op(x,y),c,a1) -> rw[Let][Let](Op(x,y),c,a1,rewrite(y)) rw[Let][Let](ab,c,a1,b1) -> rw[Let][Let][Let](c,a1,b1,rewrite(c)) rw[Let][Let][Let](c,a1,b1,c1) -> rw(a1,Op(b1,c1)) - Signature: {assrewrite/1,first/1,isOp/1,rewrite/1,rw/2,rw[Let]/3,rw[Let][Let]/4,rw[Let][Let][Let]/4,second/1 ,assrewrite#/1,first#/1,isOp#/1,rewrite#/1,rw#/2,rw[Let]#/3,rw[Let][Let]#/4,rw[Let][Let][Let]#/4 ,second#/1} / {False/0,Op/2,True/0,Val/1,c_1/1,c_2/0,c_3/0,c_4/0,c_5/0,c_6/1,c_7/0,c_8/2,c_9/1,c_10/0,c_11/2 ,c_12/2,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {assrewrite#,first#,isOp#,rewrite#,rw#,rw[Let]# ,rw[Let][Let]#,rw[Let][Let][Let]#,second#} and constructors {False,Op,True,Val} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:assrewrite#(exp) -> c_1(rewrite#(exp)) -->_1 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 -->_1 rewrite#(Val(n)) -> c_7():3 2:S:rewrite#(Op(x,y)) -> c_6(rw#(x,y)) -->_1 rw#(Val(n),c) -> c_9(rewrite#(c)):5 -->_1 rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)):4 3:S:rewrite#(Val(n)) -> c_7() 4:S:rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) -->_1 rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)):10 -->_2 rewrite#(Val(n)) -> c_7():3 -->_2 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 5:S:rw#(Val(n),c) -> c_9(rewrite#(c)) -->_1 rewrite#(Val(n)) -> c_7():3 -->_1 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 6:W:first#(Op(x,y)) -> c_2() 7:W:first#(Val(n)) -> c_3() 8:W:isOp#(Op(x,y)) -> c_4() 9:W:isOp#(Val(n)) -> c_5() 10:W:rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) -->_1 rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)):11 -->_2 rewrite#(Val(n)) -> c_7():3 -->_2 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 11:W:rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) -->_1 rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))):12 -->_2 rewrite#(Val(n)) -> c_7():3 -->_2 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 12:W:rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) -->_1 rw#(Val(n),c) -> c_9(rewrite#(c)):5 -->_1 rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)):4 13:W:second#(Op(x,y)) -> c_10() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 13: second#(Op(x,y)) -> c_10() 9: isOp#(Val(n)) -> c_5() 8: isOp#(Op(x,y)) -> c_4() 7: first#(Val(n)) -> c_3() 6: first#(Op(x,y)) -> c_2() * Step 5: RemoveHeads MAYBE + Considered Problem: - Strict DPs: assrewrite#(exp) -> c_1(rewrite#(exp)) rewrite#(Op(x,y)) -> c_6(rw#(x,y)) rewrite#(Val(n)) -> c_7() rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) rw#(Val(n),c) -> c_9(rewrite#(c)) - Weak DPs: rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) - Weak TRS: rewrite(Op(x,y)) -> rw(x,y) rewrite(Val(n)) -> Val(n) rw(Op(x,y),c) -> rw[Let](Op(x,y),c,rewrite(x)) rw(Val(n),c) -> Op(Val(n),rewrite(c)) rw[Let](Op(x,y),c,a1) -> rw[Let][Let](Op(x,y),c,a1,rewrite(y)) rw[Let][Let](ab,c,a1,b1) -> rw[Let][Let][Let](c,a1,b1,rewrite(c)) rw[Let][Let][Let](c,a1,b1,c1) -> rw(a1,Op(b1,c1)) - Signature: {assrewrite/1,first/1,isOp/1,rewrite/1,rw/2,rw[Let]/3,rw[Let][Let]/4,rw[Let][Let][Let]/4,second/1 ,assrewrite#/1,first#/1,isOp#/1,rewrite#/1,rw#/2,rw[Let]#/3,rw[Let][Let]#/4,rw[Let][Let][Let]#/4 ,second#/1} / {False/0,Op/2,True/0,Val/1,c_1/1,c_2/0,c_3/0,c_4/0,c_5/0,c_6/1,c_7/0,c_8/2,c_9/1,c_10/0,c_11/2 ,c_12/2,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {assrewrite#,first#,isOp#,rewrite#,rw#,rw[Let]# ,rw[Let][Let]#,rw[Let][Let][Let]#,second#} and constructors {False,Op,True,Val} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:assrewrite#(exp) -> c_1(rewrite#(exp)) -->_1 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 -->_1 rewrite#(Val(n)) -> c_7():3 2:S:rewrite#(Op(x,y)) -> c_6(rw#(x,y)) -->_1 rw#(Val(n),c) -> c_9(rewrite#(c)):5 -->_1 rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)):4 3:S:rewrite#(Val(n)) -> c_7() 4:S:rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) -->_1 rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)):10 -->_2 rewrite#(Val(n)) -> c_7():3 -->_2 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 5:S:rw#(Val(n),c) -> c_9(rewrite#(c)) -->_1 rewrite#(Val(n)) -> c_7():3 -->_1 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 10:W:rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) -->_1 rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)):11 -->_2 rewrite#(Val(n)) -> c_7():3 -->_2 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 11:W:rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) -->_1 rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))):12 -->_2 rewrite#(Val(n)) -> c_7():3 -->_2 rewrite#(Op(x,y)) -> c_6(rw#(x,y)):2 12:W:rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) -->_1 rw#(Val(n),c) -> c_9(rewrite#(c)):5 -->_1 rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)):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). [(1,assrewrite#(exp) -> c_1(rewrite#(exp)))] * Step 6: Failure MAYBE + Considered Problem: - Strict DPs: rewrite#(Op(x,y)) -> c_6(rw#(x,y)) rewrite#(Val(n)) -> c_7() rw#(Op(x,y),c) -> c_8(rw[Let]#(Op(x,y),c,rewrite(x)),rewrite#(x)) rw#(Val(n),c) -> c_9(rewrite#(c)) - Weak DPs: rw[Let]#(Op(x,y),c,a1) -> c_11(rw[Let][Let]#(Op(x,y),c,a1,rewrite(y)),rewrite#(y)) rw[Let][Let]#(ab,c,a1,b1) -> c_12(rw[Let][Let][Let]#(c,a1,b1,rewrite(c)),rewrite#(c)) rw[Let][Let][Let]#(c,a1,b1,c1) -> c_13(rw#(a1,Op(b1,c1))) - Weak TRS: rewrite(Op(x,y)) -> rw(x,y) rewrite(Val(n)) -> Val(n) rw(Op(x,y),c) -> rw[Let](Op(x,y),c,rewrite(x)) rw(Val(n),c) -> Op(Val(n),rewrite(c)) rw[Let](Op(x,y),c,a1) -> rw[Let][Let](Op(x,y),c,a1,rewrite(y)) rw[Let][Let](ab,c,a1,b1) -> rw[Let][Let][Let](c,a1,b1,rewrite(c)) rw[Let][Let][Let](c,a1,b1,c1) -> rw(a1,Op(b1,c1)) - Signature: {assrewrite/1,first/1,isOp/1,rewrite/1,rw/2,rw[Let]/3,rw[Let][Let]/4,rw[Let][Let][Let]/4,second/1 ,assrewrite#/1,first#/1,isOp#/1,rewrite#/1,rw#/2,rw[Let]#/3,rw[Let][Let]#/4,rw[Let][Let][Let]#/4 ,second#/1} / {False/0,Op/2,True/0,Val/1,c_1/1,c_2/0,c_3/0,c_4/0,c_5/0,c_6/1,c_7/0,c_8/2,c_9/1,c_10/0,c_11/2 ,c_12/2,c_13/1} - Obligation: innermost runtime complexity wrt. defined symbols {assrewrite#,first#,isOp#,rewrite#,rw#,rw[Let]# ,rw[Let][Let]#,rw[Let][Let][Let]#,second#} and constructors {False,Op,True,Val} + Applied Processor: EmptyProcessor + Details: The problem is still open. MAYBE