/export/starexec/sandbox/solver/bin/starexec_run_tct_rc /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),O(n^3)) * Step 1: Sum WORST_CASE(Omega(n^1),O(n^3)) + Considered Problem: - Strict TRS: f(0()) -> true() f(1()) -> false() f(s(x)) -> f(x) g(x,c(y)) -> g(x,g(s(c(y)),y)) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {f/1,g/2,if/3} / {0/0,1/0,c/1,false/0,s/1,true/0} - Obligation: runtime complexity wrt. defined symbols {f,g,if} and constructors {0,1,c,false,s,true} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: f(0()) -> true() f(1()) -> false() f(s(x)) -> f(x) g(x,c(y)) -> g(x,g(s(c(y)),y)) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {f/1,g/2,if/3} / {0/0,1/0,c/1,false/0,s/1,true/0} - Obligation: runtime complexity wrt. defined symbols {f,g,if} and constructors {0,1,c,false,s,true} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: f(x){x -> s(x)} = f(s(x)) ->^+ f(x) = C[f(x) = f(x){}] ** Step 1.b:1: NaturalPI WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: f(0()) -> true() f(1()) -> false() f(s(x)) -> f(x) g(x,c(y)) -> g(x,g(s(c(y)),y)) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {f/1,g/2,if/3} / {0/0,1/0,c/1,false/0,s/1,true/0} - Obligation: runtime complexity wrt. defined symbols {f,g,if} and constructors {0,1,c,false,s,true} + Applied Processor: NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(linear): The following argument positions are considered usable: uargs(g) = {2}, uargs(if) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = 2 p(1) = 0 p(c) = 15 + x1 p(f) = 0 p(false) = 0 p(g) = 5 + x2 p(if) = 2 + x1 + 4*x2 + x3 p(s) = 0 p(true) = 0 Following rules are strictly oriented: g(x,c(y)) = 20 + y > 10 + y = g(x,g(s(c(y)),y)) g(s(x),s(y)) = 5 > 2 = if(f(x),s(x),s(y)) if(false(),x,y) = 2 + 4*x + y > y = y if(true(),x,y) = 2 + 4*x + y > x = x Following rules are (at-least) weakly oriented: f(0()) = 0 >= 0 = true() f(1()) = 0 >= 0 = false() f(s(x)) = 0 >= 0 = f(x) ** Step 1.b:2: NaturalMI WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: f(0()) -> true() f(1()) -> false() f(s(x)) -> f(x) - Weak TRS: g(x,c(y)) -> g(x,g(s(c(y)),y)) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {f/1,g/2,if/3} / {0/0,1/0,c/1,false/0,s/1,true/0} - Obligation: runtime complexity wrt. defined symbols {f,g,if} and constructors {0,1,c,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(g) = {2}, uargs(if) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [1] p(1) = [0] p(c) = [1] x1 + [12] p(f) = [8] p(false) = [6] p(g) = [1] x2 + [8] p(if) = [1] x1 + [8] x2 + [8] x3 + [0] p(s) = [0] p(true) = [8] Following rules are strictly oriented: f(1()) = [8] > [6] = false() Following rules are (at-least) weakly oriented: f(0()) = [8] >= [8] = true() f(s(x)) = [8] >= [8] = f(x) g(x,c(y)) = [1] y + [20] >= [1] y + [16] = g(x,g(s(c(y)),y)) g(s(x),s(y)) = [8] >= [8] = if(f(x),s(x),s(y)) if(false(),x,y) = [8] x + [8] y + [6] >= [1] y + [0] = y if(true(),x,y) = [8] x + [8] y + [8] >= [1] x + [0] = x ** Step 1.b:3: NaturalMI WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: f(0()) -> true() f(s(x)) -> f(x) - Weak TRS: f(1()) -> false() g(x,c(y)) -> g(x,g(s(c(y)),y)) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {f/1,g/2,if/3} / {0/0,1/0,c/1,false/0,s/1,true/0} - Obligation: runtime complexity wrt. defined symbols {f,g,if} and constructors {0,1,c,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(g) = {2}, uargs(if) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [2] p(1) = [8] p(c) = [1] x1 + [2] p(f) = [1] p(false) = [0] p(g) = [1] x1 + [1] x2 + [1] p(if) = [1] x1 + [1] x2 + [1] x3 + [0] p(s) = [1] p(true) = [0] Following rules are strictly oriented: f(0()) = [1] > [0] = true() Following rules are (at-least) weakly oriented: f(1()) = [1] >= [0] = false() f(s(x)) = [1] >= [1] = f(x) g(x,c(y)) = [1] x + [1] y + [3] >= [1] x + [1] y + [3] = g(x,g(s(c(y)),y)) g(s(x),s(y)) = [3] >= [3] = if(f(x),s(x),s(y)) if(false(),x,y) = [1] x + [1] y + [0] >= [1] y + [0] = y if(true(),x,y) = [1] x + [1] y + [0] >= [1] x + [0] = x ** Step 1.b:4: NaturalMI WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: f(s(x)) -> f(x) - Weak TRS: f(0()) -> true() f(1()) -> false() g(x,c(y)) -> g(x,g(s(c(y)),y)) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {f/1,g/2,if/3} / {0/0,1/0,c/1,false/0,s/1,true/0} - Obligation: runtime complexity wrt. defined symbols {f,g,if} and constructors {0,1,c,false,s,true} + Applied Processor: NaturalMI {miDimension = 3, miDegree = 3, 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(g) = {2}, uargs(if) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [1] [0] [0] p(1) = [0] [1] [2] p(c) = [1 3 2] [2] [0 0 0] x1 + [0] [0 0 1] [0] p(f) = [0 1 0] [0] [0 2 0] x1 + [0] [0 0 0] [1] p(false) = [1] [0] [1] p(g) = [2 1 0] [1 0 0] [1] [2 0 0] x1 + [1 0 0] x2 + [3] [0 0 0] [2 0 0] [0] p(if) = [1 0 1] [2 0 0] [1 0 0] [1] [1 0 0] x1 + [1 1 0] x2 + [0 2 0] x3 + [0] [0 0 0] [0 0 2] [1 0 2] [0] p(s) = [0 2 0] [0] [0 1 0] x1 + [1] [0 0 0] [0] p(true) = [0] [0] [0] Following rules are strictly oriented: f(s(x)) = [0 1 0] [1] [0 2 0] x + [2] [0 0 0] [1] > [0 1 0] [0] [0 2 0] x + [0] [0 0 0] [1] = f(x) Following rules are (at-least) weakly oriented: f(0()) = [0] [0] [1] >= [0] [0] [0] = true() f(1()) = [1] [2] [1] >= [1] [0] [1] = false() g(x,c(y)) = [2 1 0] [1 3 2] [3] [2 0 0] x + [1 3 2] y + [5] [0 0 0] [2 6 4] [4] >= [2 1 0] [1 0 0] [3] [2 0 0] x + [1 0 0] y + [5] [0 0 0] [2 0 0] [4] = g(x,g(s(c(y)),y)) g(s(x),s(y)) = [0 5 0] [0 2 0] [2] [0 4 0] x + [0 2 0] y + [3] [0 0 0] [0 4 0] [0] >= [0 5 0] [0 2 0] [2] [0 4 0] x + [0 2 0] y + [3] [0 0 0] [0 2 0] [0] = if(f(x),s(x),s(y)) if(false(),x,y) = [2 0 0] [1 0 0] [3] [1 1 0] x + [0 2 0] y + [1] [0 0 2] [1 0 2] [0] >= [1 0 0] [0] [0 1 0] y + [0] [0 0 1] [0] = y if(true(),x,y) = [2 0 0] [1 0 0] [1] [1 1 0] x + [0 2 0] y + [0] [0 0 2] [1 0 2] [0] >= [1 0 0] [0] [0 1 0] x + [0] [0 0 1] [0] = x ** Step 1.b:5: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: f(0()) -> true() f(1()) -> false() f(s(x)) -> f(x) g(x,c(y)) -> g(x,g(s(c(y)),y)) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Signature: {f/1,g/2,if/3} / {0/0,1/0,c/1,false/0,s/1,true/0} - Obligation: runtime complexity wrt. defined symbols {f,g,if} and constructors {0,1,c,false,s,true} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(Omega(n^1),O(n^3))