(0) Obligation:

Clauses:

ordered([]).
ordered(.(X1, [])).
ordered(Xs) :- ','(no(max1el_list(Xs)), ','(head(Xs, X), ','(tail(Xs, Ys), ','(head(Ys, Y), ','(tail(Ys, Zs), ','(less(X, s(Y)), ordered(.(Y, Zs)))))))).
head([], X2).
head(.(X, X3), X).
tail([], []).
tail(.(X4, Xs), Xs).
less(0, s(X5)).
less(X, Y) :- ','(no(zero(X)), ','(p(X, Px), ','(p(Y, Py), less(Px, Py)))).
p(0, 0).
p(s(X), X).
max1el_list([]).
max1el_list(.(X6, [])).
zero(0).
no(X) :- ','(X, ','(!, failure(a))).
no(X7).
failure(b).

Query: ordered(g)

(1) PrologToCdtProblemTransformerProof (UPPER BOUND (ID) transformation)

Built complexity over-approximating cdt problems from derivation graph.

(2) Obligation:

Complexity Dependency Tuples Problem
Rules:

f1_in([]) → f1_out1
f1_in(.(z0, [])) → f1_out1
f1_in(.(z0, .(z1, z2))) → U1(f104_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f104_out1, .(z0, .(z1, z2))) → f1_out1
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
U5(f158_out1, s(z0), z1) → f105_out1
f104_in(z0, z1, z2) → U6(f105_in(z0, z1), z0, z1, z2)
U6(f105_out1, z0, z1, z2) → U7(f1_in(.(z1, z2)), z0, z1, z2)
U7(f1_out1, z0, z1, z2) → f104_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U8(f228_out1, z0, z1) → f223_out1
U8(z0, f229_out1(z1), z2) → f223_out2(z1)
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U9(f228_out1, z0, z1) → f272_out1
U9(z0, f278_out1(z1), z2) → f272_out2(z1)
Tuples:

F1_IN(.(z0, .(z1, z2))) → c2(U1'(f104_in(z0, z1, z2), .(z0, .(z1, z2))), F104_IN(z0, z1, z2))
F158_IN(s(z0), 0) → c5(U2'(f223_in(z0), s(z0), 0), F223_IN(z0))
F158_IN(s(z0), s(z1)) → c6(U3'(f158_in(z0, z1), s(z0), s(z1)), F158_IN(z0, z1))
F228_IN(s(z0)) → c10(U4'(f272_in(z0), s(z0)), F272_IN(z0))
F105_IN(s(z0), z1) → c14(U5'(f158_in(z0, z1), s(z0), z1), F158_IN(z0, z1))
F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
U6'(f105_out1, z0, z1, z2) → c17(U7'(f1_in(.(z1, z2)), z0, z1, z2), F1_IN(.(z1, z2)))
F223_IN(z0) → c19(U8'(f228_in(z0), f229_in(z0), z0), F228_IN(z0))
F272_IN(z0) → c22(U9'(f228_in(z0), f278_in(z0), z0), F228_IN(z0))
S tuples:

F1_IN(.(z0, .(z1, z2))) → c2(U1'(f104_in(z0, z1, z2), .(z0, .(z1, z2))), F104_IN(z0, z1, z2))
F158_IN(s(z0), 0) → c5(U2'(f223_in(z0), s(z0), 0), F223_IN(z0))
F158_IN(s(z0), s(z1)) → c6(U3'(f158_in(z0, z1), s(z0), s(z1)), F158_IN(z0, z1))
F228_IN(s(z0)) → c10(U4'(f272_in(z0), s(z0)), F272_IN(z0))
F105_IN(s(z0), z1) → c14(U5'(f158_in(z0, z1), s(z0), z1), F158_IN(z0, z1))
F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
U6'(f105_out1, z0, z1, z2) → c17(U7'(f1_in(.(z1, z2)), z0, z1, z2), F1_IN(.(z1, z2)))
F223_IN(z0) → c19(U8'(f228_in(z0), f229_in(z0), z0), F228_IN(z0))
F272_IN(z0) → c22(U9'(f228_in(z0), f278_in(z0), z0), F228_IN(z0))
K tuples:none
Defined Rule Symbols:

f1_in, U1, f158_in, U2, U3, f228_in, U4, f105_in, U5, f104_in, U6, U7, f223_in, U8, f272_in, U9

Defined Pair Symbols:

F1_IN, F158_IN, F228_IN, F105_IN, F104_IN, U6', F223_IN, F272_IN

Compound Symbols:

c2, c5, c6, c10, c14, c16, c17, c19, c22

(3) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID) transformation)

Split RHS of tuples not part of any SCC

(4) Obligation:

Complexity Dependency Tuples Problem
Rules:

f1_in([]) → f1_out1
f1_in(.(z0, [])) → f1_out1
f1_in(.(z0, .(z1, z2))) → U1(f104_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f104_out1, .(z0, .(z1, z2))) → f1_out1
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
U5(f158_out1, s(z0), z1) → f105_out1
f104_in(z0, z1, z2) → U6(f105_in(z0, z1), z0, z1, z2)
U6(f105_out1, z0, z1, z2) → U7(f1_in(.(z1, z2)), z0, z1, z2)
U7(f1_out1, z0, z1, z2) → f104_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U8(f228_out1, z0, z1) → f223_out1
U8(z0, f229_out1(z1), z2) → f223_out2(z1)
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U9(f228_out1, z0, z1) → f272_out1
U9(z0, f278_out1(z1), z2) → f272_out2(z1)
Tuples:

F1_IN(.(z0, .(z1, z2))) → c2(U1'(f104_in(z0, z1, z2), .(z0, .(z1, z2))), F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(U3'(f158_in(z0, z1), s(z0), s(z1)), F158_IN(z0, z1))
F228_IN(s(z0)) → c10(U4'(f272_in(z0), s(z0)), F272_IN(z0))
F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
U6'(f105_out1, z0, z1, z2) → c17(U7'(f1_in(.(z1, z2)), z0, z1, z2), F1_IN(.(z1, z2)))
F272_IN(z0) → c22(U9'(f228_in(z0), f278_in(z0), z0), F228_IN(z0))
F158_IN(s(z0), 0) → c(U2'(f223_in(z0), s(z0), 0))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(U5'(f158_in(z0, z1), s(z0), z1))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(U8'(f228_in(z0), f229_in(z0), z0))
F223_IN(z0) → c(F228_IN(z0))
S tuples:

F1_IN(.(z0, .(z1, z2))) → c2(U1'(f104_in(z0, z1, z2), .(z0, .(z1, z2))), F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(U3'(f158_in(z0, z1), s(z0), s(z1)), F158_IN(z0, z1))
F228_IN(s(z0)) → c10(U4'(f272_in(z0), s(z0)), F272_IN(z0))
F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
U6'(f105_out1, z0, z1, z2) → c17(U7'(f1_in(.(z1, z2)), z0, z1, z2), F1_IN(.(z1, z2)))
F272_IN(z0) → c22(U9'(f228_in(z0), f278_in(z0), z0), F228_IN(z0))
F158_IN(s(z0), 0) → c(U2'(f223_in(z0), s(z0), 0))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(U5'(f158_in(z0, z1), s(z0), z1))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(U8'(f228_in(z0), f229_in(z0), z0))
F223_IN(z0) → c(F228_IN(z0))
K tuples:none
Defined Rule Symbols:

f1_in, U1, f158_in, U2, U3, f228_in, U4, f105_in, U5, f104_in, U6, U7, f223_in, U8, f272_in, U9

Defined Pair Symbols:

F1_IN, F158_IN, F228_IN, F104_IN, U6', F272_IN, F105_IN, F223_IN

Compound Symbols:

c2, c6, c10, c16, c17, c22, c

(5) CdtGraphRemoveTrailingTuplepartsProof (BOTH BOUNDS(ID, ID) transformation)

Removed 8 trailing tuple parts

(6) Obligation:

Complexity Dependency Tuples Problem
Rules:

f1_in([]) → f1_out1
f1_in(.(z0, [])) → f1_out1
f1_in(.(z0, .(z1, z2))) → U1(f104_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f104_out1, .(z0, .(z1, z2))) → f1_out1
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
U5(f158_out1, s(z0), z1) → f105_out1
f104_in(z0, z1, z2) → U6(f105_in(z0, z1), z0, z1, z2)
U6(f105_out1, z0, z1, z2) → U7(f1_in(.(z1, z2)), z0, z1, z2)
U7(f1_out1, z0, z1, z2) → f104_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U8(f228_out1, z0, z1) → f223_out1
U8(z0, f229_out1(z1), z2) → f223_out2(z1)
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U9(f228_out1, z0, z1) → f272_out1
U9(z0, f278_out1(z1), z2) → f272_out2(z1)
Tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
S tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
K tuples:none
Defined Rule Symbols:

f1_in, U1, f158_in, U2, U3, f228_in, U4, f105_in, U5, f104_in, U6, U7, f223_in, U8, f272_in, U9

Defined Pair Symbols:

F104_IN, F158_IN, F105_IN, F223_IN, F1_IN, F228_IN, U6', F272_IN

Compound Symbols:

c16, c, c2, c6, c10, c17, c22, c

(7) CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
We considered the (Usable) Rules:

f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U5(f158_out1, s(z0), z1) → f105_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U8(f228_out1, z0, z1) → f223_out1
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
U9(f228_out1, z0, z1) → f272_out1
And the Tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(.(x1, x2)) = [1] + x1 + x2   
POL(0) = 0   
POL(F104_IN(x1, x2, x3)) = [2] + x1 + x2 + x3   
POL(F105_IN(x1, x2)) = [1] + x1   
POL(F158_IN(x1, x2)) = [2] + x1   
POL(F1_IN(x1)) = x1   
POL(F223_IN(x1)) = [3] + x1   
POL(F228_IN(x1)) = x1   
POL(F272_IN(x1)) = x1   
POL(U2(x1, x2, x3)) = 0   
POL(U3(x1, x2, x3)) = 0   
POL(U4(x1, x2)) = [3]x2   
POL(U5(x1, x2, x3)) = 0   
POL(U6'(x1, x2, x3, x4)) = [1] + x3 + x4   
POL(U8(x1, x2, x3)) = 0   
POL(U9(x1, x2, x3)) = 0   
POL(c) = 0   
POL(c(x1)) = x1   
POL(c10(x1)) = x1   
POL(c16(x1, x2)) = x1 + x2   
POL(c17(x1)) = x1   
POL(c2(x1)) = x1   
POL(c22(x1)) = x1   
POL(c6(x1)) = x1   
POL(f105_in(x1, x2)) = 0   
POL(f105_out1) = 0   
POL(f158_in(x1, x2)) = 0   
POL(f158_out1) = 0   
POL(f223_in(x1)) = 0   
POL(f223_out1) = 0   
POL(f223_out2(x1)) = 0   
POL(f228_in(x1)) = [2] + [3]x1   
POL(f228_out1) = 0   
POL(f229_in(x1)) = 0   
POL(f272_in(x1)) = 0   
POL(f272_out1) = 0   
POL(f272_out2(x1)) = 0   
POL(f278_in(x1)) = 0   
POL(s(x1)) = [2] + x1   

(8) Obligation:

Complexity Dependency Tuples Problem
Rules:

f1_in([]) → f1_out1
f1_in(.(z0, [])) → f1_out1
f1_in(.(z0, .(z1, z2))) → U1(f104_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f104_out1, .(z0, .(z1, z2))) → f1_out1
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
U5(f158_out1, s(z0), z1) → f105_out1
f104_in(z0, z1, z2) → U6(f105_in(z0, z1), z0, z1, z2)
U6(f105_out1, z0, z1, z2) → U7(f1_in(.(z1, z2)), z0, z1, z2)
U7(f1_out1, z0, z1, z2) → f104_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U8(f228_out1, z0, z1) → f223_out1
U8(z0, f229_out1(z1), z2) → f223_out2(z1)
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U9(f228_out1, z0, z1) → f272_out1
U9(z0, f278_out1(z1), z2) → f272_out2(z1)
Tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
S tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
K tuples:

F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
Defined Rule Symbols:

f1_in, U1, f158_in, U2, U3, f228_in, U4, f105_in, U5, f104_in, U6, U7, f223_in, U8, f272_in, U9

Defined Pair Symbols:

F104_IN, F158_IN, F105_IN, F223_IN, F1_IN, F228_IN, U6', F272_IN

Compound Symbols:

c16, c, c2, c6, c10, c17, c22, c

(9) CdtKnowledgeProof (EQUIVALENT transformation)

The following tuples could be moved from S to K by knowledge propagation:

F272_IN(z0) → c22(F228_IN(z0))
F228_IN(s(z0)) → c10(F272_IN(z0))

(10) Obligation:

Complexity Dependency Tuples Problem
Rules:

f1_in([]) → f1_out1
f1_in(.(z0, [])) → f1_out1
f1_in(.(z0, .(z1, z2))) → U1(f104_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f104_out1, .(z0, .(z1, z2))) → f1_out1
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
U5(f158_out1, s(z0), z1) → f105_out1
f104_in(z0, z1, z2) → U6(f105_in(z0, z1), z0, z1, z2)
U6(f105_out1, z0, z1, z2) → U7(f1_in(.(z1, z2)), z0, z1, z2)
U7(f1_out1, z0, z1, z2) → f104_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U8(f228_out1, z0, z1) → f223_out1
U8(z0, f229_out1(z1), z2) → f223_out2(z1)
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U9(f228_out1, z0, z1) → f272_out1
U9(z0, f278_out1(z1), z2) → f272_out2(z1)
Tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
S tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
K tuples:

F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
F272_IN(z0) → c22(F228_IN(z0))
Defined Rule Symbols:

f1_in, U1, f158_in, U2, U3, f228_in, U4, f105_in, U5, f104_in, U6, U7, f223_in, U8, f272_in, U9

Defined Pair Symbols:

F104_IN, F158_IN, F105_IN, F223_IN, F1_IN, F228_IN, U6', F272_IN

Compound Symbols:

c16, c, c2, c6, c10, c17, c22, c

(11) CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
We considered the (Usable) Rules:

f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U5(f158_out1, s(z0), z1) → f105_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U8(f228_out1, z0, z1) → f223_out1
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
U9(f228_out1, z0, z1) → f272_out1
And the Tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(.(x1, x2)) = [1] + x2   
POL(0) = 0   
POL(F104_IN(x1, x2, x3)) = [1] + x3   
POL(F105_IN(x1, x2)) = 0   
POL(F158_IN(x1, x2)) = 0   
POL(F1_IN(x1)) = x1   
POL(F223_IN(x1)) = 0   
POL(F228_IN(x1)) = 0   
POL(F272_IN(x1)) = 0   
POL(U2(x1, x2, x3)) = 0   
POL(U3(x1, x2, x3)) = 0   
POL(U4(x1, x2)) = 0   
POL(U5(x1, x2, x3)) = 0   
POL(U6'(x1, x2, x3, x4)) = [1] + x4   
POL(U8(x1, x2, x3)) = 0   
POL(U9(x1, x2, x3)) = x1   
POL(c) = 0   
POL(c(x1)) = x1   
POL(c10(x1)) = x1   
POL(c16(x1, x2)) = x1 + x2   
POL(c17(x1)) = x1   
POL(c2(x1)) = x1   
POL(c22(x1)) = x1   
POL(c6(x1)) = x1   
POL(f105_in(x1, x2)) = 0   
POL(f105_out1) = 0   
POL(f158_in(x1, x2)) = 0   
POL(f158_out1) = 0   
POL(f223_in(x1)) = [3] + x1   
POL(f223_out1) = 0   
POL(f223_out2(x1)) = 0   
POL(f228_in(x1)) = [1] + x1   
POL(f228_out1) = 0   
POL(f229_in(x1)) = 0   
POL(f272_in(x1)) = [1] + [2]x1   
POL(f272_out1) = 0   
POL(f272_out2(x1)) = 0   
POL(f278_in(x1)) = 0   
POL(s(x1)) = 0   

(12) Obligation:

Complexity Dependency Tuples Problem
Rules:

f1_in([]) → f1_out1
f1_in(.(z0, [])) → f1_out1
f1_in(.(z0, .(z1, z2))) → U1(f104_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f104_out1, .(z0, .(z1, z2))) → f1_out1
f158_in(0, s(z0)) → f158_out1
f158_in(s(z0), 0) → U2(f223_in(z0), s(z0), 0)
f158_in(s(z0), s(z1)) → U3(f158_in(z0, z1), s(z0), s(z1))
U2(f223_out1, s(z0), 0) → f158_out1
U2(f223_out2(z0), s(z1), 0) → f158_out1
U3(f158_out1, s(z0), s(z1)) → f158_out1
f228_in(s(z0)) → U4(f272_in(z0), s(z0))
U4(f272_out1, s(z0)) → f228_out1
U4(f272_out2(z0), s(z1)) → f228_out1
f105_in(0, z0) → f105_out1
f105_in(s(z0), z1) → U5(f158_in(z0, z1), s(z0), z1)
U5(f158_out1, s(z0), z1) → f105_out1
f104_in(z0, z1, z2) → U6(f105_in(z0, z1), z0, z1, z2)
U6(f105_out1, z0, z1, z2) → U7(f1_in(.(z1, z2)), z0, z1, z2)
U7(f1_out1, z0, z1, z2) → f104_out1
f223_in(z0) → U8(f228_in(z0), f229_in(z0), z0)
U8(f228_out1, z0, z1) → f223_out1
U8(z0, f229_out1(z1), z2) → f223_out2(z1)
f272_in(z0) → U9(f228_in(z0), f278_in(z0), z0)
U9(f228_out1, z0, z1) → f272_out1
U9(z0, f278_out1(z1), z2) → f272_out2(z1)
Tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F272_IN(z0) → c22(F228_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
S tuples:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
K tuples:

F158_IN(s(z0), 0) → c(F223_IN(z0))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
F223_IN(z0) → c(F228_IN(z0))
F158_IN(s(z0), s(z1)) → c6(F158_IN(z0, z1))
F228_IN(s(z0)) → c10(F272_IN(z0))
F158_IN(s(z0), 0) → c
F105_IN(s(z0), z1) → c
F223_IN(z0) → c
F272_IN(z0) → c22(F228_IN(z0))
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
Defined Rule Symbols:

f1_in, U1, f158_in, U2, U3, f228_in, U4, f105_in, U5, f104_in, U6, U7, f223_in, U8, f272_in, U9

Defined Pair Symbols:

F104_IN, F158_IN, F105_IN, F223_IN, F1_IN, F228_IN, U6', F272_IN

Compound Symbols:

c16, c, c2, c6, c10, c17, c22, c

(13) CdtKnowledgeProof (EQUIVALENT transformation)

The following tuples could be moved from S to K by knowledge propagation:

F104_IN(z0, z1, z2) → c16(U6'(f105_in(z0, z1), z0, z1, z2), F105_IN(z0, z1))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F105_IN(s(z0), z1) → c(F158_IN(z0, z1))
U6'(f105_out1, z0, z1, z2) → c17(F1_IN(.(z1, z2)))
F105_IN(s(z0), z1) → c
F1_IN(.(z0, .(z1, z2))) → c2(F104_IN(z0, z1, z2))
Now S is empty

(14) BOUNDS(O(1), O(1))

(15) PrologToCdtProblemTransformerProof (UPPER BOUND (ID) transformation)

Built complexity over-approximating cdt problems from derivation graph.

(16) Obligation:

Complexity Dependency Tuples Problem
Rules:

f2_in([]) → f2_out1
f2_in(.(z0, [])) → f2_out1
f2_in(.(z0, .(z1, z2))) → U1(f99_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f99_out1, .(z0, .(z1, z2))) → f2_out1
f170_in(0, s(z0)) → f170_out1
f170_in(s(z0), 0) → U2(f233_in(z0), s(z0), 0)
f170_in(s(z0), s(z1)) → U3(f170_in(z0, z1), s(z0), s(z1))
U2(f233_out1, s(z0), 0) → f170_out1
U2(f233_out2(z0), s(z1), 0) → f170_out1
U3(f170_out1, s(z0), s(z1)) → f170_out1
f237_in(s(z0)) → U4(f280_in(z0), s(z0))
U4(f280_out1, s(z0)) → f237_out1
U4(f280_out2(z0), s(z1)) → f237_out1
f106_in(0, z0) → f106_out1
f106_in(s(z0), z1) → U5(f170_in(z0, z1), s(z0), z1)
U5(f170_out1, s(z0), z1) → f106_out1
f99_in(z0, z1, z2) → U6(f106_in(z0, z1), z0, z1, z2)
U6(f106_out1, z0, z1, z2) → U7(f2_in(.(z1, z2)), z0, z1, z2)
U7(f2_out1, z0, z1, z2) → f99_out1
f233_in(z0) → U8(f237_in(z0), f238_in(z0), z0)
U8(f237_out1, z0, z1) → f233_out1
U8(z0, f238_out1(z1), z2) → f233_out2(z1)
f280_in(z0) → U9(f237_in(z0), f282_in(z0), z0)
U9(f237_out1, z0, z1) → f280_out1
U9(z0, f282_out1(z1), z2) → f280_out2(z1)
Tuples:

F2_IN(.(z0, .(z1, z2))) → c2(U1'(f99_in(z0, z1, z2), .(z0, .(z1, z2))), F99_IN(z0, z1, z2))
F170_IN(s(z0), 0) → c5(U2'(f233_in(z0), s(z0), 0), F233_IN(z0))
F170_IN(s(z0), s(z1)) → c6(U3'(f170_in(z0, z1), s(z0), s(z1)), F170_IN(z0, z1))
F237_IN(s(z0)) → c10(U4'(f280_in(z0), s(z0)), F280_IN(z0))
F106_IN(s(z0), z1) → c14(U5'(f170_in(z0, z1), s(z0), z1), F170_IN(z0, z1))
F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
U6'(f106_out1, z0, z1, z2) → c17(U7'(f2_in(.(z1, z2)), z0, z1, z2), F2_IN(.(z1, z2)))
F233_IN(z0) → c19(U8'(f237_in(z0), f238_in(z0), z0), F237_IN(z0))
F280_IN(z0) → c22(U9'(f237_in(z0), f282_in(z0), z0), F237_IN(z0))
S tuples:

F2_IN(.(z0, .(z1, z2))) → c2(U1'(f99_in(z0, z1, z2), .(z0, .(z1, z2))), F99_IN(z0, z1, z2))
F170_IN(s(z0), 0) → c5(U2'(f233_in(z0), s(z0), 0), F233_IN(z0))
F170_IN(s(z0), s(z1)) → c6(U3'(f170_in(z0, z1), s(z0), s(z1)), F170_IN(z0, z1))
F237_IN(s(z0)) → c10(U4'(f280_in(z0), s(z0)), F280_IN(z0))
F106_IN(s(z0), z1) → c14(U5'(f170_in(z0, z1), s(z0), z1), F170_IN(z0, z1))
F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
U6'(f106_out1, z0, z1, z2) → c17(U7'(f2_in(.(z1, z2)), z0, z1, z2), F2_IN(.(z1, z2)))
F233_IN(z0) → c19(U8'(f237_in(z0), f238_in(z0), z0), F237_IN(z0))
F280_IN(z0) → c22(U9'(f237_in(z0), f282_in(z0), z0), F237_IN(z0))
K tuples:none
Defined Rule Symbols:

f2_in, U1, f170_in, U2, U3, f237_in, U4, f106_in, U5, f99_in, U6, U7, f233_in, U8, f280_in, U9

Defined Pair Symbols:

F2_IN, F170_IN, F237_IN, F106_IN, F99_IN, U6', F233_IN, F280_IN

Compound Symbols:

c2, c5, c6, c10, c14, c16, c17, c19, c22

(17) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID) transformation)

Split RHS of tuples not part of any SCC

(18) Obligation:

Complexity Dependency Tuples Problem
Rules:

f2_in([]) → f2_out1
f2_in(.(z0, [])) → f2_out1
f2_in(.(z0, .(z1, z2))) → U1(f99_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f99_out1, .(z0, .(z1, z2))) → f2_out1
f170_in(0, s(z0)) → f170_out1
f170_in(s(z0), 0) → U2(f233_in(z0), s(z0), 0)
f170_in(s(z0), s(z1)) → U3(f170_in(z0, z1), s(z0), s(z1))
U2(f233_out1, s(z0), 0) → f170_out1
U2(f233_out2(z0), s(z1), 0) → f170_out1
U3(f170_out1, s(z0), s(z1)) → f170_out1
f237_in(s(z0)) → U4(f280_in(z0), s(z0))
U4(f280_out1, s(z0)) → f237_out1
U4(f280_out2(z0), s(z1)) → f237_out1
f106_in(0, z0) → f106_out1
f106_in(s(z0), z1) → U5(f170_in(z0, z1), s(z0), z1)
U5(f170_out1, s(z0), z1) → f106_out1
f99_in(z0, z1, z2) → U6(f106_in(z0, z1), z0, z1, z2)
U6(f106_out1, z0, z1, z2) → U7(f2_in(.(z1, z2)), z0, z1, z2)
U7(f2_out1, z0, z1, z2) → f99_out1
f233_in(z0) → U8(f237_in(z0), f238_in(z0), z0)
U8(f237_out1, z0, z1) → f233_out1
U8(z0, f238_out1(z1), z2) → f233_out2(z1)
f280_in(z0) → U9(f237_in(z0), f282_in(z0), z0)
U9(f237_out1, z0, z1) → f280_out1
U9(z0, f282_out1(z1), z2) → f280_out2(z1)
Tuples:

F2_IN(.(z0, .(z1, z2))) → c2(U1'(f99_in(z0, z1, z2), .(z0, .(z1, z2))), F99_IN(z0, z1, z2))
F170_IN(s(z0), s(z1)) → c6(U3'(f170_in(z0, z1), s(z0), s(z1)), F170_IN(z0, z1))
F237_IN(s(z0)) → c10(U4'(f280_in(z0), s(z0)), F280_IN(z0))
F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
U6'(f106_out1, z0, z1, z2) → c17(U7'(f2_in(.(z1, z2)), z0, z1, z2), F2_IN(.(z1, z2)))
F280_IN(z0) → c22(U9'(f237_in(z0), f282_in(z0), z0), F237_IN(z0))
F170_IN(s(z0), 0) → c(U2'(f233_in(z0), s(z0), 0))
F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(U5'(f170_in(z0, z1), s(z0), z1))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(U8'(f237_in(z0), f238_in(z0), z0))
F233_IN(z0) → c(F237_IN(z0))
S tuples:

F2_IN(.(z0, .(z1, z2))) → c2(U1'(f99_in(z0, z1, z2), .(z0, .(z1, z2))), F99_IN(z0, z1, z2))
F170_IN(s(z0), s(z1)) → c6(U3'(f170_in(z0, z1), s(z0), s(z1)), F170_IN(z0, z1))
F237_IN(s(z0)) → c10(U4'(f280_in(z0), s(z0)), F280_IN(z0))
F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
U6'(f106_out1, z0, z1, z2) → c17(U7'(f2_in(.(z1, z2)), z0, z1, z2), F2_IN(.(z1, z2)))
F280_IN(z0) → c22(U9'(f237_in(z0), f282_in(z0), z0), F237_IN(z0))
F170_IN(s(z0), 0) → c(U2'(f233_in(z0), s(z0), 0))
F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(U5'(f170_in(z0, z1), s(z0), z1))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(U8'(f237_in(z0), f238_in(z0), z0))
F233_IN(z0) → c(F237_IN(z0))
K tuples:none
Defined Rule Symbols:

f2_in, U1, f170_in, U2, U3, f237_in, U4, f106_in, U5, f99_in, U6, U7, f233_in, U8, f280_in, U9

Defined Pair Symbols:

F2_IN, F170_IN, F237_IN, F99_IN, U6', F280_IN, F106_IN, F233_IN

Compound Symbols:

c2, c6, c10, c16, c17, c22, c

(19) CdtGraphRemoveTrailingTuplepartsProof (BOTH BOUNDS(ID, ID) transformation)

Removed 8 trailing tuple parts

(20) Obligation:

Complexity Dependency Tuples Problem
Rules:

f2_in([]) → f2_out1
f2_in(.(z0, [])) → f2_out1
f2_in(.(z0, .(z1, z2))) → U1(f99_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f99_out1, .(z0, .(z1, z2))) → f2_out1
f170_in(0, s(z0)) → f170_out1
f170_in(s(z0), 0) → U2(f233_in(z0), s(z0), 0)
f170_in(s(z0), s(z1)) → U3(f170_in(z0, z1), s(z0), s(z1))
U2(f233_out1, s(z0), 0) → f170_out1
U2(f233_out2(z0), s(z1), 0) → f170_out1
U3(f170_out1, s(z0), s(z1)) → f170_out1
f237_in(s(z0)) → U4(f280_in(z0), s(z0))
U4(f280_out1, s(z0)) → f237_out1
U4(f280_out2(z0), s(z1)) → f237_out1
f106_in(0, z0) → f106_out1
f106_in(s(z0), z1) → U5(f170_in(z0, z1), s(z0), z1)
U5(f170_out1, s(z0), z1) → f106_out1
f99_in(z0, z1, z2) → U6(f106_in(z0, z1), z0, z1, z2)
U6(f106_out1, z0, z1, z2) → U7(f2_in(.(z1, z2)), z0, z1, z2)
U7(f2_out1, z0, z1, z2) → f99_out1
f233_in(z0) → U8(f237_in(z0), f238_in(z0), z0)
U8(f237_out1, z0, z1) → f233_out1
U8(z0, f238_out1(z1), z2) → f233_out2(z1)
f280_in(z0) → U9(f237_in(z0), f282_in(z0), z0)
U9(f237_out1, z0, z1) → f280_out1
U9(z0, f282_out1(z1), z2) → f280_out2(z1)
Tuples:

F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F2_IN(.(z0, .(z1, z2))) → c2(F99_IN(z0, z1, z2))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
U6'(f106_out1, z0, z1, z2) → c17(F2_IN(.(z1, z2)))
F280_IN(z0) → c22(F237_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
S tuples:

F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F2_IN(.(z0, .(z1, z2))) → c2(F99_IN(z0, z1, z2))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
U6'(f106_out1, z0, z1, z2) → c17(F2_IN(.(z1, z2)))
F280_IN(z0) → c22(F237_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
K tuples:none
Defined Rule Symbols:

f2_in, U1, f170_in, U2, U3, f237_in, U4, f106_in, U5, f99_in, U6, U7, f233_in, U8, f280_in, U9

Defined Pair Symbols:

F99_IN, F170_IN, F106_IN, F233_IN, F2_IN, F237_IN, U6', F280_IN

Compound Symbols:

c16, c, c2, c6, c10, c17, c22, c

(21) CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
We considered the (Usable) Rules:

f106_in(0, z0) → f106_out1
f106_in(s(z0), z1) → U5(f170_in(z0, z1), s(z0), z1)
f170_in(0, s(z0)) → f170_out1
f170_in(s(z0), 0) → U2(f233_in(z0), s(z0), 0)
f170_in(s(z0), s(z1)) → U3(f170_in(z0, z1), s(z0), s(z1))
U5(f170_out1, s(z0), z1) → f106_out1
U3(f170_out1, s(z0), s(z1)) → f170_out1
f233_in(z0) → U8(f237_in(z0), f238_in(z0), z0)
U2(f233_out1, s(z0), 0) → f170_out1
U2(f233_out2(z0), s(z1), 0) → f170_out1
f237_in(s(z0)) → U4(f280_in(z0), s(z0))
U8(f237_out1, z0, z1) → f233_out1
f280_in(z0) → U9(f237_in(z0), f282_in(z0), z0)
U4(f280_out1, s(z0)) → f237_out1
U4(f280_out2(z0), s(z1)) → f237_out1
U9(f237_out1, z0, z1) → f280_out1
And the Tuples:

F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F2_IN(.(z0, .(z1, z2))) → c2(F99_IN(z0, z1, z2))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
U6'(f106_out1, z0, z1, z2) → c17(F2_IN(.(z1, z2)))
F280_IN(z0) → c22(F237_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(.(x1, x2)) = [1] + x1 + x2   
POL(0) = 0   
POL(F106_IN(x1, x2)) = [1] + x1   
POL(F170_IN(x1, x2)) = [2] + x1   
POL(F233_IN(x1)) = [3] + x1   
POL(F237_IN(x1)) = x1   
POL(F280_IN(x1)) = x1   
POL(F2_IN(x1)) = x1   
POL(F99_IN(x1, x2, x3)) = [2] + x1 + x2 + x3   
POL(U2(x1, x2, x3)) = 0   
POL(U3(x1, x2, x3)) = 0   
POL(U4(x1, x2)) = [3]x2   
POL(U5(x1, x2, x3)) = 0   
POL(U6'(x1, x2, x3, x4)) = [1] + x3 + x4   
POL(U8(x1, x2, x3)) = 0   
POL(U9(x1, x2, x3)) = 0   
POL(c) = 0   
POL(c(x1)) = x1   
POL(c10(x1)) = x1   
POL(c16(x1, x2)) = x1 + x2   
POL(c17(x1)) = x1   
POL(c2(x1)) = x1   
POL(c22(x1)) = x1   
POL(c6(x1)) = x1   
POL(f106_in(x1, x2)) = 0   
POL(f106_out1) = 0   
POL(f170_in(x1, x2)) = 0   
POL(f170_out1) = 0   
POL(f233_in(x1)) = 0   
POL(f233_out1) = 0   
POL(f233_out2(x1)) = 0   
POL(f237_in(x1)) = [2] + [3]x1   
POL(f237_out1) = 0   
POL(f238_in(x1)) = 0   
POL(f280_in(x1)) = 0   
POL(f280_out1) = 0   
POL(f280_out2(x1)) = 0   
POL(f282_in(x1)) = 0   
POL(s(x1)) = [2] + x1   

(22) Obligation:

Complexity Dependency Tuples Problem
Rules:

f2_in([]) → f2_out1
f2_in(.(z0, [])) → f2_out1
f2_in(.(z0, .(z1, z2))) → U1(f99_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f99_out1, .(z0, .(z1, z2))) → f2_out1
f170_in(0, s(z0)) → f170_out1
f170_in(s(z0), 0) → U2(f233_in(z0), s(z0), 0)
f170_in(s(z0), s(z1)) → U3(f170_in(z0, z1), s(z0), s(z1))
U2(f233_out1, s(z0), 0) → f170_out1
U2(f233_out2(z0), s(z1), 0) → f170_out1
U3(f170_out1, s(z0), s(z1)) → f170_out1
f237_in(s(z0)) → U4(f280_in(z0), s(z0))
U4(f280_out1, s(z0)) → f237_out1
U4(f280_out2(z0), s(z1)) → f237_out1
f106_in(0, z0) → f106_out1
f106_in(s(z0), z1) → U5(f170_in(z0, z1), s(z0), z1)
U5(f170_out1, s(z0), z1) → f106_out1
f99_in(z0, z1, z2) → U6(f106_in(z0, z1), z0, z1, z2)
U6(f106_out1, z0, z1, z2) → U7(f2_in(.(z1, z2)), z0, z1, z2)
U7(f2_out1, z0, z1, z2) → f99_out1
f233_in(z0) → U8(f237_in(z0), f238_in(z0), z0)
U8(f237_out1, z0, z1) → f233_out1
U8(z0, f238_out1(z1), z2) → f233_out2(z1)
f280_in(z0) → U9(f237_in(z0), f282_in(z0), z0)
U9(f237_out1, z0, z1) → f280_out1
U9(z0, f282_out1(z1), z2) → f280_out2(z1)
Tuples:

F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F2_IN(.(z0, .(z1, z2))) → c2(F99_IN(z0, z1, z2))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
U6'(f106_out1, z0, z1, z2) → c17(F2_IN(.(z1, z2)))
F280_IN(z0) → c22(F237_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
S tuples:

F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
F2_IN(.(z0, .(z1, z2))) → c2(F99_IN(z0, z1, z2))
U6'(f106_out1, z0, z1, z2) → c17(F2_IN(.(z1, z2)))
F280_IN(z0) → c22(F237_IN(z0))
K tuples:

F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
Defined Rule Symbols:

f2_in, U1, f170_in, U2, U3, f237_in, U4, f106_in, U5, f99_in, U6, U7, f233_in, U8, f280_in, U9

Defined Pair Symbols:

F99_IN, F170_IN, F106_IN, F233_IN, F2_IN, F237_IN, U6', F280_IN

Compound Symbols:

c16, c, c2, c6, c10, c17, c22, c

(23) CdtKnowledgeProof (EQUIVALENT transformation)

The following tuples could be moved from S to K by knowledge propagation:

F280_IN(z0) → c22(F237_IN(z0))
F237_IN(s(z0)) → c10(F280_IN(z0))

(24) Obligation:

Complexity Dependency Tuples Problem
Rules:

f2_in([]) → f2_out1
f2_in(.(z0, [])) → f2_out1
f2_in(.(z0, .(z1, z2))) → U1(f99_in(z0, z1, z2), .(z0, .(z1, z2)))
U1(f99_out1, .(z0, .(z1, z2))) → f2_out1
f170_in(0, s(z0)) → f170_out1
f170_in(s(z0), 0) → U2(f233_in(z0), s(z0), 0)
f170_in(s(z0), s(z1)) → U3(f170_in(z0, z1), s(z0), s(z1))
U2(f233_out1, s(z0), 0) → f170_out1
U2(f233_out2(z0), s(z1), 0) → f170_out1
U3(f170_out1, s(z0), s(z1)) → f170_out1
f237_in(s(z0)) → U4(f280_in(z0), s(z0))
U4(f280_out1, s(z0)) → f237_out1
U4(f280_out2(z0), s(z1)) → f237_out1
f106_in(0, z0) → f106_out1
f106_in(s(z0), z1) → U5(f170_in(z0, z1), s(z0), z1)
U5(f170_out1, s(z0), z1) → f106_out1
f99_in(z0, z1, z2) → U6(f106_in(z0, z1), z0, z1, z2)
U6(f106_out1, z0, z1, z2) → U7(f2_in(.(z1, z2)), z0, z1, z2)
U7(f2_out1, z0, z1, z2) → f99_out1
f233_in(z0) → U8(f237_in(z0), f238_in(z0), z0)
U8(f237_out1, z0, z1) → f233_out1
U8(z0, f238_out1(z1), z2) → f233_out2(z1)
f280_in(z0) → U9(f237_in(z0), f282_in(z0), z0)
U9(f237_out1, z0, z1) → f280_out1
U9(z0, f282_out1(z1), z2) → f280_out2(z1)
Tuples:

F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F2_IN(.(z0, .(z1, z2))) → c2(F99_IN(z0, z1, z2))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
U6'(f106_out1, z0, z1, z2) → c17(F2_IN(.(z1, z2)))
F280_IN(z0) → c22(F237_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
S tuples:

F99_IN(z0, z1, z2) → c16(U6'(f106_in(z0, z1), z0, z1, z2), F106_IN(z0, z1))
F2_IN(.(z0, .(z1, z2))) → c2(F99_IN(z0, z1, z2))
U6'(f106_out1, z0, z1, z2) → c17(F2_IN(.(z1, z2)))
K tuples:

F170_IN(s(z0), 0) → c(F233_IN(z0))
F106_IN(s(z0), z1) → c(F170_IN(z0, z1))
F233_IN(z0) → c(F237_IN(z0))
F170_IN(s(z0), s(z1)) → c6(F170_IN(z0, z1))
F237_IN(s(z0)) → c10(F280_IN(z0))
F170_IN(s(z0), 0) → c
F106_IN(s(z0), z1) → c
F233_IN(z0) → c
F280_IN(z0) → c22(F237_IN(z0))
Defined Rule Symbols:

f2_in, U1, f170_in, U2, U3, f237_in, U4, f106_in, U5, f99_in, U6, U7, f233_in, U8, f280_in, U9

Defined Pair Symbols:

F99_IN, F170_IN, F106_IN, F233_IN, F2_IN, F237_IN, U6', F280_IN

Compound Symbols:

c16, c, c2, c6, c10, c17, c22, c