/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: Sum. 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: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:2: 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: NaturalMI. 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: 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 + [5] p(f) = [0] p(false) = [0] p(g) = [1] x2 + [0] p(if) = [4] x1 + [2] x2 + [1] x3 + [0] p(s) = [0] p(true) = [0] Following rules are strictly oriented: g(x,c(y)) = [1] y + [5] > [1] y + [0] = g(x,g(s(c(y)),y)) Following rules are (at-least) weakly oriented: f(0()) = [0] >= [0] = true() f(1()) = [0] >= [0] = false() f(s(x)) = [0] >= [0] = f(x) g(s(x),s(y)) = [0] >= [0] = if(f(x),s(x),s(y)) if(false(),x,y) = [2] x + [1] y + [0] >= [1] y + [0] = y if(true(),x,y) = [2] x + [1] y + [0] >= [1] x + [0] = x ** Step 1.b:2: NaturalPI. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: f(0()) -> true() f(1()) -> false() f(s(x)) -> f(x) g(s(x),s(y)) -> if(f(x),s(x),s(y)) if(false(),x,y) -> y if(true(),x,y) -> x - Weak TRS: g(x,c(y)) -> g(x,g(s(c(y)),y)) - 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) = 8 p(1) = 0 p(c) = 8 + x1 p(f) = 0 p(false) = 0 p(g) = 8 + x2 p(if) = 5 + 2*x1 + 4*x2 + 8*x3 p(s) = 0 p(true) = 0 Following rules are strictly oriented: g(s(x),s(y)) = 8 > 5 = if(f(x),s(x),s(y)) if(false(),x,y) = 5 + 4*x + 8*y > y = y if(true(),x,y) = 5 + 4*x + 8*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) g(x,c(y)) = 16 + y >= 16 + y = g(x,g(s(c(y)),y)) ** Step 1.b:3: NaturalPI. 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: 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) = 1 p(1) = 2 p(c) = 14 + x1 p(f) = 2 p(false) = 0 p(g) = 10 + x2 p(if) = 1 + 4*x1 + x2 + 8*x3 p(s) = 0 p(true) = 0 Following rules are strictly oriented: f(0()) = 2 > 0 = true() f(1()) = 2 > 0 = false() Following rules are (at-least) weakly oriented: f(s(x)) = 2 >= 2 = f(x) g(x,c(y)) = 24 + y >= 20 + y = g(x,g(s(c(y)),y)) g(s(x),s(y)) = 10 >= 9 = if(f(x),s(x),s(y)) if(false(),x,y) = 1 + x + 8*y >= y = y if(true(),x,y) = 1 + x + 8*y >= x = 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))