/export/starexec/sandbox2/solver/bin/starexec_run_tct_rci /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(1)) * Step 1: Sum. WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: f(x,y,z) -> g(<=(x,y),x,y,z) g(false(),x,y,z) -> f(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) g(true(),x,y,z) -> z p(0()) -> 0() p(s(x)) -> x - Signature: {f/3,g/4,p/1} / {0/0,<=/2,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {f,g,p} and constructors {0,<=,false,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: DependencyPairs. WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: f(x,y,z) -> g(<=(x,y),x,y,z) g(false(),x,y,z) -> f(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) g(true(),x,y,z) -> z p(0()) -> 0() p(s(x)) -> x - Signature: {f/3,g/4,p/1} / {0/0,<=/2,false/0,s/1,true/0} - Obligation: innermost runtime complexity wrt. defined symbols {f,g,p} and constructors {0,<=,false,s,true} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) g#(true(),x,y,z) -> c_3() p#(0()) -> c_4() p#(s(x)) -> c_5() Weak DPs and mark the set of starting terms. * Step 3: PredecessorEstimation. WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) g#(true(),x,y,z) -> c_3() p#(0()) -> c_4() p#(s(x)) -> c_5() - Weak TRS: f(x,y,z) -> g(<=(x,y),x,y,z) g(false(),x,y,z) -> f(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) g(true(),x,y,z) -> z p(0()) -> 0() p(s(x)) -> x - Signature: {f/3,g/4,p/1,f#/3,g#/4,p#/1} / {0/0,<=/2,false/0,s/1,true/0,c_1/1,c_2/7,c_3/0,c_4/0,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#,p#} 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,5} by application of Pre({1,3,4,5}) = {2}. Here rules are labelled as follows: 1: f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) 2: g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) 3: g#(true(),x,y,z) -> c_3() 4: p#(0()) -> c_4() 5: p#(s(x)) -> c_5() * Step 4: PredecessorEstimation. WORST_CASE(?,O(1)) + Considered Problem: - Strict DPs: g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) - Weak DPs: f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) g#(true(),x,y,z) -> c_3() p#(0()) -> c_4() p#(s(x)) -> c_5() - Weak TRS: f(x,y,z) -> g(<=(x,y),x,y,z) g(false(),x,y,z) -> f(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) g(true(),x,y,z) -> z p(0()) -> 0() p(s(x)) -> x - Signature: {f/3,g/4,p/1,f#/3,g#/4,p#/1} / {0/0,<=/2,false/0,s/1,true/0,c_1/1,c_2/7,c_3/0,c_4/0,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#,p#} and constructors {0,<=,false,s,true} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1} by application of Pre({1}) = {}. Here rules are labelled as follows: 1: g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) 2: f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) 3: g#(true(),x,y,z) -> c_3() 4: p#(0()) -> c_4() 5: p#(s(x)) -> c_5() * Step 5: RemoveWeakSuffixes. WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) g#(true(),x,y,z) -> c_3() p#(0()) -> c_4() p#(s(x)) -> c_5() - Weak TRS: f(x,y,z) -> g(<=(x,y),x,y,z) g(false(),x,y,z) -> f(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) g(true(),x,y,z) -> z p(0()) -> 0() p(s(x)) -> x - Signature: {f/3,g/4,p/1,f#/3,g#/4,p#/1} / {0/0,<=/2,false/0,s/1,true/0,c_1/1,c_2/7,c_3/0,c_4/0,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#,p#} and constructors {0,<=,false,s,true} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:W:f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) 2:W:g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) -->_7 p#(s(x)) -> c_5():5 -->_5 p#(s(x)) -> c_5():5 -->_3 p#(s(x)) -> c_5():5 -->_7 p#(0()) -> c_4():4 -->_5 p#(0()) -> c_4():4 -->_3 p#(0()) -> c_4():4 -->_6 f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)):1 -->_4 f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)):1 -->_2 f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)):1 -->_1 f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)):1 3:W:g#(true(),x,y,z) -> c_3() 4:W:p#(0()) -> c_4() 5:W:p#(s(x)) -> c_5() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 3: g#(true(),x,y,z) -> c_3() 2: g#(false(),x,y,z) -> c_2(f#(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) ,f#(p(x),y,z) ,p#(x) ,f#(p(y),z,x) ,p#(y) ,f#(p(z),x,y) ,p#(z)) 4: p#(0()) -> c_4() 5: p#(s(x)) -> c_5() 1: f#(x,y,z) -> c_1(g#(<=(x,y),x,y,z)) * Step 6: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: f(x,y,z) -> g(<=(x,y),x,y,z) g(false(),x,y,z) -> f(f(p(x),y,z),f(p(y),z,x),f(p(z),x,y)) g(true(),x,y,z) -> z p(0()) -> 0() p(s(x)) -> x - Signature: {f/3,g/4,p/1,f#/3,g#/4,p#/1} / {0/0,<=/2,false/0,s/1,true/0,c_1/1,c_2/7,c_3/0,c_4/0,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#,p#} and constructors {0,<=,false,s,true} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(1))