(0) Obligation:
Clauses:
h(X) :- ','(f(X), g(X)).
f(c(0, X1)).
f(c(X, Y)) :- ','(no(zero(X)), ','(p(X, P), f(c(P, s(Y))))).
g(c(X2, 0)).
g(c(X, Y)) :- ','(no(zero(Y)), ','(p(Y, P), g(c(s(X), P)))).
p(0, 0).
p(s(X), X).
zero(0).
no(X) :- ','(X, ','(!, failure(a))).
no(X3).
failure(b).
Query: h(g)
(1) PrologToCdtProblemTransformerProof (UPPER BOUND (ID) transformation)
Built complexity over-approximating cdt problems from derivation graph.
(2) Obligation:
Complexity Dependency Tuples Problem
Rules:
f2_in(z0) → U1(f6_in(z0), z0)
U1(f6_out1, z0) → f2_out1
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
f14_in(c(z0, 0)) → f14_out1
f14_in(c(z0, s(z1))) → U3(f14_in(c(s(z0), z1)), c(z0, s(z1)))
U3(f14_out1, c(z0, s(z1))) → f14_out1
f6_in(z0) → U4(f13_in(z0), z0)
U4(f13_out1, z0) → U5(f14_in(z0), z0)
U5(f14_out1, z0) → f6_out1
Tuples:
F2_IN(z0) → c1(U1'(f6_in(z0), z0), F6_IN(z0))
F13_IN(c(s(z0), z1)) → c4(U2'(f13_in(c(z0, s(z1))), c(s(z0), z1)), F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(U3'(f14_in(c(s(z0), z1)), c(z0, s(z1))), F14_IN(c(s(z0), z1)))
F6_IN(z0) → c9(U4'(f13_in(z0), z0), F13_IN(z0))
U4'(f13_out1, z0) → c10(U5'(f14_in(z0), z0), F14_IN(z0))
S tuples:
F2_IN(z0) → c1(U1'(f6_in(z0), z0), F6_IN(z0))
F13_IN(c(s(z0), z1)) → c4(U2'(f13_in(c(z0, s(z1))), c(s(z0), z1)), F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(U3'(f14_in(c(s(z0), z1)), c(z0, s(z1))), F14_IN(c(s(z0), z1)))
F6_IN(z0) → c9(U4'(f13_in(z0), z0), F13_IN(z0))
U4'(f13_out1, z0) → c10(U5'(f14_in(z0), z0), F14_IN(z0))
K tuples:none
Defined Rule Symbols:
f2_in, U1, f13_in, U2, f14_in, U3, f6_in, U4, U5
Defined Pair Symbols:
F2_IN, F13_IN, F14_IN, F6_IN, U4'
Compound Symbols:
c1, c4, c7, c9, c10
(3) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID) transformation)
Split RHS of tuples not part of any SCC
(4) Obligation:
Complexity Dependency Tuples Problem
Rules:
f2_in(z0) → U1(f6_in(z0), z0)
U1(f6_out1, z0) → f2_out1
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
f14_in(c(z0, 0)) → f14_out1
f14_in(c(z0, s(z1))) → U3(f14_in(c(s(z0), z1)), c(z0, s(z1)))
U3(f14_out1, c(z0, s(z1))) → f14_out1
f6_in(z0) → U4(f13_in(z0), z0)
U4(f13_out1, z0) → U5(f14_in(z0), z0)
U5(f14_out1, z0) → f6_out1
Tuples:
F13_IN(c(s(z0), z1)) → c4(U2'(f13_in(c(z0, s(z1))), c(s(z0), z1)), F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(U3'(f14_in(c(s(z0), z1)), c(z0, s(z1))), F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2(U1'(f6_in(z0), z0))
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(U5'(f14_in(z0), z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
S tuples:
F13_IN(c(s(z0), z1)) → c4(U2'(f13_in(c(z0, s(z1))), c(s(z0), z1)), F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(U3'(f14_in(c(s(z0), z1)), c(z0, s(z1))), F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2(U1'(f6_in(z0), z0))
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(U5'(f14_in(z0), z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
K tuples:none
Defined Rule Symbols:
f2_in, U1, f13_in, U2, f14_in, U3, f6_in, U4, U5
Defined Pair Symbols:
F13_IN, F14_IN, F2_IN, F6_IN, U4'
Compound Symbols:
c4, c7, c2
(5) CdtGraphRemoveTrailingTuplepartsProof (BOTH BOUNDS(ID, ID) transformation)
Removed 4 trailing tuple parts
(6) Obligation:
Complexity Dependency Tuples Problem
Rules:
f2_in(z0) → U1(f6_in(z0), z0)
U1(f6_out1, z0) → f2_out1
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
f14_in(c(z0, 0)) → f14_out1
f14_in(c(z0, s(z1))) → U3(f14_in(c(s(z0), z1)), c(z0, s(z1)))
U3(f14_out1, c(z0, s(z1))) → f14_out1
f6_in(z0) → U4(f13_in(z0), z0)
U4(f13_out1, z0) → U5(f14_in(z0), z0)
U5(f14_out1, z0) → f6_out1
Tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
S tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
K tuples:none
Defined Rule Symbols:
f2_in, U1, f13_in, U2, f14_in, U3, f6_in, U4, U5
Defined Pair Symbols:
F2_IN, F6_IN, U4', F13_IN, F14_IN
Compound Symbols:
c2, c4, c7, c2
(7) CdtKnowledgeProof (EQUIVALENT transformation)
The following tuples could be moved from S to K by knowledge propagation:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
U4'(f13_out1, z0) → c2
(8) Obligation:
Complexity Dependency Tuples Problem
Rules:
f2_in(z0) → U1(f6_in(z0), z0)
U1(f6_out1, z0) → f2_out1
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
f14_in(c(z0, 0)) → f14_out1
f14_in(c(z0, s(z1))) → U3(f14_in(c(s(z0), z1)), c(z0, s(z1)))
U3(f14_out1, c(z0, s(z1))) → f14_out1
f6_in(z0) → U4(f13_in(z0), z0)
U4(f13_out1, z0) → U5(f14_in(z0), z0)
U5(f14_out1, z0) → f6_out1
Tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
S tuples:
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
K tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
Defined Rule Symbols:
f2_in, U1, f13_in, U2, f14_in, U3, f6_in, U4, U5
Defined Pair Symbols:
F2_IN, F6_IN, U4', F13_IN, F14_IN
Compound Symbols:
c2, c4, c7, c2
(9) 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.
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
We considered the (Usable) Rules:
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
And the Tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
The order we found is given by the following interpretation:
Polynomial interpretation :
POL(0) = 0
POL(F13_IN(x1)) = [2]
POL(F14_IN(x1)) = [2] + x1
POL(F2_IN(x1)) = [3] + [3]x1
POL(F6_IN(x1)) = [3] + [3]x1
POL(U2(x1, x2)) = 0
POL(U4'(x1, x2)) = [2] + [2]x2
POL(c(x1, x2)) = x2
POL(c2) = 0
POL(c2(x1)) = x1
POL(c4(x1)) = x1
POL(c7(x1)) = x1
POL(f13_in(x1)) = 0
POL(f13_out1) = 0
POL(s(x1)) = [1] + x1
(10) Obligation:
Complexity Dependency Tuples Problem
Rules:
f2_in(z0) → U1(f6_in(z0), z0)
U1(f6_out1, z0) → f2_out1
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
f14_in(c(z0, 0)) → f14_out1
f14_in(c(z0, s(z1))) → U3(f14_in(c(s(z0), z1)), c(z0, s(z1)))
U3(f14_out1, c(z0, s(z1))) → f14_out1
f6_in(z0) → U4(f13_in(z0), z0)
U4(f13_out1, z0) → U5(f14_in(z0), z0)
U5(f14_out1, z0) → f6_out1
Tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
S tuples:
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
K tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
Defined Rule Symbols:
f2_in, U1, f13_in, U2, f14_in, U3, f6_in, U4, U5
Defined Pair Symbols:
F2_IN, F6_IN, U4', F13_IN, F14_IN
Compound Symbols:
c2, c4, c7, c2
(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.
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
We considered the (Usable) Rules:
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
And the Tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
The order we found is given by the following interpretation:
Polynomial interpretation :
POL(0) = 0
POL(F13_IN(x1)) = [1] + x1
POL(F14_IN(x1)) = 0
POL(F2_IN(x1)) = [1] + [2]x1
POL(F6_IN(x1)) = [1] + [2]x1
POL(U2(x1, x2)) = 0
POL(U4'(x1, x2)) = 0
POL(c(x1, x2)) = x1
POL(c2) = 0
POL(c2(x1)) = x1
POL(c4(x1)) = x1
POL(c7(x1)) = x1
POL(f13_in(x1)) = 0
POL(f13_out1) = 0
POL(s(x1)) = [1] + x1
(12) Obligation:
Complexity Dependency Tuples Problem
Rules:
f2_in(z0) → U1(f6_in(z0), z0)
U1(f6_out1, z0) → f2_out1
f13_in(c(0, z0)) → f13_out1
f13_in(c(s(z0), z1)) → U2(f13_in(c(z0, s(z1))), c(s(z0), z1))
U2(f13_out1, c(s(z0), z1)) → f13_out1
f14_in(c(z0, 0)) → f14_out1
f14_in(c(z0, s(z1))) → U3(f14_in(c(s(z0), z1)), c(z0, s(z1)))
U3(f14_out1, c(z0, s(z1))) → f14_out1
f6_in(z0) → U4(f13_in(z0), z0)
U4(f13_out1, z0) → U5(f14_in(z0), z0)
U5(f14_out1, z0) → f6_out1
Tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
S tuples:none
K tuples:
F2_IN(z0) → c2(F6_IN(z0))
F6_IN(z0) → c2(U4'(f13_in(z0), z0))
F6_IN(z0) → c2(F13_IN(z0))
U4'(f13_out1, z0) → c2(F14_IN(z0))
F2_IN(z0) → c2
U4'(f13_out1, z0) → c2
F14_IN(c(z0, s(z1))) → c7(F14_IN(c(s(z0), z1)))
F13_IN(c(s(z0), z1)) → c4(F13_IN(c(z0, s(z1))))
Defined Rule Symbols:
f2_in, U1, f13_in, U2, f14_in, U3, f6_in, U4, U5
Defined Pair Symbols:
F2_IN, F6_IN, U4', F13_IN, F14_IN
Compound Symbols:
c2, c4, c7, c2
(13) SIsEmptyProof (EQUIVALENT transformation)
The set 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:
f1_in(c(0, z0)) → U1(f8_in(z0), c(0, z0))
f1_in(c(s(z0), z1)) → U2(f372_in(z0, z1), c(s(z0), z1))
U1(f8_out1, c(0, z0)) → f1_out1
U1(f8_out2, c(0, z0)) → f1_out1
U2(f372_out1, c(s(z0), z1)) → f1_out1
f315_in(z0, 0) → f315_out1
f315_in(z0, s(z1)) → U3(f315_in(s(z0), z1), z0, s(z1))
U3(f315_out1, z0, s(z1)) → f315_out1
f374_in(0, z0) → f374_out1
f374_in(s(z0), z1) → U4(f374_in(z0, s(z1)), s(z0), z1)
U4(f374_out1, s(z0), z1) → f374_out1
f10_in(0) → f10_out1
f10_in(s(0)) → f10_out1
f10_in(s(s(0))) → f10_out1
f10_in(s(s(s(0)))) → f10_out1
f10_in(s(s(s(s(0))))) → f10_out1
f10_in(s(s(s(s(s(0)))))) → f10_out1
f10_in(s(s(s(s(s(s(0))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(0)))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(s(z0))))))))) → U5(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0)))))))))
U5(f315_out1, s(s(s(s(s(s(s(s(z0))))))))) → f10_out1
f372_in(z0, z1) → U6(f374_in(z0, z1), z0, z1)
U6(f374_out1, z0, z1) → U7(f315_in(z0, z1), z0, z1)
U7(f315_out1, z0, z1) → f372_out1
f8_in(z0) → U8(f10_in(z0), f11_in(z0), z0)
U8(f10_out1, z0, z1) → f8_out1
U8(z0, f11_out1, z1) → f8_out2
Tuples:
F1_IN(c(0, z0)) → c1(U1'(f8_in(z0), c(0, z0)), F8_IN(z0))
F1_IN(c(s(z0), z1)) → c2(U2'(f372_in(z0, z1), c(s(z0), z1)), F372_IN(z0, z1))
F315_IN(z0, s(z1)) → c7(U3'(f315_in(s(z0), z1), z0, s(z1)), F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(U4'(f374_in(z0, s(z1)), s(z0), z1), F374_IN(z0, s(z1)))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c20(U5'(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0))))))))), F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F372_IN(z0, z1) → c22(U6'(f374_in(z0, z1), z0, z1), F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c23(U7'(f315_in(z0, z1), z0, z1), F315_IN(z0, z1))
F8_IN(z0) → c25(U8'(f10_in(z0), f11_in(z0), z0), F10_IN(z0))
S tuples:
F1_IN(c(0, z0)) → c1(U1'(f8_in(z0), c(0, z0)), F8_IN(z0))
F1_IN(c(s(z0), z1)) → c2(U2'(f372_in(z0, z1), c(s(z0), z1)), F372_IN(z0, z1))
F315_IN(z0, s(z1)) → c7(U3'(f315_in(s(z0), z1), z0, s(z1)), F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(U4'(f374_in(z0, s(z1)), s(z0), z1), F374_IN(z0, s(z1)))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c20(U5'(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0))))))))), F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F372_IN(z0, z1) → c22(U6'(f374_in(z0, z1), z0, z1), F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c23(U7'(f315_in(z0, z1), z0, z1), F315_IN(z0, z1))
F8_IN(z0) → c25(U8'(f10_in(z0), f11_in(z0), z0), F10_IN(z0))
K tuples:none
Defined Rule Symbols:
f1_in, U1, U2, f315_in, U3, f374_in, U4, f10_in, U5, f372_in, U6, U7, f8_in, U8
Defined Pair Symbols:
F1_IN, F315_IN, F374_IN, F10_IN, F372_IN, U6', F8_IN
Compound Symbols:
c1, c2, c7, c10, c20, c22, c23, c25
(17) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID) transformation)
Split RHS of tuples not part of any SCC
(18) Obligation:
Complexity Dependency Tuples Problem
Rules:
f1_in(c(0, z0)) → U1(f8_in(z0), c(0, z0))
f1_in(c(s(z0), z1)) → U2(f372_in(z0, z1), c(s(z0), z1))
U1(f8_out1, c(0, z0)) → f1_out1
U1(f8_out2, c(0, z0)) → f1_out1
U2(f372_out1, c(s(z0), z1)) → f1_out1
f315_in(z0, 0) → f315_out1
f315_in(z0, s(z1)) → U3(f315_in(s(z0), z1), z0, s(z1))
U3(f315_out1, z0, s(z1)) → f315_out1
f374_in(0, z0) → f374_out1
f374_in(s(z0), z1) → U4(f374_in(z0, s(z1)), s(z0), z1)
U4(f374_out1, s(z0), z1) → f374_out1
f10_in(0) → f10_out1
f10_in(s(0)) → f10_out1
f10_in(s(s(0))) → f10_out1
f10_in(s(s(s(0)))) → f10_out1
f10_in(s(s(s(s(0))))) → f10_out1
f10_in(s(s(s(s(s(0)))))) → f10_out1
f10_in(s(s(s(s(s(s(0))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(0)))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(s(z0))))))))) → U5(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0)))))))))
U5(f315_out1, s(s(s(s(s(s(s(s(z0))))))))) → f10_out1
f372_in(z0, z1) → U6(f374_in(z0, z1), z0, z1)
U6(f374_out1, z0, z1) → U7(f315_in(z0, z1), z0, z1)
U7(f315_out1, z0, z1) → f372_out1
f8_in(z0) → U8(f10_in(z0), f11_in(z0), z0)
U8(f10_out1, z0, z1) → f8_out1
U8(z0, f11_out1, z1) → f8_out2
Tuples:
F315_IN(z0, s(z1)) → c7(U3'(f315_in(s(z0), z1), z0, s(z1)), F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(U4'(f374_in(z0, s(z1)), s(z0), z1), F374_IN(z0, s(z1)))
F1_IN(c(0, z0)) → c3(U1'(f8_in(z0), c(0, z0)))
F1_IN(c(0, z0)) → c3(F8_IN(z0))
F1_IN(c(s(z0), z1)) → c3(U2'(f372_in(z0, z1), c(s(z0), z1)))
F1_IN(c(s(z0), z1)) → c3(F372_IN(z0, z1))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(U5'(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0))))))))))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(U7'(f315_in(z0, z1), z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
F8_IN(z0) → c3(U8'(f10_in(z0), f11_in(z0), z0))
F8_IN(z0) → c3(F10_IN(z0))
S tuples:
F315_IN(z0, s(z1)) → c7(U3'(f315_in(s(z0), z1), z0, s(z1)), F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(U4'(f374_in(z0, s(z1)), s(z0), z1), F374_IN(z0, s(z1)))
F1_IN(c(0, z0)) → c3(U1'(f8_in(z0), c(0, z0)))
F1_IN(c(0, z0)) → c3(F8_IN(z0))
F1_IN(c(s(z0), z1)) → c3(U2'(f372_in(z0, z1), c(s(z0), z1)))
F1_IN(c(s(z0), z1)) → c3(F372_IN(z0, z1))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(U5'(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0))))))))))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(U7'(f315_in(z0, z1), z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
F8_IN(z0) → c3(U8'(f10_in(z0), f11_in(z0), z0))
F8_IN(z0) → c3(F10_IN(z0))
K tuples:none
Defined Rule Symbols:
f1_in, U1, U2, f315_in, U3, f374_in, U4, f10_in, U5, f372_in, U6, U7, f8_in, U8
Defined Pair Symbols:
F315_IN, F374_IN, F1_IN, F10_IN, F372_IN, U6', F8_IN
Compound Symbols:
c7, c10, c3
(19) CdtGraphRemoveTrailingTuplepartsProof (BOTH BOUNDS(ID, ID) transformation)
Removed 7 trailing tuple parts
(20) Obligation:
Complexity Dependency Tuples Problem
Rules:
f1_in(c(0, z0)) → U1(f8_in(z0), c(0, z0))
f1_in(c(s(z0), z1)) → U2(f372_in(z0, z1), c(s(z0), z1))
U1(f8_out1, c(0, z0)) → f1_out1
U1(f8_out2, c(0, z0)) → f1_out1
U2(f372_out1, c(s(z0), z1)) → f1_out1
f315_in(z0, 0) → f315_out1
f315_in(z0, s(z1)) → U3(f315_in(s(z0), z1), z0, s(z1))
U3(f315_out1, z0, s(z1)) → f315_out1
f374_in(0, z0) → f374_out1
f374_in(s(z0), z1) → U4(f374_in(z0, s(z1)), s(z0), z1)
U4(f374_out1, s(z0), z1) → f374_out1
f10_in(0) → f10_out1
f10_in(s(0)) → f10_out1
f10_in(s(s(0))) → f10_out1
f10_in(s(s(s(0)))) → f10_out1
f10_in(s(s(s(s(0))))) → f10_out1
f10_in(s(s(s(s(s(0)))))) → f10_out1
f10_in(s(s(s(s(s(s(0))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(0)))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(s(z0))))))))) → U5(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0)))))))))
U5(f315_out1, s(s(s(s(s(s(s(s(z0))))))))) → f10_out1
f372_in(z0, z1) → U6(f374_in(z0, z1), z0, z1)
U6(f374_out1, z0, z1) → U7(f315_in(z0, z1), z0, z1)
U7(f315_out1, z0, z1) → f372_out1
f8_in(z0) → U8(f10_in(z0), f11_in(z0), z0)
U8(f10_out1, z0, z1) → f8_out1
U8(z0, f11_out1, z1) → f8_out2
Tuples:
F1_IN(c(0, z0)) → c3(F8_IN(z0))
F1_IN(c(s(z0), z1)) → c3(F372_IN(z0, z1))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
F8_IN(z0) → c3(F10_IN(z0))
F315_IN(z0, s(z1)) → c7(F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(F374_IN(z0, s(z1)))
F1_IN(c(0, z0)) → c3
F1_IN(c(s(z0), z1)) → c3
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3
U6'(f374_out1, z0, z1) → c3
F8_IN(z0) → c3
S tuples:
F1_IN(c(0, z0)) → c3(F8_IN(z0))
F1_IN(c(s(z0), z1)) → c3(F372_IN(z0, z1))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
F8_IN(z0) → c3(F10_IN(z0))
F315_IN(z0, s(z1)) → c7(F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(F374_IN(z0, s(z1)))
F1_IN(c(0, z0)) → c3
F1_IN(c(s(z0), z1)) → c3
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3
U6'(f374_out1, z0, z1) → c3
F8_IN(z0) → c3
K tuples:none
Defined Rule Symbols:
f1_in, U1, U2, f315_in, U3, f374_in, U4, f10_in, U5, f372_in, U6, U7, f8_in, U8
Defined Pair Symbols:
F1_IN, F10_IN, F372_IN, U6', F8_IN, F315_IN, F374_IN
Compound Symbols:
c3, c7, c10, c3
(21) CdtKnowledgeProof (EQUIVALENT transformation)
The following tuples could be moved from S to K by knowledge propagation:
F1_IN(c(0, z0)) → c3(F8_IN(z0))
F1_IN(c(s(z0), z1)) → c3(F372_IN(z0, z1))
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
F8_IN(z0) → c3(F10_IN(z0))
F1_IN(c(0, z0)) → c3
F1_IN(c(s(z0), z1)) → c3
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3
U6'(f374_out1, z0, z1) → c3
F8_IN(z0) → c3
F8_IN(z0) → c3(F10_IN(z0))
F8_IN(z0) → c3
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3
(22) Obligation:
Complexity Dependency Tuples Problem
Rules:
f1_in(c(0, z0)) → U1(f8_in(z0), c(0, z0))
f1_in(c(s(z0), z1)) → U2(f372_in(z0, z1), c(s(z0), z1))
U1(f8_out1, c(0, z0)) → f1_out1
U1(f8_out2, c(0, z0)) → f1_out1
U2(f372_out1, c(s(z0), z1)) → f1_out1
f315_in(z0, 0) → f315_out1
f315_in(z0, s(z1)) → U3(f315_in(s(z0), z1), z0, s(z1))
U3(f315_out1, z0, s(z1)) → f315_out1
f374_in(0, z0) → f374_out1
f374_in(s(z0), z1) → U4(f374_in(z0, s(z1)), s(z0), z1)
U4(f374_out1, s(z0), z1) → f374_out1
f10_in(0) → f10_out1
f10_in(s(0)) → f10_out1
f10_in(s(s(0))) → f10_out1
f10_in(s(s(s(0)))) → f10_out1
f10_in(s(s(s(s(0))))) → f10_out1
f10_in(s(s(s(s(s(0)))))) → f10_out1
f10_in(s(s(s(s(s(s(0))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(0)))))))) → f10_out1
f10_in(s(s(s(s(s(s(s(s(z0))))))))) → U5(f315_in(s(s(s(s(s(s(s(0))))))), z0), s(s(s(s(s(s(s(s(z0)))))))))
U5(f315_out1, s(s(s(s(s(s(s(s(z0))))))))) → f10_out1
f372_in(z0, z1) → U6(f374_in(z0, z1), z0, z1)
U6(f374_out1, z0, z1) → U7(f315_in(z0, z1), z0, z1)
U7(f315_out1, z0, z1) → f372_out1
f8_in(z0) → U8(f10_in(z0), f11_in(z0), z0)
U8(f10_out1, z0, z1) → f8_out1
U8(z0, f11_out1, z1) → f8_out2
Tuples:
F1_IN(c(0, z0)) → c3(F8_IN(z0))
F1_IN(c(s(z0), z1)) → c3(F372_IN(z0, z1))
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(F315_IN(s(s(s(s(s(s(s(0))))))), z0))
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
F8_IN(z0) → c3(F10_IN(z0))
F315_IN(z0, s(z1)) → c7(F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(F374_IN(z0, s(z1)))
F1_IN(c(0, z0)) → c3
F1_IN(c(s(z0), z1)) → c3
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3
U6'(f374_out1, z0, z1) → c3
F8_IN(z0) → c3
S tuples:
F315_IN(z0, s(z1)) → c7(F315_IN(s(z0), z1))
F374_IN(s(z0), z1) → c10(F374_IN(z0, s(z1)))
K tuples:
F1_IN(c(0, z0)) → c3(F8_IN(z0))
F1_IN(c(s(z0), z1)) → c3(F372_IN(z0, z1))
F372_IN(z0, z1) → c3(U6'(f374_in(z0, z1), z0, z1))
F372_IN(z0, z1) → c3(F374_IN(z0, z1))
U6'(f374_out1, z0, z1) → c3(F315_IN(z0, z1))
F8_IN(z0) → c3(F10_IN(z0))
F1_IN(c(0, z0)) → c3
F1_IN(c(s(z0), z1)) → c3
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3
U6'(f374_out1, z0, z1) → c3
F8_IN(z0) → c3
F10_IN(s(s(s(s(s(s(s(s(z0))))))))) → c3(F315_IN(s(s(s(s(s(s(s(0))))))), z0))
Defined Rule Symbols:
f1_in, U1, U2, f315_in, U3, f374_in, U4, f10_in, U5, f372_in, U6, U7, f8_in, U8
Defined Pair Symbols:
F1_IN, F10_IN, F372_IN, U6', F8_IN, F315_IN, F374_IN
Compound Symbols:
c3, c7, c10, c3