WORST_CASE(?,O(n^1)) * Step 1: Sum 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: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: NaturalPI 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: 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) = 0 p(f0) = 2 p(f1) = 2 + 2*x2 p(f2) = 2 + 2*x1 p(f3) = 2 p(f4) = 2 p(f5) = 2 + x1 + x3 p(f6) = 2 + x3 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 + 2*x2 > 0 = 0() f2(x1,x2,0(),x4,x5) = 2 + 2*x1 > 0 = 0() f2(x1,x2,S(x),0(),0()) = 2 + 2*x1 > 0 = 0() f2(x1,x2,S(x'),S(x),0()) = 2 + 2*x1 > 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 + x1 + x3 > 0 = 0() f6(x1,x2,x3,x4,0()) = 2 + x3 > 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*x2 >= 2 + 2*x2 = f2(x2,x1,x3,x4,x) f2(x1,x2,S(x'),0(),S(x)) = 2 + 2*x1 >= 2 = f3(x1,x2,x',0(),x) f2(x1,x2,S(x''),S(x'),S(x)) = 2 + 2*x1 >= 2 + x1 = 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 + x1 + x3 >= 2 + x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,S(x)) = 2 + x3 >= 2 = f0(x1,x2,x4,x3,x) * Step 3: NaturalPI 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: 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) = 4 + x1 p(f0) = 2*x4 p(f1) = 2*x3 p(f2) = 2*x3 p(f3) = 2*x3 + 2*x4 p(f4) = 2*x3 + 2*x4 p(f5) = 2*x3 p(f6) = 2*x3 Following rules are strictly oriented: f0(x1,S(x'),x3,S(x),x5) = 8 + 2*x > 2*x = f1(x',S(x'),x,S(x),S(x)) f2(x1,x2,S(x'),0(),S(x)) = 8 + 2*x' > 2*x' = f3(x1,x2,x',0(),x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 2*x4 >= 0 = 0() f0(x1,S(x),x3,0(),x5) = 0 >= 0 = 0() f1(x1,x2,x3,x4,0()) = 2*x3 >= 0 = 0() f1(x1,x2,x3,x4,S(x)) = 2*x3 >= 2*x3 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = 0 >= 0 = 0() f2(x1,x2,S(x),0(),0()) = 8 + 2*x >= 0 = 0() f2(x1,x2,S(x'),S(x),0()) = 8 + 2*x' >= 0 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 8 + 2*x'' >= 8 + 2*x'' = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 2*x3 + 2*x4 >= 0 = 0() f3(x1,x2,x3,x4,S(x)) = 2*x3 + 2*x4 >= 2*x3 + 2*x4 = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = 2*x3 + 2*x4 >= 0 = 0() f4(S(x),0(),x3,x4,0()) = 2*x3 + 2*x4 >= 0 = 0() f4(S(x'),0(),x3,x4,S(x)) = 2*x3 + 2*x4 >= 2*x3 + 2*x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 2*x3 + 2*x4 >= 0 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 2*x3 + 2*x4 >= 2*x3 = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = 2*x3 >= 0 = 0() f5(x1,x2,x3,x4,S(x)) = 2*x3 >= 2*x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = 2*x3 >= 0 = 0() f6(x1,x2,x3,x4,S(x)) = 2*x3 >= 2*x3 = 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'),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: 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) = 2 p(S) = 4 + x1 p(f0) = 3 + 2*x2 p(f1) = 3 + 2*x2 p(f2) = 3 + 2*x1 p(f3) = 3 + 2*x1 p(f4) = 3 + 2*x1 p(f5) = 3 + 2*x1 p(f6) = 3 + 2*x2 Following rules are strictly oriented: f4(S(x'),0(),x3,x4,S(x)) = 11 + 2*x' > 3 + 2*x' = f3(x',0(),x3,x4,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 7 >= 2 = 0() f0(x1,S(x),x3,0(),x5) = 11 + 2*x >= 2 = 0() f0(x1,S(x'),x3,S(x),x5) = 11 + 2*x' >= 11 + 2*x' = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = 3 + 2*x2 >= 2 = 0() f1(x1,x2,x3,x4,S(x)) = 3 + 2*x2 >= 3 + 2*x2 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = 3 + 2*x1 >= 2 = 0() f2(x1,x2,S(x),0(),0()) = 3 + 2*x1 >= 2 = 0() f2(x1,x2,S(x'),0(),S(x)) = 3 + 2*x1 >= 3 + 2*x1 = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 3 + 2*x1 >= 2 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 3 + 2*x1 >= 3 + 2*x1 = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 3 + 2*x1 >= 2 = 0() f3(x1,x2,x3,x4,S(x)) = 3 + 2*x1 >= 3 + 2*x1 = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = 7 >= 2 = 0() f4(S(x),0(),x3,x4,0()) = 11 + 2*x >= 2 = 0() f4(S(x'),S(x),x3,x4,0()) = 11 + 2*x' >= 2 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 11 + 2*x'' >= 11 + 2*x'' = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = 3 + 2*x1 >= 2 = 0() f5(x1,x2,x3,x4,S(x)) = 3 + 2*x1 >= 3 + 2*x1 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = 3 + 2*x2 >= 2 = 0() f6(x1,x2,x3,x4,S(x)) = 3 + 2*x2 >= 3 + 2*x2 = f0(x1,x2,x4,x3,x) * Step 5: 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) = 1 + x1 p(f0) = 4*x4 p(f1) = 4 + 4*x3 p(f2) = 4*x3 p(f3) = 4*x3 + 4*x4 p(f4) = 4*x3 + 4*x4 p(f5) = 4*x3 p(f6) = 4*x3 Following rules are strictly oriented: f1(x1,x2,x3,x4,S(x)) = 4 + 4*x3 > 4*x3 = f2(x2,x1,x3,x4,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 4*x4 >= 0 = 0() f0(x1,S(x),x3,0(),x5) = 0 >= 0 = 0() f0(x1,S(x'),x3,S(x),x5) = 4 + 4*x >= 4 + 4*x = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = 4 + 4*x3 >= 0 = 0() f2(x1,x2,0(),x4,x5) = 0 >= 0 = 0() f2(x1,x2,S(x),0(),0()) = 4 + 4*x >= 0 = 0() f2(x1,x2,S(x'),0(),S(x)) = 4 + 4*x' >= 4*x' = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 4 + 4*x' >= 0 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 4 + 4*x'' >= 4 + 4*x'' = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 4*x3 + 4*x4 >= 0 = 0() f3(x1,x2,x3,x4,S(x)) = 4*x3 + 4*x4 >= 4*x3 + 4*x4 = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = 4*x3 + 4*x4 >= 0 = 0() f4(S(x),0(),x3,x4,0()) = 4*x3 + 4*x4 >= 0 = 0() f4(S(x'),0(),x3,x4,S(x)) = 4*x3 + 4*x4 >= 4*x3 + 4*x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 4*x3 + 4*x4 >= 0 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 4*x3 + 4*x4 >= 4*x3 = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = 4*x3 >= 0 = 0() f5(x1,x2,x3,x4,S(x)) = 4*x3 >= 4*x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = 4*x3 >= 0 = 0() f6(x1,x2,x3,x4,S(x)) = 4*x3 >= 4*x3 = f0(x1,x2,x4,x3,x) * Step 6: NaturalPI 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) 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() 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() 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) = 4*x4 p(f1) = 4*x3 p(f2) = 4*x3 p(f3) = 6 + 4*x3 + 4*x4 p(f4) = 6 + 4*x3 + 4*x4 p(f5) = 4*x3 p(f6) = 4*x3 Following rules are strictly oriented: f4(S(x''),S(x'),x3,x4,S(x)) = 6 + 4*x3 + 4*x4 > 4*x3 = f2(S(x''),x',x3,x4,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 4*x4 >= 0 = 0() f0(x1,S(x),x3,0(),x5) = 0 >= 0 = 0() f0(x1,S(x'),x3,S(x),x5) = 8 + 4*x >= 4*x = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = 4*x3 >= 0 = 0() f1(x1,x2,x3,x4,S(x)) = 4*x3 >= 4*x3 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = 0 >= 0 = 0() f2(x1,x2,S(x),0(),0()) = 8 + 4*x >= 0 = 0() f2(x1,x2,S(x'),0(),S(x)) = 8 + 4*x' >= 6 + 4*x' = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 8 + 4*x' >= 0 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 8 + 4*x'' >= 8 + 4*x'' = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 6 + 4*x3 + 4*x4 >= 0 = 0() f3(x1,x2,x3,x4,S(x)) = 6 + 4*x3 + 4*x4 >= 6 + 4*x3 + 4*x4 = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = 6 + 4*x3 + 4*x4 >= 0 = 0() f4(S(x),0(),x3,x4,0()) = 6 + 4*x3 + 4*x4 >= 0 = 0() f4(S(x'),0(),x3,x4,S(x)) = 6 + 4*x3 + 4*x4 >= 6 + 4*x3 + 4*x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 6 + 4*x3 + 4*x4 >= 0 = 0() f5(x1,x2,x3,x4,0()) = 4*x3 >= 0 = 0() f5(x1,x2,x3,x4,S(x)) = 4*x3 >= 4*x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = 4*x3 >= 0 = 0() f6(x1,x2,x3,x4,S(x)) = 4*x3 >= 4*x3 = f0(x1,x2,x4,x3,x) * Step 7: NaturalPI 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) f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,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() 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() - 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) = 2 p(S) = 2 + x1 p(f0) = 2 + 4*x4 p(f1) = 4 + 4*x3 p(f2) = 3 + 4*x3 p(f3) = 3 + 4*x3 + 4*x4 p(f4) = 3 + 4*x3 + 4*x4 p(f5) = 2 + 4*x3 p(f6) = 2 + 4*x3 Following rules are strictly oriented: f2(x1,x2,S(x''),S(x'),S(x)) = 11 + 4*x'' > 10 + 4*x'' = f5(x1,x2,S(x''),x',x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 2 + 4*x4 >= 2 = 0() f0(x1,S(x),x3,0(),x5) = 10 >= 2 = 0() f0(x1,S(x'),x3,S(x),x5) = 10 + 4*x >= 4 + 4*x = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = 4 + 4*x3 >= 2 = 0() f1(x1,x2,x3,x4,S(x)) = 4 + 4*x3 >= 3 + 4*x3 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = 11 >= 2 = 0() f2(x1,x2,S(x),0(),0()) = 11 + 4*x >= 2 = 0() f2(x1,x2,S(x'),0(),S(x)) = 11 + 4*x' >= 11 + 4*x' = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 11 + 4*x' >= 2 = 0() f3(x1,x2,x3,x4,0()) = 3 + 4*x3 + 4*x4 >= 2 = 0() f3(x1,x2,x3,x4,S(x)) = 3 + 4*x3 + 4*x4 >= 3 + 4*x3 + 4*x4 = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = 3 + 4*x3 + 4*x4 >= 2 = 0() f4(S(x),0(),x3,x4,0()) = 3 + 4*x3 + 4*x4 >= 2 = 0() f4(S(x'),0(),x3,x4,S(x)) = 3 + 4*x3 + 4*x4 >= 3 + 4*x3 + 4*x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 3 + 4*x3 + 4*x4 >= 2 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 3 + 4*x3 + 4*x4 >= 3 + 4*x3 = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = 2 + 4*x3 >= 2 = 0() f5(x1,x2,x3,x4,S(x)) = 2 + 4*x3 >= 2 + 4*x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = 2 + 4*x3 >= 2 = 0() f6(x1,x2,x3,x4,S(x)) = 2 + 4*x3 >= 2 + 4*x3 = f0(x1,x2,x4,x3,x) * Step 8: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,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() f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x) 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() 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() - 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) = 1 + x1 p(f0) = 4*x2 + 4*x4 p(f1) = 4*x2 + 4*x3 p(f2) = 4*x1 + 4*x3 p(f3) = 4 + 4*x1 + 4*x3 + 4*x4 p(f4) = 4*x1 + 4*x3 + 4*x4 p(f5) = 4*x1 + 4*x3 p(f6) = 4*x2 + 4*x3 Following rules are strictly oriented: f3(x1,x2,x3,x4,S(x)) = 4 + 4*x1 + 4*x3 + 4*x4 > 4*x1 + 4*x3 + 4*x4 = f4(x1,x2,x4,x3,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 4*x4 >= 0 = 0() f0(x1,S(x),x3,0(),x5) = 4 + 4*x >= 0 = 0() f0(x1,S(x'),x3,S(x),x5) = 8 + 4*x + 4*x' >= 4 + 4*x + 4*x' = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = 4*x2 + 4*x3 >= 0 = 0() f1(x1,x2,x3,x4,S(x)) = 4*x2 + 4*x3 >= 4*x2 + 4*x3 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = 4*x1 >= 0 = 0() f2(x1,x2,S(x),0(),0()) = 4 + 4*x + 4*x1 >= 0 = 0() f2(x1,x2,S(x'),0(),S(x)) = 4 + 4*x' + 4*x1 >= 4 + 4*x' + 4*x1 = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 4 + 4*x' + 4*x1 >= 0 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 4 + 4*x'' + 4*x1 >= 4 + 4*x'' + 4*x1 = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 4 + 4*x1 + 4*x3 + 4*x4 >= 0 = 0() f4(0(),x2,x3,x4,x5) = 4*x3 + 4*x4 >= 0 = 0() f4(S(x),0(),x3,x4,0()) = 4 + 4*x + 4*x3 + 4*x4 >= 0 = 0() f4(S(x'),0(),x3,x4,S(x)) = 4 + 4*x' + 4*x3 + 4*x4 >= 4 + 4*x' + 4*x3 + 4*x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 4 + 4*x' + 4*x3 + 4*x4 >= 0 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 4 + 4*x'' + 4*x3 + 4*x4 >= 4 + 4*x'' + 4*x3 = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = 4*x1 + 4*x3 >= 0 = 0() f5(x1,x2,x3,x4,S(x)) = 4*x1 + 4*x3 >= 4*x1 + 4*x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = 4*x2 + 4*x3 >= 0 = 0() f6(x1,x2,x3,x4,S(x)) = 4*x2 + 4*x3 >= 4*x2 + 4*x3 = f0(x1,x2,x4,x3,x) * Step 9: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: 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() 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() 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) = 1 + x1 p(f0) = 3 + x4 p(f1) = 4 + x3 p(f2) = 4 + x3 p(f3) = 4 + x3 + x4 p(f4) = 4 + x3 + x4 p(f5) = 4 + x3 p(f6) = 4 + x3 Following rules are strictly oriented: f6(x1,x2,x3,x4,S(x)) = 4 + x3 > 3 + x3 = f0(x1,x2,x4,x3,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 3 + x4 >= 0 = 0() f0(x1,S(x),x3,0(),x5) = 3 >= 0 = 0() f0(x1,S(x'),x3,S(x),x5) = 4 + x >= 4 + x = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = 4 + x3 >= 0 = 0() f1(x1,x2,x3,x4,S(x)) = 4 + x3 >= 4 + x3 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = 4 >= 0 = 0() f2(x1,x2,S(x),0(),0()) = 5 + x >= 0 = 0() f2(x1,x2,S(x'),0(),S(x)) = 5 + x' >= 4 + x' = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 5 + x' >= 0 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 5 + x'' >= 5 + x'' = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 4 + x3 + x4 >= 0 = 0() f3(x1,x2,x3,x4,S(x)) = 4 + x3 + x4 >= 4 + x3 + x4 = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = 4 + x3 + x4 >= 0 = 0() f4(S(x),0(),x3,x4,0()) = 4 + x3 + x4 >= 0 = 0() f4(S(x'),0(),x3,x4,S(x)) = 4 + x3 + x4 >= 4 + x3 + x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 4 + x3 + x4 >= 0 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 4 + x3 + x4 >= 4 + x3 = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = 4 + x3 >= 0 = 0() f5(x1,x2,x3,x4,S(x)) = 4 + x3 >= 4 + x3 = f6(x2,x1,x3,x4,x) f6(x1,x2,x3,x4,0()) = 4 + x3 >= 0 = 0() * Step 10: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: 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() 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() 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: 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) = 2*x4 p(f1) = 1 + 2*x3 p(f2) = 1 + 2*x3 p(f3) = 4 + 2*x3 + 2*x4 p(f4) = 4 + 2*x3 + 2*x4 p(f5) = 1 + 2*x3 p(f6) = 2*x3 Following rules are strictly oriented: f5(x1,x2,x3,x4,S(x)) = 1 + 2*x3 > 2*x3 = f6(x2,x1,x3,x4,x) Following rules are (at-least) weakly oriented: f0(x1,0(),x3,x4,x5) = 2*x4 >= 0 = 0() f0(x1,S(x),x3,0(),x5) = 0 >= 0 = 0() f0(x1,S(x'),x3,S(x),x5) = 4 + 2*x >= 1 + 2*x = f1(x',S(x'),x,S(x),S(x)) f1(x1,x2,x3,x4,0()) = 1 + 2*x3 >= 0 = 0() f1(x1,x2,x3,x4,S(x)) = 1 + 2*x3 >= 1 + 2*x3 = f2(x2,x1,x3,x4,x) f2(x1,x2,0(),x4,x5) = 1 >= 0 = 0() f2(x1,x2,S(x),0(),0()) = 5 + 2*x >= 0 = 0() f2(x1,x2,S(x'),0(),S(x)) = 5 + 2*x' >= 4 + 2*x' = f3(x1,x2,x',0(),x) f2(x1,x2,S(x'),S(x),0()) = 5 + 2*x' >= 0 = 0() f2(x1,x2,S(x''),S(x'),S(x)) = 5 + 2*x'' >= 5 + 2*x'' = f5(x1,x2,S(x''),x',x) f3(x1,x2,x3,x4,0()) = 4 + 2*x3 + 2*x4 >= 0 = 0() f3(x1,x2,x3,x4,S(x)) = 4 + 2*x3 + 2*x4 >= 4 + 2*x3 + 2*x4 = f4(x1,x2,x4,x3,x) f4(0(),x2,x3,x4,x5) = 4 + 2*x3 + 2*x4 >= 0 = 0() f4(S(x),0(),x3,x4,0()) = 4 + 2*x3 + 2*x4 >= 0 = 0() f4(S(x'),0(),x3,x4,S(x)) = 4 + 2*x3 + 2*x4 >= 4 + 2*x3 + 2*x4 = f3(x',0(),x3,x4,x) f4(S(x'),S(x),x3,x4,0()) = 4 + 2*x3 + 2*x4 >= 0 = 0() f4(S(x''),S(x'),x3,x4,S(x)) = 4 + 2*x3 + 2*x4 >= 1 + 2*x3 = f2(S(x''),x',x3,x4,x) f5(x1,x2,x3,x4,0()) = 1 + 2*x3 >= 0 = 0() f6(x1,x2,x3,x4,0()) = 2*x3 >= 0 = 0() f6(x1,x2,x3,x4,S(x)) = 2*x3 >= 2*x3 = f0(x1,x2,x4,x3,x) * Step 11: 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))