/export/starexec/sandbox2/solver/bin/starexec_run_tct_rci /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) cond(true(),x,y) -> cond(gr(x,y),x,add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2} / {0/0,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {add,cond,gr} and constructors {0,false,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) cond(true(),x,y) -> cond(gr(x,y),x,add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2} / {0/0,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {add,cond,gr} and constructors {0,false,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:2: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) cond(true(),x,y) -> cond(gr(x,y),x,add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2} / {0/0,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {add,cond,gr} and constructors {0,false,s,true} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: add(x,y){x -> s(x)} = add(s(x),y) ->^+ s(add(x,y)) = C[add(x,y) = add(x,y){}] ** Step 1.b:1: DependencyPairs. MAYBE + Considered Problem: - Strict TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) cond(true(),x,y) -> cond(gr(x,y),x,add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2} / {0/0,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {add,cond,gr} and constructors {0,false,s,true} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs add#(0(),x) -> c_1() add#(s(x),y) -> c_2(add#(x,y)) cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) gr#(0(),x) -> c_4() gr#(s(x),0()) -> c_5() gr#(s(x),s(y)) -> c_6(gr#(x,y)) Weak DPs and mark the set of starting terms. ** Step 1.b:2: PredecessorEstimation. MAYBE + Considered Problem: - Strict DPs: add#(0(),x) -> c_1() add#(s(x),y) -> c_2(add#(x,y)) cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) gr#(0(),x) -> c_4() gr#(s(x),0()) -> c_5() gr#(s(x),s(y)) -> c_6(gr#(x,y)) - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) cond(true(),x,y) -> cond(gr(x,y),x,add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/3,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,4,5} by application of Pre({1,4,5}) = {2,3,6}. Here rules are labelled as follows: 1: add#(0(),x) -> c_1() 2: add#(s(x),y) -> c_2(add#(x,y)) 3: cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) 4: gr#(0(),x) -> c_4() 5: gr#(s(x),0()) -> c_5() 6: gr#(s(x),s(y)) -> c_6(gr#(x,y)) ** Step 1.b:3: RemoveWeakSuffixes. MAYBE + Considered Problem: - Strict DPs: add#(s(x),y) -> c_2(add#(x,y)) cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) gr#(s(x),s(y)) -> c_6(gr#(x,y)) - Weak DPs: add#(0(),x) -> c_1() gr#(0(),x) -> c_4() gr#(s(x),0()) -> c_5() - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) cond(true(),x,y) -> cond(gr(x,y),x,add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/3,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:add#(s(x),y) -> c_2(add#(x,y)) -->_1 add#(0(),x) -> c_1():4 -->_1 add#(s(x),y) -> c_2(add#(x,y)):1 2:S:cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) -->_2 gr#(s(x),s(y)) -> c_6(gr#(x,y)):3 -->_2 gr#(s(x),0()) -> c_5():6 -->_2 gr#(0(),x) -> c_4():5 -->_3 add#(0(),x) -> c_1():4 -->_1 cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)):2 -->_3 add#(s(x),y) -> c_2(add#(x,y)):1 3:S:gr#(s(x),s(y)) -> c_6(gr#(x,y)) -->_1 gr#(s(x),0()) -> c_5():6 -->_1 gr#(0(),x) -> c_4():5 -->_1 gr#(s(x),s(y)) -> c_6(gr#(x,y)):3 4:W:add#(0(),x) -> c_1() 5:W:gr#(0(),x) -> c_4() 6:W:gr#(s(x),0()) -> c_5() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 5: gr#(0(),x) -> c_4() 6: gr#(s(x),0()) -> c_5() 4: add#(0(),x) -> c_1() ** Step 1.b:4: UsableRules. MAYBE + Considered Problem: - Strict DPs: add#(s(x),y) -> c_2(add#(x,y)) cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) gr#(s(x),s(y)) -> c_6(gr#(x,y)) - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) cond(true(),x,y) -> cond(gr(x,y),x,add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/3,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) add#(s(x),y) -> c_2(add#(x,y)) cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) gr#(s(x),s(y)) -> c_6(gr#(x,y)) ** Step 1.b:5: DecomposeDG. MAYBE + Considered Problem: - Strict DPs: add#(s(x),y) -> c_2(add#(x,y)) cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) gr#(s(x),s(y)) -> c_6(gr#(x,y)) - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/3,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: DecomposeDG {onSelection = all below first cut in WDG, onUpper = Nothing, onLower = Nothing} + Details: We decompose the input problem according to the dependency graph into the upper component cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) and a lower component add#(s(x),y) -> c_2(add#(x,y)) gr#(s(x),s(y)) -> c_6(gr#(x,y)) Further, following extension rules are added to the lower component. cond#(true(),x,y) -> add#(x,y) cond#(true(),x,y) -> cond#(gr(x,y),x,add(x,y)) cond#(true(),x,y) -> gr#(x,y) *** Step 1.b:5.a:1: SimplifyRHS. MAYBE + Considered Problem: - Strict DPs: cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/3,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)) -->_1 cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y)),gr#(x,y),add#(x,y)):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y))) *** Step 1.b:5.a:2: Failure MAYBE + Considered Problem: - Strict DPs: cond#(true(),x,y) -> c_3(cond#(gr(x,y),x,add(x,y))) - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/1,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: EmptyProcessor + Details: The problem is still open. *** Step 1.b:5.b:1: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: add#(s(x),y) -> c_2(add#(x,y)) gr#(s(x),s(y)) -> c_6(gr#(x,y)) - Weak DPs: cond#(true(),x,y) -> add#(x,y) cond#(true(),x,y) -> cond#(gr(x,y),x,add(x,y)) cond#(true(),x,y) -> gr#(x,y) - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/3,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(c_2) = {1}, uargs(c_6) = {1} Following symbols are considered usable: {add#,cond#,gr#} TcT has computed the following interpretation: p(0) = [2] p(add) = [2] x2 + [14] p(cond) = [1] x1 + [2] x3 + [1] p(false) = [0] p(gr) = [8] x2 + [0] p(s) = [1] x1 + [3] p(true) = [0] p(add#) = [4] x1 + [0] p(cond#) = [4] x2 + [8] p(gr#) = [3] x1 + [7] p(c_1) = [8] p(c_2) = [1] x1 + [8] p(c_3) = [2] x1 + [1] x2 + [4] x3 + [2] p(c_4) = [2] p(c_5) = [1] p(c_6) = [1] x1 + [0] Following rules are strictly oriented: add#(s(x),y) = [4] x + [12] > [4] x + [8] = c_2(add#(x,y)) gr#(s(x),s(y)) = [3] x + [16] > [3] x + [7] = c_6(gr#(x,y)) Following rules are (at-least) weakly oriented: cond#(true(),x,y) = [4] x + [8] >= [4] x + [0] = add#(x,y) cond#(true(),x,y) = [4] x + [8] >= [4] x + [8] = cond#(gr(x,y),x,add(x,y)) cond#(true(),x,y) = [4] x + [8] >= [3] x + [7] = gr#(x,y) *** Step 1.b:5.b:2: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: add#(s(x),y) -> c_2(add#(x,y)) cond#(true(),x,y) -> add#(x,y) cond#(true(),x,y) -> cond#(gr(x,y),x,add(x,y)) cond#(true(),x,y) -> gr#(x,y) gr#(s(x),s(y)) -> c_6(gr#(x,y)) - Weak TRS: add(0(),x) -> x add(s(x),y) -> s(add(x,y)) gr(0(),x) -> false() gr(s(x),0()) -> true() gr(s(x),s(y)) -> gr(x,y) - Signature: {add/2,cond/3,gr/2,add#/2,cond#/3,gr#/2} / {0/0,false/0,s/1,true/0,c_1/0,c_2/1,c_3/3,c_4/0,c_5/0,c_6/1} - Obligation: innermost runtime complexity wrt. defined symbols {add#,cond#,gr#} and constructors {0,false,s,true} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(Omega(n^1),?)