WORST_CASE(?,O(n^1)) * Step 1: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) -> 0() f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) -> 0() f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) -> 0() f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) -> 0() f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) -> 0() f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + 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: none Following symbols are considered usable: {f0,f1,f2,f3,f4,f5,f6} TcT has computed the following interpretation: p(0) = [0] p(S) = [0] p(f0) = [2] p(f1) = [2] p(f2) = [2] p(f3) = [2] p(f4) = [2] p(f5) = [2] p(f6) = [2] Following rules are strictly oriented: f0(x1,0(),x3,x4,x5) = [2] > [0] = 0() f0(x1,S(x),x3,0(),x5) = [2] > [0] = 0() f1(x1,x2,x3,x4,0()) = [2] > [0] = 0() f2(x1,x2,0(),x4,x5) = [2] > [0] = 0() f2(x1,x2,S(x),0(),0()) = [2] > [0] = 0() f2(x1,x2,S(x'),S(x),0()) = [2] > [0] = 0() f3(x1,x2,x3,x4,0()) = [2] > [0] = 0() f4(0(),x2,x3,x4,x5) = [2] > [0] = 0() f4(S(x),0(),x3,x4,0()) = [2] > [0] = 0() f4(S(x'),S(x),x3,x4,0()) = [2] > [0] = 0() f5(x1,x2,x3,x4,0()) = [2] > [0] = 0() f6(x1,x2,x3,x4,0()) = [2] > [0] = 0() Following rules are (at-least) weakly oriented: f0(x1,S(x'),x3,S(x),x5) = [2] >= [2] = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,S(x)) = [2] >= [2] = f2(x2,x1,x3,x4,x) f2(x1,x2,S(x'),0(),S(x)) = [2] >= [2] = f3(x1,x2,x',0(),x) f2(x1,x2,S(x''),S(x'),S(x)) = [2] >= [2] = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,S(x)) = [2] >= [2] = f4(x1,x2,x4,x3,x) f4(S(x'),0(),x3,x4,S(x)) = [2] >= [2] = f3(x',0(),x3,x4,x) f4(S(x''),S(x'),x3,x4,S(x)) = [2] >= [2] = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,S(x)) = [2] >= [2] = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,S(x)) = [2] >= [2] = f0(x1,x2,x4,x3,x) * Step 2: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Weak TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f1(x1,x2,x3,x4,0()) -> 0() f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),S(x),0()) -> 0() f3(x1,x2,x3,x4,0()) -> 0() f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),S(x),x3,x4,0()) -> 0() f5(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,0()) -> 0() - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + 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: none Following symbols are considered usable: {f0,f1,f2,f3,f4,f5,f6} TcT has computed the following interpretation: p(0) = [0] p(S) = [1] x1 + [1] p(f0) = [4] x4 + [0] p(f1) = [4] x3 + [0] p(f2) = [4] x3 + [0] p(f3) = [4] x3 + [4] x4 + [0] p(f4) = [4] x3 + [4] x4 + [0] p(f5) = [4] x3 + [0] p(f6) = [4] x3 + [0] Following rules are strictly oriented: f0(x1,S(x'),x3,S(x),x5) = [4] x + [4] > [4] x + [0] = f1(x',S(x'),x,S(x),S(x)) f2(x1,x2,S(x'),0(),S(x)) = [4] x' + [4] > [4] x' + [0] = f3(x1,x2,x',0(),x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = [4] x4 + [0] >= [0] = 0() f0(x1,S(x),x3,0(),x5) = [0] >= [0] = 0() f1(x1,x2,x3,x4,0()) = [4] x3 + [0] >= [0] = 0() f1(x1,x2,x3,x4,S(x)) = [4] x3 + [0] >= [4] x3 + [0] = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = [0] >= [0] = 0() f2(x1,x2,S(x),0(),0()) = [4] x + [4] >= [0] = 0() f2(x1,x2,S(x'),S(x),0()) = [4] x' + [4] >= [0] = 0() f2(x1,x2,S(x''),S(x'),S(x)) = [4] x'' + [4] >= [4] x'' + [4] = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = [4] x3 + [4] x4 + [0] >= [0] = 0() f3(x1,x2,x3,x4,S(x)) = [4] x3 + [4] x4 + [0] >= [4] x3 + [4] x4 + [0] = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = [4] x3 + [4] x4 + [0] >= [0] = 0() f4(S(x),0(),x3,x4,0()) = [4] x3 + [4] x4 + [0] >= [0] = 0() f4(S(x'),0(),x3,x4,S(x)) = [4] x3 + [4] x4 + [0] >= [4] x3 + [4] x4 + [0] = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = [4] x3 + [4] x4 + [0] >= [0] = 0() f4(S(x''),S(x'),x3,x4,S(x)) = [4] x3 + [4] x4 + [0] >= [4] x3 + [0] = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = [4] x3 + [0] >= [0] = 0() f5(x1,x2,x3,x4,S(x)) = [4] x3 + [0] >= [4] x3 + [0] = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = [4] x3 + [0] >= [0] = 0() f6(x1,x2,x3,x4,S(x)) = [4] x3 + [0] >= [4] x3 + [0] = f0(x1,x2,x4,x3,x) * Step 3: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Weak TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) -> 0() f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) -> 0() f3(x1,x2,x3,x4,0()) -> 0() f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),S(x),x3,x4,0()) -> 0() f5(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,0()) -> 0() - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + 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: none Following symbols are considered usable: {f0,f1,f2,f3,f4,f5,f6} TcT has computed the following interpretation: p(0) = [0] p(S) = [1] x1 + [1] p(f0) = [4] x2 + [0] p(f1) = [4] x2 + [0] p(f2) = [4] x1 + [0] p(f3) = [4] x1 + [0] p(f4) = [4] x1 + [0] p(f5) = [4] x1 + [0] p(f6) = [4] x2 + [0] Following rules are strictly oriented: f4(S(x'),0(),x3,x4,S(x)) = [4] x' + [4] > [4] x' + [0] = f3(x',0(),x3,x4,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = [0] >= [0] = 0() f0(x1,S(x),x3,0(),x5) = [4] x + [4] >= [0] = 0() f0(x1,S(x'),x3,S(x),x5) = [4] x' + [4] >= [4] x' + [4] = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = [4] x2 + [0] >= [0] = 0() f1(x1,x2,x3,x4,S(x)) = [4] x2 + [0] >= [4] x2 + [0] = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = [4] x1 + [0] >= [0] = 0() f2(x1,x2,S(x),0(),0()) = [4] x1 + [0] >= [0] = 0() f2(x1,x2,S(x'),0(),S(x)) = [4] x1 + [0] >= [4] x1 + [0] = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = [4] x1 + [0] >= [0] = 0() f2(x1,x2,S(x''),S(x'),S(x)) = [4] x1 + [0] >= [4] x1 + [0] = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = [4] x1 + [0] >= [0] = 0() f3(x1,x2,x3,x4,S(x)) = [4] x1 + [0] >= [4] x1 + [0] = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = [0] >= [0] = 0() f4(S(x),0(),x3,x4,0()) = [4] x + [4] >= [0] = 0() f4(S(x'),S(x),x3,x4,0()) = [4] x' + [4] >= [0] = 0() f4(S(x''),S(x'),x3,x4,S(x)) = [4] x'' + [4] >= [4] x'' + [4] = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = [4] x1 + [0] >= [0] = 0() f5(x1,x2,x3,x4,S(x)) = [4] x1 + [0] >= [4] x1 + [0] = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = [4] x2 + [0] >= [0] = 0() f6(x1,x2,x3,x4,S(x)) = [4] x2 + [0] >= [4] x2 + [0] = f0(x1,x2,x4,x3,x) * Step 4: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Weak TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) -> 0() f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) -> 0() f3(x1,x2,x3,x4,0()) -> 0() f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) -> 0() f5(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,0()) -> 0() - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + 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: none Following symbols are considered usable: {f0,f1,f2,f3,f4,f5,f6} TcT has computed the following interpretation: p(0) = 0 p(S) = 2 + x1 p(f0) = x2 + x4 p(f1) = x2 + x3 p(f2) = x1 + x3 p(f3) = 2 + x1 + x3 + x4 p(f4) = x1 + x3 + x4 p(f5) = x1 + x3 p(f6) = x2 + x3 Following rules are strictly oriented: f3(x1,x2,x3,x4,S(x)) = 2 + x1 + x3 + x4 > x1 + x3 + x4 = f4(x1,x2,x4,x3,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = x4 >= 0 = 0() f0(x1,S(x),x3,0(),x5) = 2 + x >= 0 = 0() f0(x1,S(x'),x3,S(x),x5) = 4 + x + x' >= 2 + x + x' = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = x2 + x3 >= 0 = 0() f1(x1,x2,x3,x4,S(x)) = x2 + x3 >= x2 + x3 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = x1 >= 0 = 0() f2(x1,x2,S(x),0(),0()) = 2 + x + x1 >= 0 = 0() f2(x1,x2,S(x'),0(),S(x)) = 2 + x' + x1 >= 2 + x' + x1 = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 2 + x' + x1 >= 0 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 2 + x'' + x1 >= 2 + x'' + x1 = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 2 + x1 + x3 + x4 >= 0 = 0() f4(0(),x2,x3,x4,x5) = x3 + x4 >= 0 = 0() f4(S(x),0(),x3,x4,0()) = 2 + x + x3 + x4 >= 0 = 0() f4(S(x'),0(),x3,x4,S(x)) = 2 + x' + x3 + x4 >= 2 + x' + x3 + x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 2 + x' + x3 + x4 >= 0 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 2 + x'' + x3 + x4 >= 2 + x'' + x3 = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = x1 + x3 >= 0 = 0() f5(x1,x2,x3,x4,S(x)) = x1 + x3 >= x1 + x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = x2 + x3 >= 0 = 0() f6(x1,x2,x3,x4,S(x)) = x2 + x3 >= x2 + x3 = f0(x1,x2,x4,x3,x) * Step 5: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Weak TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) -> 0() f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) -> 0() f3(x1,x2,x3,x4,0()) -> 0() f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) -> 0() f5(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,0()) -> 0() - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + 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: none Following symbols are considered usable: {f0,f1,f2,f3,f4,f5,f6} TcT has computed the following interpretation: p(0) = [0] p(S) = [1] x1 + [4] p(f0) = [1] x2 + [1] x4 + [0] p(f1) = [1] x2 + [1] x3 + [1] p(f2) = [1] x1 + [1] x3 + [0] p(f3) = [1] x1 + [1] x3 + [1] x4 + [0] p(f4) = [1] x1 + [1] x3 + [1] x4 + [0] p(f5) = [1] x1 + [1] x3 + [0] p(f6) = [1] x2 + [1] x3 + [0] Following rules are strictly oriented: f1(x1,x2,x3,x4,S(x)) = [1] x2 + [1] x3 + [1] > [1] x2 + [1] x3 + [0] = f2(x2,x1,x3,x4,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = [1] x4 + [0] >= [0] = 0() f0(x1,S(x),x3,0(),x5) = [1] x + [4] >= [0] = 0() f0(x1,S(x'),x3,S(x),x5) = [1] x + [1] x' + [8] >= [1] x + [1] x' + [5] = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = [1] x2 + [1] x3 + [1] >= [0] = 0() f2(x1,x2,0(),x4,x5) = [1] x1 + [0] >= [0] = 0() f2(x1,x2,S(x),0(),0()) = [1] x + [1] x1 + [4] >= [0] = 0() f2(x1,x2,S(x'),0(),S(x)) = [1] x' + [1] x1 + [4] >= [1] x' + [1] x1 + [0] = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = [1] x' + [1] x1 + [4] >= [0] = 0() f2(x1,x2,S(x''),S(x'),S(x)) = [1] x'' + [1] x1 + [4] >= [1] x'' + [1] x1 + [4] = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = [1] x1 + [1] x3 + [1] x4 + [0] >= [0] = 0() f3(x1,x2,x3,x4,S(x)) = [1] x1 + [1] x3 + [1] x4 + [0] >= [1] x1 + [1] x3 + [1] x4 + [0] = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = [1] x3 + [1] x4 + [0] >= [0] = 0() f4(S(x),0(),x3,x4,0()) = [1] x + [1] x3 + [1] x4 + [4] >= [0] = 0() f4(S(x'),0(),x3,x4,S(x)) = [1] x' + [1] x3 + [1] x4 + [4] >= [1] x' + [1] x3 + [1] x4 + [0] = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = [1] x' + [1] x3 + [1] x4 + [4] >= [0] = 0() f4(S(x''),S(x'),x3,x4,S(x)) = [1] x'' + [1] x3 + [1] x4 + [4] >= [1] x'' + [1] x3 + [4] = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = [1] x1 + [1] x3 + [0] >= [0] = 0() f5(x1,x2,x3,x4,S(x)) = [1] x1 + [1] x3 + [0] >= [1] x1 + [1] x3 + [0] = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = [1] x2 + [1] x3 + [0] >= [0] = 0() f6(x1,x2,x3,x4,S(x)) = [1] x2 + [1] x3 + [0] >= [1] x2 + [1] x3 + [0] = f0(x1,x2,x4,x3,x) * Step 6: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Weak TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) -> 0() f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) -> 0() f3(x1,x2,x3,x4,0()) -> 0() f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) -> 0() f5(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,0()) -> 0() - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + 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: none Following symbols are considered usable: {f0,f1,f2,f3,f4,f5,f6} TcT has computed the following interpretation: p(0) = [0] p(S) = [1] x1 + [4] p(f0) = [2] x2 + [1] x4 + [2] p(f1) = [2] x2 + [1] x3 + [4] p(f2) = [2] x1 + [1] x3 + [4] p(f3) = [2] x1 + [1] x3 + [1] x4 + [5] p(f4) = [2] x1 + [1] x3 + [1] x4 + [5] p(f5) = [2] x1 + [1] x3 + [4] p(f6) = [2] x2 + [1] x3 + [4] Following rules are strictly oriented: f4(S(x''),S(x'),x3,x4,S(x)) = [2] x'' + [1] x3 + [1] x4 + [13] > [2] x'' + [1] x3 + [12] = f2(S(x''),x',x3,x4,x) f6(x1,x2,x3,x4,S(x)) = [2] x2 + [1] x3 + [4] > [2] x2 + [1] x3 + [2] = f0(x1,x2,x4,x3,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = [1] x4 + [2] >= [0] = 0() f0(x1,S(x),x3,0(),x5) = [2] x + [10] >= [0] = 0() f0(x1,S(x'),x3,S(x),x5) = [1] x + [2] x' + [14] >= [1] x + [2] x' + [12] = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = [2] x2 + [1] x3 + [4] >= [0] = 0() f1(x1,x2,x3,x4,S(x)) = [2] x2 + [1] x3 + [4] >= [2] x2 + [1] x3 + [4] = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = [2] x1 + [4] >= [0] = 0() f2(x1,x2,S(x),0(),0()) = [1] x + [2] x1 + [8] >= [0] = 0() f2(x1,x2,S(x'),0(),S(x)) = [1] x' + [2] x1 + [8] >= [1] x' + [2] x1 + [5] = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = [1] x' + [2] x1 + [8] >= [0] = 0() f2(x1,x2,S(x''),S(x'),S(x)) = [1] x'' + [2] x1 + [8] >= [1] x'' + [2] x1 + [8] = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = [2] x1 + [1] x3 + [1] x4 + [5] >= [0] = 0() f3(x1,x2,x3,x4,S(x)) = [2] x1 + [1] x3 + [1] x4 + [5] >= [2] x1 + [1] x3 + [1] x4 + [5] = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = [1] x3 + [1] x4 + [5] >= [0] = 0() f4(S(x),0(),x3,x4,0()) = [2] x + [1] x3 + [1] x4 + [13] >= [0] = 0() f4(S(x'),0(),x3,x4,S(x)) = [2] x' + [1] x3 + [1] x4 + [13] >= [2] x' + [1] x3 + [1] x4 + [5] = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = [2] x' + [1] x3 + [1] x4 + [13] >= [0] = 0() f5(x1,x2,x3,x4,0()) = [2] x1 + [1] x3 + [4] >= [0] = 0() f5(x1,x2,x3,x4,S(x)) = [2] x1 + [1] x3 + [4] >= [2] x1 + [1] x3 + [4] = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = [2] x2 + [1] x3 + [4] >= [0] = 0() * Step 7: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) - Weak TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) -> 0() f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) -> 0() f3(x1,x2,x3,x4,0()) -> 0() f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) -> 0() f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + 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: none Following symbols are considered usable: {f0,f1,f2,f3,f4,f5,f6} TcT has computed the following interpretation: p(0) = [0] p(S) = [1] x1 + [2] p(f0) = [2] x4 + [0] p(f1) = [2] x3 + [4] p(f2) = [2] x3 + [4] p(f3) = [2] x3 + [2] x4 + [6] p(f4) = [2] x3 + [2] x4 + [6] p(f5) = [2] x3 + [1] p(f6) = [2] x3 + [0] Following rules are strictly oriented: f2(x1,x2,S(x''),S(x'),S(x)) = [2] x'' + [8] > [2] x'' + [5] = f5(x1,x2,S(x''),x',x) f5(x1,x2,x3,x4,S(x)) = [2] x3 + [1] > [2] x3 + [0] = f6(x2,x1,x3,x4,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = [2] x4 + [0] >= [0] = 0() f0(x1,S(x),x3,0(),x5) = [0] >= [0] = 0() f0(x1,S(x'),x3,S(x),x5) = [2] x + [4] >= [2] x + [4] = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = [2] x3 + [4] >= [0] = 0() f1(x1,x2,x3,x4,S(x)) = [2] x3 + [4] >= [2] x3 + [4] = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = [4] >= [0] = 0() f2(x1,x2,S(x),0(),0()) = [2] x + [8] >= [0] = 0() f2(x1,x2,S(x'),0(),S(x)) = [2] x' + [8] >= [2] x' + [6] = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = [2] x' + [8] >= [0] = 0() f3(x1,x2,x3,x4,0()) = [2] x3 + [2] x4 + [6] >= [0] = 0() f3(x1,x2,x3,x4,S(x)) = [2] x3 + [2] x4 + [6] >= [2] x3 + [2] x4 + [6] = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = [2] x3 + [2] x4 + [6] >= [0] = 0() f4(S(x),0(),x3,x4,0()) = [2] x3 + [2] x4 + [6] >= [0] = 0() f4(S(x'),0(),x3,x4,S(x)) = [2] x3 + [2] x4 + [6] >= [2] x3 + [2] x4 + [6] = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = [2] x3 + [2] x4 + [6] >= [0] = 0() f4(S(x''),S(x'),x3,x4,S(x)) = [2] x3 + [2] x4 + [6] >= [2] x3 + [4] = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = [2] x3 + [1] >= [0] = 0() f6(x1,x2,x3,x4,0()) = [2] x3 + [0] >= [0] = 0() f6(x1,x2,x3,x4,S(x)) = [2] x3 + [0] >= [2] x3 + [0] = f0(x1,x2,x4,x3,x) * Step 8: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: f0(x1,0(),x3,x4,x5) -> 0() f0(x1,S(x),x3,0(),x5) -> 0() f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) -> 0() f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) -> 0() f2(x1,x2,S(x),0(),0()) -> 0() f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) -> 0() f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) -> 0() f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) -> 0() f4(S(x),0(),x3,x4,0()) -> 0() f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) -> 0() f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) -> 0() f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) -> 0() f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x) - Signature: {f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1} - Obligation: innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))