/export/starexec/sandbox/solver/bin/starexec_run_tct_rci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^1)) * Step 1: Sum. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() del(.(x,.(y,z))) -> f(=(x,y),x,y,z) f(false(),x,y,z) -> .(x,del(.(y,z))) f(true(),x,y,z) -> del(.(y,z)) - Signature: {=/2,del/1,f/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0} - Obligation: innermost runtime complexity wrt. defined symbols {=,del,f} and constructors {.,and,false,nil,true,u,v} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: DependencyPairs. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() del(.(x,.(y,z))) -> f(=(x,y),x,y,z) f(false(),x,y,z) -> .(x,del(.(y,z))) f(true(),x,y,z) -> del(.(y,z)) - Signature: {=/2,del/1,f/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0} - Obligation: innermost runtime complexity wrt. defined symbols {=,del,f} and constructors {.,and,false,nil,true,u,v} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs =#(.(x,y),.(u(),v())) -> c_1(=#(x,u()),=#(y,v())) =#(.(x,y),nil()) -> c_2() =#(nil(),.(y,z)) -> c_3() =#(nil(),nil()) -> c_4() del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) Weak DPs and mark the set of starting terms. * Step 3: PredecessorEstimation. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: =#(.(x,y),.(u(),v())) -> c_1(=#(x,u()),=#(y,v())) =#(.(x,y),nil()) -> c_2() =#(nil(),.(y,z)) -> c_3() =#(nil(),nil()) -> c_4() del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) - Weak TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() del(.(x,.(y,z))) -> f(=(x,y),x,y,z) f(false(),x,y,z) -> .(x,del(.(y,z))) f(true(),x,y,z) -> del(.(y,z)) - Signature: {=/2,del/1,f/4,=#/2,del#/1,f#/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0,c_1/2,c_2/0,c_3/0,c_4/0,c_5/2 ,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {=#,del#,f#} and constructors {.,and,false,nil,true,u,v} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,2,3,4} by application of Pre({1,2,3,4}) = {5}. Here rules are labelled as follows: 1: =#(.(x,y),.(u(),v())) -> c_1(=#(x,u()),=#(y,v())) 2: =#(.(x,y),nil()) -> c_2() 3: =#(nil(),.(y,z)) -> c_3() 4: =#(nil(),nil()) -> c_4() 5: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)) 6: f#(false(),x,y,z) -> c_6(del#(.(y,z))) 7: f#(true(),x,y,z) -> c_7(del#(.(y,z))) * Step 4: RemoveWeakSuffixes. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) - Weak DPs: =#(.(x,y),.(u(),v())) -> c_1(=#(x,u()),=#(y,v())) =#(.(x,y),nil()) -> c_2() =#(nil(),.(y,z)) -> c_3() =#(nil(),nil()) -> c_4() - Weak TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() del(.(x,.(y,z))) -> f(=(x,y),x,y,z) f(false(),x,y,z) -> .(x,del(.(y,z))) f(true(),x,y,z) -> del(.(y,z)) - Signature: {=/2,del/1,f/4,=#/2,del#/1,f#/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0,c_1/2,c_2/0,c_3/0,c_4/0,c_5/2 ,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {=#,del#,f#} and constructors {.,and,false,nil,true,u,v} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)) -->_1 f#(true(),x,y,z) -> c_7(del#(.(y,z))):3 -->_1 f#(false(),x,y,z) -> c_6(del#(.(y,z))):2 -->_2 =#(nil(),nil()) -> c_4():7 -->_2 =#(nil(),.(y,z)) -> c_3():6 -->_2 =#(.(x,y),nil()) -> c_2():5 -->_2 =#(.(x,y),.(u(),v())) -> c_1(=#(x,u()),=#(y,v())):4 2:S:f#(false(),x,y,z) -> c_6(del#(.(y,z))) -->_1 del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)):1 3:S:f#(true(),x,y,z) -> c_7(del#(.(y,z))) -->_1 del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)):1 4:W:=#(.(x,y),.(u(),v())) -> c_1(=#(x,u()),=#(y,v())) 5:W:=#(.(x,y),nil()) -> c_2() 6:W:=#(nil(),.(y,z)) -> c_3() 7:W:=#(nil(),nil()) -> c_4() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 4: =#(.(x,y),.(u(),v())) -> c_1(=#(x,u()),=#(y,v())) 5: =#(.(x,y),nil()) -> c_2() 6: =#(nil(),.(y,z)) -> c_3() 7: =#(nil(),nil()) -> c_4() * Step 5: SimplifyRHS. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) - Weak TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() del(.(x,.(y,z))) -> f(=(x,y),x,y,z) f(false(),x,y,z) -> .(x,del(.(y,z))) f(true(),x,y,z) -> del(.(y,z)) - Signature: {=/2,del/1,f/4,=#/2,del#/1,f#/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0,c_1/2,c_2/0,c_3/0,c_4/0,c_5/2 ,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {=#,del#,f#} and constructors {.,and,false,nil,true,u,v} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)) -->_1 f#(true(),x,y,z) -> c_7(del#(.(y,z))):3 -->_1 f#(false(),x,y,z) -> c_6(del#(.(y,z))):2 2:S:f#(false(),x,y,z) -> c_6(del#(.(y,z))) -->_1 del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)):1 3:S:f#(true(),x,y,z) -> c_7(del#(.(y,z))) -->_1 del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z),=#(x,y)):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z)) * Step 6: UsableRules. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) - Weak TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() del(.(x,.(y,z))) -> f(=(x,y),x,y,z) f(false(),x,y,z) -> .(x,del(.(y,z))) f(true(),x,y,z) -> del(.(y,z)) - Signature: {=/2,del/1,f/4,=#/2,del#/1,f#/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0,c_1/2,c_2/0,c_3/0,c_4/0,c_5/1 ,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {=#,del#,f#} and constructors {.,and,false,nil,true,u,v} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) * Step 7: WeightGap. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) - Weak TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() - Signature: {=/2,del/1,f/4,=#/2,del#/1,f#/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0,c_1/2,c_2/0,c_3/0,c_4/0,c_5/1 ,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {=#,del#,f#} and constructors {.,and,false,nil,true,u,v} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following constant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(f#) = {1}, uargs(c_5) = {1}, uargs(c_6) = {1}, uargs(c_7) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(.) = [1] x1 + [1] x2 + [4] p(=) = [3] x1 + [0] p(and) = [1] x1 + [1] x2 + [12] p(del) = [2] x1 + [1] p(f) = [1] x1 + [4] x3 + [1] p(false) = [12] p(nil) = [4] p(true) = [12] p(u) = [2] p(v) = [12] p(=#) = [8] x1 + [1] x2 + [1] p(del#) = [3] x1 + [0] p(f#) = [1] x1 + [3] x3 + [3] x4 + [6] p(c_1) = [0] p(c_2) = [1] p(c_3) = [0] p(c_4) = [0] p(c_5) = [1] x1 + [8] p(c_6) = [1] x1 + [5] p(c_7) = [1] x1 + [8] Following rules are strictly oriented: del#(.(x,.(y,z))) = [3] x + [3] y + [3] z + [24] > [3] x + [3] y + [3] z + [14] = c_5(f#(=(x,y),x,y,z)) f#(false(),x,y,z) = [3] y + [3] z + [18] > [3] y + [3] z + [17] = c_6(del#(.(y,z))) Following rules are (at-least) weakly oriented: f#(true(),x,y,z) = [3] y + [3] z + [18] >= [3] y + [3] z + [20] = c_7(del#(.(y,z))) =(.(x,y),.(u(),v())) = [3] x + [3] y + [12] >= [3] x + [3] y + [12] = and(=(x,u()),=(y,v())) =(.(x,y),nil()) = [3] x + [3] y + [12] >= [12] = false() =(nil(),.(y,z)) = [12] >= [12] = false() =(nil(),nil()) = [12] >= [12] = true() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 8: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: f#(true(),x,y,z) -> c_7(del#(.(y,z))) - Weak DPs: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) - Weak TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() - Signature: {=/2,del/1,f/4,=#/2,del#/1,f#/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0,c_1/2,c_2/0,c_3/0,c_4/0,c_5/1 ,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {=#,del#,f#} and constructors {.,and,false,nil,true,u,v} + 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_5) = {1}, uargs(c_6) = {1}, uargs(c_7) = {1} Following symbols are considered usable: {=,=#,del#,f#} TcT has computed the following interpretation: p(.) = [1] x1 + [1] x2 + [1] p(=) = [1] x1 + [1] p(and) = [0] p(del) = [0] p(f) = [1] x2 + [8] x3 + [2] x4 + [0] p(false) = [1] p(nil) = [0] p(true) = [1] p(u) = [15] p(v) = [7] p(=#) = [1] x2 + [1] p(del#) = [12] x1 + [5] p(f#) = [10] x1 + [2] x2 + [12] x3 + [12] x4 + [8] p(c_1) = [1] x1 + [1] p(c_2) = [1] p(c_3) = [2] p(c_4) = [8] p(c_5) = [1] x1 + [0] p(c_6) = [1] x1 + [1] p(c_7) = [1] x1 + [0] Following rules are strictly oriented: f#(true(),x,y,z) = [2] x + [12] y + [12] z + [18] > [12] y + [12] z + [17] = c_7(del#(.(y,z))) Following rules are (at-least) weakly oriented: del#(.(x,.(y,z))) = [12] x + [12] y + [12] z + [29] >= [12] x + [12] y + [12] z + [18] = c_5(f#(=(x,y),x,y,z)) f#(false(),x,y,z) = [2] x + [12] y + [12] z + [18] >= [12] y + [12] z + [18] = c_6(del#(.(y,z))) =(.(x,y),.(u(),v())) = [1] x + [1] y + [2] >= [0] = and(=(x,u()),=(y,v())) =(.(x,y),nil()) = [1] x + [1] y + [2] >= [1] = false() =(nil(),.(y,z)) = [1] >= [1] = false() =(nil(),nil()) = [1] >= [1] = true() * Step 9: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: del#(.(x,.(y,z))) -> c_5(f#(=(x,y),x,y,z)) f#(false(),x,y,z) -> c_6(del#(.(y,z))) f#(true(),x,y,z) -> c_7(del#(.(y,z))) - Weak TRS: =(.(x,y),.(u(),v())) -> and(=(x,u()),=(y,v())) =(.(x,y),nil()) -> false() =(nil(),.(y,z)) -> false() =(nil(),nil()) -> true() - Signature: {=/2,del/1,f/4,=#/2,del#/1,f#/4} / {./2,and/2,false/0,nil/0,true/0,u/0,v/0,c_1/2,c_2/0,c_3/0,c_4/0,c_5/1 ,c_6/1,c_7/1} - Obligation: innermost runtime complexity wrt. defined symbols {=#,del#,f#} and constructors {.,and,false,nil,true,u,v} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))