/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).

(0) CpxTRS
(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 23 ms]
(2) CpxTRS
    (3) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
    (4) CpxRelTRS
    (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxRelTRS
    (7) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
    (8) CdtProblem
    (9) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CdtProblem
    (11) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CdtProblem
    (13) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CdtProblem
    (15) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
    (16) CdtProblem
    (17) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) CdtProblem
    (19) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (20) CdtProblem
    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 620 ms]
    (22) CdtProblem
    (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 63 ms]
    (24) CdtProblem
    (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 39 ms]
    (26) CdtProblem
    (27) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 40 ms]
    (28) CdtProblem
    (29) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 377 ms]
    (30) CdtProblem
    (31) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 343 ms]
    (32) CdtProblem
    (33) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (34) BOUNDS(1, 1)
(35) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(36) TRS for Loop Detection
    (37) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (38) BEST
        (39) proven lower bound
            (40) LowerBoundPropagationProof [FINISHED, 0 ms]
            (41) BOUNDS(n^1, INF)
        (42) TRS for Loop Detection


----------------------------------------

(0)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(O(x), O(y)) -> O(+(x, y))
   +(O(x), I(y)) -> I(+(x, y))
   +(I(x), O(y)) -> I(+(x, y))
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   +(x, +(y, z)) -> +(+(x, y), z)
   -(x, 0) -> x
   -(0, x) -> 0
   -(O(x), O(y)) -> O(-(x, y))
   -(O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(I(x), O(y)) -> I(-(x, y))
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(O(x), O(y)) -> ge(x, y)
   ge(O(x), I(y)) -> not(ge(y, x))
   ge(I(x), O(y)) -> ge(x, y)
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, O(x)) -> ge(0, x)
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0)
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
The following defined symbols can occur below the 0th argument of ge: Size, O, +, ge, -, not, Min, Max
The following defined symbols can occur below the 1th argument of ge: Size, O, +, ge, -, not, Max, Min
The following defined symbols can occur below the 0th argument of and: Size, O, +, if, ge, -, not, and, WB, Max, Min, BS
The following defined symbols can occur below the 1th argument of and: Size, O, +, if, ge, -, not, and, WB, Max, Min, BS
The following defined symbols can occur below the 0th argument of if: Size, O, +, ge, -, not
The following defined symbols can occur below the 1th argument of if: Size, O, +, ge, -, not
The following defined symbols can occur below the 2th argument of if: Size, O, +, ge, -, not
The following defined symbols can occur below the 0th argument of -: Size, O, +, ge, -, not, Log'
The following defined symbols can occur below the 1th argument of -: Size, O, +, ge, -, not
The following defined symbols can occur below the 0th argument of +: Size, O, +, ge, -, not, Log'
The following defined symbols can occur below the 1th argument of +: Size, O, +, ge, -, not
The following defined symbols can occur below the 0th argument of O: O, +, ge, -, not, Size, Log'
The following defined symbols can occur below the 0th argument of not: ge, not, Size, O, +, -, Min, Max

Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0)

----------------------------------------

(2)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(O(x), O(y)) -> O(+(x, y))
   +(O(x), I(y)) -> I(+(x, y))
   +(I(x), O(y)) -> I(+(x, y))
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   +(x, +(y, z)) -> +(+(x, y), z)
   -(x, 0) -> x
   -(0, x) -> 0
   -(O(x), O(y)) -> O(-(x, y))
   -(O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(I(x), O(y)) -> I(-(x, y))
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(O(x), O(y)) -> ge(x, y)
   ge(O(x), I(y)) -> not(ge(y, x))
   ge(I(x), O(y)) -> ge(x, y)
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, O(x)) -> ge(0, x)
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(3) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

(4)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   -(x, 0) -> x
   -(0, x) -> 0
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
   ge(0, c_O(x)) -> ge(0, x)
   ge(c_O(x), I(y)) -> not(ge(y, x))
   ge(c_O(x), c_O(y)) -> ge(x, y)
   +(c_O(x), I(y)) -> I(+(x, y))
   +(I(x), c_O(y)) -> I(+(x, y))
   -(I(x), c_O(y)) -> I(-(x, y))
   +(c_O(x), c_O(y)) -> O(+(x, y))
   -(c_O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(c_O(x), c_O(y)) -> O(-(x, y))
   +(x, c_+(y, z)) -> +(+(x, y), z)
   ge(I(x), c_O(y)) -> ge(x, y)

The (relative) TRS S consists of the following rules:

   O(x0) -> c_O(x0)
   +(x0, x1) -> c_+(x0, x1)

Rewrite Strategy: FULL
----------------------------------------

(5) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

The duplicating contexts are:
BS(N([], l, r))


The defined contexts are:
and([], x1)
if([], x1, x2)
ge([], x1)
ge(x0, [])
if(x0, [], x2)
ge(I(0), [])
-([], x1)
-(x0, [])
if(x0, x1, [])
and(x0, [])
+([], I(1))
+([], x1)
+(x0, [])
-([], I(1))
O([])
+([], I(0))
-([], I(0))
not([])
ge(0, [])


[] just represents basic- or constructor-terms in the following defined contexts:
ge([], x1)
ge(x0, [])


As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
----------------------------------------

(6)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   -(x, 0) -> x
   -(0, x) -> 0
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
   ge(0, c_O(x)) -> ge(0, x)
   ge(c_O(x), I(y)) -> not(ge(y, x))
   ge(c_O(x), c_O(y)) -> ge(x, y)
   +(c_O(x), I(y)) -> I(+(x, y))
   +(I(x), c_O(y)) -> I(+(x, y))
   -(I(x), c_O(y)) -> I(-(x, y))
   +(c_O(x), c_O(y)) -> O(+(x, y))
   -(c_O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(c_O(x), c_O(y)) -> O(-(x, y))
   +(x, c_+(y, z)) -> +(+(x, y), z)
   ge(I(x), c_O(y)) -> ge(x, y)

The (relative) TRS S consists of the following rules:

   O(x0) -> c_O(x0)
   +(x0, x1) -> c_+(x0, x1)

Rewrite Strategy: INNERMOST
----------------------------------------

(7) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   O(z0) -> c_O(z0)
   O(0) -> 0
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   not(true) -> false
   not(false) -> true
   and(z0, true) -> z0
   and(z0, false) -> false
   if(true, z0, z1) -> z0
   if(false, z0, z1) -> z1
   ge(I(z0), I(z1)) -> ge(z0, z1)
   ge(z0, 0) -> true
   ge(0, I(z0)) -> false
   ge(0, c_O(z0)) -> ge(0, z0)
   ge(c_O(z0), I(z1)) -> not(ge(z1, z0))
   ge(c_O(z0), c_O(z1)) -> ge(z0, z1)
   ge(I(z0), c_O(z1)) -> ge(z0, z1)
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
   Log(z0) -> -(Log'(z0), I(0))
   Val(L(z0)) -> z0
   Val(N(z0, l, r)) -> z0
   Min(L(z0)) -> z0
   Min(N(z0, l, r)) -> Min(l)
   Max(L(z0)) -> z0
   Max(N(z0, l, r)) -> Max(r)
   BS(L(z0)) -> true
   BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r)))
   Size(L(z0)) -> I(0)
   Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(z0)) -> true
   WB(N(z0, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
Tuples:
   O'(z0) -> c
   O'(0) -> c1
   +'(z0, z1) -> c2
   +'(0, z0) -> c3
   +'(z0, 0) -> c4
   +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(z0, 0) -> c10
   -'(0, z0) -> c11
   -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1))
   NOT(true) -> c16
   NOT(false) -> c17
   AND(z0, true) -> c18
   AND(z0, false) -> c19
   IF(true, z0, z1) -> c20
   IF(false, z0, z1) -> c21
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(z0, 0) -> c23
   GE(0, I(z0)) -> c24
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(0) -> c29
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0))
   VAL(L(z0)) -> c32
   VAL(N(z0, l, r)) -> c33
   MIN(L(z0)) -> c34
   MIN(N(z0, l, r)) -> c35(MIN(l))
   MAX(L(z0)) -> c36
   MAX(N(z0, l, r)) -> c37(MAX(r))
   BS'(L(z0)) -> c38
   BS'(N(z0, l, r)) -> c39(AND(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))), AND(ge(z0, Max(l)), ge(Min(r), z0)), GE(z0, Max(l)), MAX(l), GE(Min(r), z0), MIN(r), AND(BS(l), BS(r)), BS'(l), BS'(r))
   SIZE(L(z0)) -> c40
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r))
   WB'(L(z0)) -> c42
   WB'(N(z0, l, r)) -> c43(AND(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))), IF(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), GE(Size(l), Size(r)), SIZE(l), SIZE(r), GE(I(0), -(Size(l), Size(r))), -'(Size(l), Size(r)), SIZE(l), SIZE(r), GE(I(0), -(Size(r), Size(l))), -'(Size(r), Size(l)), SIZE(r), SIZE(l), AND(WB(l), WB(r)), WB'(l), WB'(r))
S tuples:
   O'(0) -> c1
   +'(0, z0) -> c3
   +'(z0, 0) -> c4
   +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(z0, 0) -> c10
   -'(0, z0) -> c11
   -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1))
   NOT(true) -> c16
   NOT(false) -> c17
   AND(z0, true) -> c18
   AND(z0, false) -> c19
   IF(true, z0, z1) -> c20
   IF(false, z0, z1) -> c21
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(z0, 0) -> c23
   GE(0, I(z0)) -> c24
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(0) -> c29
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0))
   VAL(L(z0)) -> c32
   VAL(N(z0, l, r)) -> c33
   MIN(L(z0)) -> c34
   MIN(N(z0, l, r)) -> c35(MIN(l))
   MAX(L(z0)) -> c36
   MAX(N(z0, l, r)) -> c37(MAX(r))
   BS'(L(z0)) -> c38
   BS'(N(z0, l, r)) -> c39(AND(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))), AND(ge(z0, Max(l)), ge(Min(r), z0)), GE(z0, Max(l)), MAX(l), GE(Min(r), z0), MIN(r), AND(BS(l), BS(r)), BS'(l), BS'(r))
   SIZE(L(z0)) -> c40
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r))
   WB'(L(z0)) -> c42
   WB'(N(z0, l, r)) -> c43(AND(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))), IF(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), GE(Size(l), Size(r)), SIZE(l), SIZE(r), GE(I(0), -(Size(l), Size(r))), -'(Size(l), Size(r)), SIZE(l), SIZE(r), GE(I(0), -(Size(r), Size(l))), -'(Size(r), Size(l)), SIZE(r), SIZE(l), AND(WB(l), WB(r)), WB'(l), WB'(r))
K tuples:none
Defined Rule Symbols:   O_1, +_2, -_2, not_1, and_2, if_3, ge_2, Log'_1, Log_1, Val_1, Min_1, Max_1, BS_1, Size_1, WB_1

Defined Pair Symbols:   O'_1, +'_2, -'_2, NOT_1, AND_2, IF_3, GE_2, LOG'_1, LOG_1, VAL_1, MIN_1, MAX_1, BS'_1, SIZE_1, WB'_1

Compound Symbols:   c, c1, c2, c3, c4, c5_3, c6_1, c7_1, c8_2, c9_2, c10, c11, c12_2, c13_1, c14_2, c15_2, c16, c17, c18, c19, c20, c21, c22_1, c23, c24, c25_1, c26_2, c27_1, c28_1, c29, c30_2, c31_2, c32, c33, c34, c35_1, c36, c37_1, c38, c39_9, c40, c41_4, c42, c43_16


----------------------------------------

(9) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 27 trailing nodes:
   MAX(L(z0)) -> c36
   SIZE(L(z0)) -> c40
   AND(z0, true) -> c18
   +'(0, z0) -> c3
   VAL(L(z0)) -> c32
   WB'(N(z0, l, r)) -> c43(AND(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r))), IF(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), GE(Size(l), Size(r)), SIZE(l), SIZE(r), GE(I(0), -(Size(l), Size(r))), -'(Size(l), Size(r)), SIZE(l), SIZE(r), GE(I(0), -(Size(r), Size(l))), -'(Size(r), Size(l)), SIZE(r), SIZE(l), AND(WB(l), WB(r)), WB'(l), WB'(r))
   -'(0, z0) -> c11
   -'(z0, 0) -> c10
   AND(z0, false) -> c19
   MAX(N(z0, l, r)) -> c37(MAX(r))
   GE(z0, 0) -> c23
   MIN(L(z0)) -> c34
   LOG'(0) -> c29
   IF(false, z0, z1) -> c21
   NOT(true) -> c16
   +'(z0, 0) -> c4
   WB'(L(z0)) -> c42
   IF(true, z0, z1) -> c20
   O'(0) -> c1
   NOT(false) -> c17
   BS'(L(z0)) -> c38
   MIN(N(z0, l, r)) -> c35(MIN(l))
   VAL(N(z0, l, r)) -> c33
   GE(0, I(z0)) -> c24
   BS'(N(z0, l, r)) -> c39(AND(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))), AND(ge(z0, Max(l)), ge(Min(r), z0)), GE(z0, Max(l)), MAX(l), GE(Min(r), z0), MIN(r), AND(BS(l), BS(r)), BS'(l), BS'(r))
   O'(z0) -> c
   +'(z0, z1) -> c2

----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   O(z0) -> c_O(z0)
   O(0) -> 0
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   not(true) -> false
   not(false) -> true
   and(z0, true) -> z0
   and(z0, false) -> false
   if(true, z0, z1) -> z0
   if(false, z0, z1) -> z1
   ge(I(z0), I(z1)) -> ge(z0, z1)
   ge(z0, 0) -> true
   ge(0, I(z0)) -> false
   ge(0, c_O(z0)) -> ge(0, z0)
   ge(c_O(z0), I(z1)) -> not(ge(z1, z0))
   ge(c_O(z0), c_O(z1)) -> ge(z0, z1)
   ge(I(z0), c_O(z1)) -> ge(z0, z1)
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
   Log(z0) -> -(Log'(z0), I(0))
   Val(L(z0)) -> z0
   Val(N(z0, l, r)) -> z0
   Min(L(z0)) -> z0
   Min(N(z0, l, r)) -> Min(l)
   Max(L(z0)) -> z0
   Max(N(z0, l, r)) -> Max(r)
   BS(L(z0)) -> true
   BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r)))
   Size(L(z0)) -> I(0)
   Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(z0)) -> true
   WB(N(z0, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
Tuples:
   +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r))
S tuples:
   +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r))
K tuples:none
Defined Rule Symbols:   O_1, +_2, -_2, not_1, and_2, if_3, ge_2, Log'_1, Log_1, Val_1, Min_1, Max_1, BS_1, Size_1, WB_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, LOG_1, SIZE_1

Compound Symbols:   c5_3, c6_1, c7_1, c8_2, c9_2, c12_2, c13_1, c14_2, c15_2, c22_1, c25_1, c26_2, c27_1, c28_1, c30_2, c31_2, c41_4


----------------------------------------

(11) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
Removed 8 trailing tuple parts
----------------------------------------

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   O(z0) -> c_O(z0)
   O(0) -> 0
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   not(true) -> false
   not(false) -> true
   and(z0, true) -> z0
   and(z0, false) -> false
   if(true, z0, z1) -> z0
   if(false, z0, z1) -> z1
   ge(I(z0), I(z1)) -> ge(z0, z1)
   ge(z0, 0) -> true
   ge(0, I(z0)) -> false
   ge(0, c_O(z0)) -> ge(0, z0)
   ge(c_O(z0), I(z1)) -> not(ge(z1, z0))
   ge(c_O(z0), c_O(z1)) -> ge(z0, z1)
   ge(I(z0), c_O(z1)) -> ge(z0, z1)
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
   Log(z0) -> -(Log'(z0), I(0))
   Val(L(z0)) -> z0
   Val(N(z0, l, r)) -> z0
   Min(L(z0)) -> z0
   Min(N(z0, l, r)) -> Min(l)
   Max(L(z0)) -> z0
   Max(N(z0, l, r)) -> Max(r)
   BS(L(z0)) -> true
   BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r)))
   Size(L(z0)) -> I(0)
   Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(z0)) -> true
   WB(N(z0, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
K tuples:none
Defined Rule Symbols:   O_1, +_2, -_2, not_1, and_2, if_3, ge_2, Log'_1, Log_1, Val_1, Min_1, Max_1, BS_1, Size_1, WB_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, LOG_1, SIZE_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c31_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1


----------------------------------------

(13) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID))
Split RHS of tuples not part of any SCC
----------------------------------------

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   O(z0) -> c_O(z0)
   O(0) -> 0
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   not(true) -> false
   not(false) -> true
   and(z0, true) -> z0
   and(z0, false) -> false
   if(true, z0, z1) -> z0
   if(false, z0, z1) -> z1
   ge(I(z0), I(z1)) -> ge(z0, z1)
   ge(z0, 0) -> true
   ge(0, I(z0)) -> false
   ge(0, c_O(z0)) -> ge(0, z0)
   ge(c_O(z0), I(z1)) -> not(ge(z1, z0))
   ge(c_O(z0), c_O(z1)) -> ge(z0, z1)
   ge(I(z0), c_O(z1)) -> ge(z0, z1)
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
   Log(z0) -> -(Log'(z0), I(0))
   Val(L(z0)) -> z0
   Val(N(z0, l, r)) -> z0
   Min(L(z0)) -> z0
   Min(N(z0, l, r)) -> Min(l)
   Max(L(z0)) -> z0
   Max(N(z0, l, r)) -> Max(r)
   BS(L(z0)) -> true
   BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r)))
   Size(L(z0)) -> I(0)
   Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(z0)) -> true
   WB(N(z0, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   LOG(z0) -> c(LOG'(z0))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   LOG(z0) -> c(LOG'(z0))
K tuples:none
Defined Rule Symbols:   O_1, +_2, -_2, not_1, and_2, if_3, ge_2, Log'_1, Log_1, Val_1, Min_1, Max_1, BS_1, Size_1, WB_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(15) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 1 leading nodes:
   LOG(z0) -> c(LOG'(z0))

----------------------------------------

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   O(z0) -> c_O(z0)
   O(0) -> 0
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   not(true) -> false
   not(false) -> true
   and(z0, true) -> z0
   and(z0, false) -> false
   if(true, z0, z1) -> z0
   if(false, z0, z1) -> z1
   ge(I(z0), I(z1)) -> ge(z0, z1)
   ge(z0, 0) -> true
   ge(0, I(z0)) -> false
   ge(0, c_O(z0)) -> ge(0, z0)
   ge(c_O(z0), I(z1)) -> not(ge(z1, z0))
   ge(c_O(z0), c_O(z1)) -> ge(z0, z1)
   ge(I(z0), c_O(z1)) -> ge(z0, z1)
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
   Log(z0) -> -(Log'(z0), I(0))
   Val(L(z0)) -> z0
   Val(N(z0, l, r)) -> z0
   Min(L(z0)) -> z0
   Min(N(z0, l, r)) -> Min(l)
   Max(L(z0)) -> z0
   Max(N(z0, l, r)) -> Max(r)
   BS(L(z0)) -> true
   BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r)))
   Size(L(z0)) -> I(0)
   Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(z0)) -> true
   WB(N(z0, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
K tuples:none
Defined Rule Symbols:   O_1, +_2, -_2, not_1, and_2, if_3, ge_2, Log'_1, Log_1, Val_1, Min_1, Max_1, BS_1, Size_1, WB_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(17) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
The following tuples could be moved from S to K by knowledge propagation:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))

----------------------------------------

(18)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   O(z0) -> c_O(z0)
   O(0) -> 0
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   not(true) -> false
   not(false) -> true
   and(z0, true) -> z0
   and(z0, false) -> false
   if(true, z0, z1) -> z0
   if(false, z0, z1) -> z1
   ge(I(z0), I(z1)) -> ge(z0, z1)
   ge(z0, 0) -> true
   ge(0, I(z0)) -> false
   ge(0, c_O(z0)) -> ge(0, z0)
   ge(c_O(z0), I(z1)) -> not(ge(z1, z0))
   ge(c_O(z0), c_O(z1)) -> ge(z0, z1)
   ge(I(z0), c_O(z1)) -> ge(z0, z1)
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
   Log(z0) -> -(Log'(z0), I(0))
   Val(L(z0)) -> z0
   Val(N(z0, l, r)) -> z0
   Min(L(z0)) -> z0
   Min(N(z0, l, r)) -> Min(l)
   Max(L(z0)) -> z0
   Max(N(z0, l, r)) -> Max(r)
   BS(L(z0)) -> true
   BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r)))
   Size(L(z0)) -> I(0)
   Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(z0)) -> true
   WB(N(z0, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
Defined Rule Symbols:   O_1, +_2, -_2, not_1, and_2, if_3, ge_2, Log'_1, Log_1, Val_1, Min_1, Max_1, BS_1, Size_1, WB_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(19) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   not(true) -> false
   not(false) -> true
   and(z0, true) -> z0
   and(z0, false) -> false
   if(true, z0, z1) -> z0
   if(false, z0, z1) -> z1
   ge(I(z0), I(z1)) -> ge(z0, z1)
   ge(z0, 0) -> true
   ge(0, I(z0)) -> false
   ge(0, c_O(z0)) -> ge(0, z0)
   ge(c_O(z0), I(z1)) -> not(ge(z1, z0))
   ge(c_O(z0), c_O(z1)) -> ge(z0, z1)
   ge(I(z0), c_O(z1)) -> ge(z0, z1)
   Log(z0) -> -(Log'(z0), I(0))
   Val(L(z0)) -> z0
   Val(N(z0, l, r)) -> z0
   Min(L(z0)) -> z0
   Min(N(z0, l, r)) -> Min(l)
   Max(L(z0)) -> z0
   Max(N(z0, l, r)) -> Max(r)
   BS(L(z0)) -> true
   BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r)))
   Size(L(z0)) -> I(0)
   Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(z0)) -> true
   WB(N(z0, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))

----------------------------------------

(20)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   O(z0) -> c_O(z0)
   O(0) -> 0
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
Defined Rule Symbols:   +_2, O_1, -_2, Log'_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
We considered the (Usable) Rules:none
And the Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(+(x_1, x_2)) = x_2 + x_2^2
   POL(+'(x_1, x_2)) = 0
   POL(-(x_1, x_2)) = 0
   POL(-'(x_1, x_2)) = 0
   POL(0) = 0
   POL(1) = 0
   POL(GE(x_1, x_2)) = [2]x_1 + [2]x_2
   POL(I(x_1)) = [2] + x_1
   POL(LOG(x_1)) = [2] + x_1 + [2]x_1^2
   POL(LOG'(x_1)) = 0
   POL(Log'(x_1)) = [2]x_1^2
   POL(N(x_1, x_2, x_3)) = 0
   POL(O(x_1)) = 0
   POL(SIZE(x_1)) = [2]
   POL(Size(x_1)) = 0
   POL(c(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c14(x_1, x_2)) = x_1 + x_2
   POL(c15(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28(x_1)) = x_1
   POL(c30(x_1, x_2)) = x_1 + x_2
   POL(c41(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(c_+(x_1, x_2)) = 0
   POL(c_O(x_1)) = x_1
   POL(l) = 0
   POL(r) = 0

----------------------------------------

(22)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   O(z0) -> c_O(z0)
   O(0) -> 0
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
Defined Rule Symbols:   +_2, O_1, -_2, Log'_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(23) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
We considered the (Usable) Rules:none
And the Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(+(x_1, x_2)) = 0
   POL(+'(x_1, x_2)) = 0
   POL(-(x_1, x_2)) = [1]
   POL(-'(x_1, x_2)) = 0
   POL(0) = [1]
   POL(1) = [1]
   POL(GE(x_1, x_2)) = x_1 + x_2
   POL(I(x_1)) = [1] + x_1
   POL(LOG(x_1)) = 0
   POL(LOG'(x_1)) = x_1
   POL(Log'(x_1)) = x_1
   POL(N(x_1, x_2, x_3)) = x_2
   POL(O(x_1)) = 0
   POL(SIZE(x_1)) = x_1
   POL(Size(x_1)) = [1] + x_1
   POL(c(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c14(x_1, x_2)) = x_1 + x_2
   POL(c15(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28(x_1)) = x_1
   POL(c30(x_1, x_2)) = x_1 + x_2
   POL(c41(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(c_+(x_1, x_2)) = [1] + x_1 + x_2
   POL(c_O(x_1)) = [1] + x_1
   POL(l) = 0
   POL(r) = [1]

----------------------------------------

(24)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   O(z0) -> c_O(z0)
   O(0) -> 0
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
Defined Rule Symbols:   +_2, O_1, -_2, Log'_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(25) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
We considered the (Usable) Rules:none
And the Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(+(x_1, x_2)) = 0
   POL(+'(x_1, x_2)) = x_2
   POL(-(x_1, x_2)) = [1]
   POL(-'(x_1, x_2)) = 0
   POL(0) = 0
   POL(1) = 0
   POL(GE(x_1, x_2)) = x_1 + x_2
   POL(I(x_1)) = x_1
   POL(LOG(x_1)) = 0
   POL(LOG'(x_1)) = x_1
   POL(Log'(x_1)) = [1] + x_1
   POL(N(x_1, x_2, x_3)) = x_2
   POL(O(x_1)) = 0
   POL(SIZE(x_1)) = x_1
   POL(Size(x_1)) = [1] + x_1
   POL(c(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c14(x_1, x_2)) = x_1 + x_2
   POL(c15(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28(x_1)) = x_1
   POL(c30(x_1, x_2)) = x_1 + x_2
   POL(c41(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(c_+(x_1, x_2)) = [1] + x_1 + x_2
   POL(c_O(x_1)) = [1] + x_1
   POL(l) = 0
   POL(r) = [1]

----------------------------------------

(26)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   O(z0) -> c_O(z0)
   O(0) -> 0
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
Defined Rule Symbols:   +_2, O_1, -_2, Log'_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(27) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
We considered the (Usable) Rules:none
And the Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(+(x_1, x_2)) = 0
   POL(+'(x_1, x_2)) = x_2
   POL(-(x_1, x_2)) = [1]
   POL(-'(x_1, x_2)) = x_2
   POL(0) = 0
   POL(1) = 0
   POL(GE(x_1, x_2)) = x_1 + x_2
   POL(I(x_1)) = [1] + x_1
   POL(LOG(x_1)) = [1]
   POL(LOG'(x_1)) = x_1
   POL(Log'(x_1)) = [1] + x_1
   POL(N(x_1, x_2, x_3)) = [1] + x_2 + x_3
   POL(O(x_1)) = 0
   POL(SIZE(x_1)) = [1] + x_1
   POL(Size(x_1)) = [1] + x_1
   POL(c(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c14(x_1, x_2)) = x_1 + x_2
   POL(c15(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28(x_1)) = x_1
   POL(c30(x_1, x_2)) = x_1 + x_2
   POL(c41(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(c_+(x_1, x_2)) = [1] + x_1 + x_2
   POL(c_O(x_1)) = [1] + x_1
   POL(l) = [1]
   POL(r) = [1]

----------------------------------------

(28)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   O(z0) -> c_O(z0)
   O(0) -> 0
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
Defined Rule Symbols:   +_2, O_1, -_2, Log'_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(29) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
We considered the (Usable) Rules:
   O(z0) -> c_O(z0)
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, z1) -> c_+(z0, z1)
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   O(0) -> 0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   Log'(0) -> 0
   +(0, z0) -> z0
   +(z0, 0) -> z0
   Log'(I(z0)) -> +(Log'(z0), I(0))
And the Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(+(x_1, x_2)) = x_1 + x_2
   POL(+'(x_1, x_2)) = x_2^2 + [2]x_1*x_2
   POL(-(x_1, x_2)) = 0
   POL(-'(x_1, x_2)) = 0
   POL(0) = 0
   POL(1) = 0
   POL(GE(x_1, x_2)) = 0
   POL(I(x_1)) = [1] + x_1
   POL(LOG(x_1)) = [2] + x_1 + x_1^2
   POL(LOG'(x_1)) = [2]x_1 + [2]x_1^2
   POL(Log'(x_1)) = x_1
   POL(N(x_1, x_2, x_3)) = 0
   POL(O(x_1)) = x_1
   POL(SIZE(x_1)) = [1]
   POL(Size(x_1)) = 0
   POL(c(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c14(x_1, x_2)) = x_1 + x_2
   POL(c15(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28(x_1)) = x_1
   POL(c30(x_1, x_2)) = x_1 + x_2
   POL(c41(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(c_+(x_1, x_2)) = x_1 + x_2
   POL(c_O(x_1)) = x_1
   POL(l) = 0
   POL(r) = 0

----------------------------------------

(30)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   O(z0) -> c_O(z0)
   O(0) -> 0
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
Defined Rule Symbols:   +_2, O_1, -_2, Log'_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(31) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
We considered the (Usable) Rules:
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   -(0, z0) -> 0
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   -(I(z0), I(z1)) -> O(-(z0, z1))
   O(0) -> 0
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   O(z0) -> c_O(z0)
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, z1) -> c_+(z0, z1)
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   -(z0, 0) -> z0
   +(0, z0) -> z0
   +(z0, 0) -> z0
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
And the Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(+(x_1, x_2)) = x_1 + x_2
   POL(+'(x_1, x_2)) = 0
   POL(-(x_1, x_2)) = x_1
   POL(-'(x_1, x_2)) = x_2^2 + x_1*x_2
   POL(0) = 0
   POL(1) = 0
   POL(GE(x_1, x_2)) = 0
   POL(I(x_1)) = [1] + x_1
   POL(LOG(x_1)) = [2] + x_1 + [2]x_1^2
   POL(LOG'(x_1)) = x_1
   POL(Log'(x_1)) = [1] + [2]x_1^2
   POL(N(x_1, x_2, x_3)) = [2] + x_2
   POL(O(x_1)) = [1] + x_1
   POL(SIZE(x_1)) = [2] + [2]x_1 + x_1^2
   POL(Size(x_1)) = 0
   POL(c(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c13(x_1)) = x_1
   POL(c14(x_1, x_2)) = x_1 + x_2
   POL(c15(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c25(x_1)) = x_1
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28(x_1)) = x_1
   POL(c30(x_1, x_2)) = x_1 + x_2
   POL(c41(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(c_+(x_1, x_2)) = x_1 + x_2
   POL(c_O(x_1)) = [1] + x_1
   POL(l) = [2]
   POL(r) = 0

----------------------------------------

(32)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   +(z0, z1) -> c_+(z0, z1)
   +(0, z0) -> z0
   +(z0, 0) -> z0
   +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0)))
   +(c_O(z0), I(z1)) -> I(+(z0, z1))
   +(I(z0), c_O(z1)) -> I(+(z0, z1))
   +(c_O(z0), c_O(z1)) -> O(+(z0, z1))
   +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2)
   O(z0) -> c_O(z0)
   O(0) -> 0
   -(z0, 0) -> z0
   -(0, z0) -> 0
   -(I(z0), I(z1)) -> O(-(z0, z1))
   -(I(z0), c_O(z1)) -> I(-(z0, z1))
   -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1)))
   -(c_O(z0), c_O(z1)) -> O(-(z0, z1))
   Log'(0) -> 0
   Log'(I(z0)) -> +(Log'(z0), I(0))
Tuples:
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
S tuples:none
K tuples:
   SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)))
   LOG(z0) -> c(-'(Log'(z0), I(0)))
   GE(I(z0), I(z1)) -> c22(GE(z0, z1))
   GE(I(z0), c_O(z1)) -> c28(GE(z0, z1))
   GE(c_O(z0), I(z1)) -> c26(GE(z1, z0))
   GE(0, c_O(z0)) -> c25(GE(0, z0))
   GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1))
   LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0))
   +'(I(z0), c_O(z1)) -> c7(+'(z0, z1))
   +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1))
   +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1))
   +'(c_O(z0), I(z1)) -> c6(+'(z0, z1))
   -'(I(z0), c_O(z1)) -> c13(-'(z0, z1))
   -'(I(z0), I(z1)) -> c12(-'(z0, z1))
   -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1))
   +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1))
   -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1))
Defined Rule Symbols:   +_2, O_1, -_2, Log'_1

Defined Pair Symbols:   +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1

Compound Symbols:   c6_1, c7_1, c9_2, c13_1, c14_2, c22_1, c25_1, c27_1, c28_1, c30_2, c5_2, c8_1, c12_1, c15_1, c26_1, c41_1, c_1


----------------------------------------

(33) SIsEmptyProof (BOTH BOUNDS(ID, ID))
The set S is empty
----------------------------------------

(34)
BOUNDS(1, 1)

----------------------------------------

(35) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(36)
Obligation:
Analyzing the following TRS for decreasing loops:

The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(O(x), O(y)) -> O(+(x, y))
   +(O(x), I(y)) -> I(+(x, y))
   +(I(x), O(y)) -> I(+(x, y))
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   +(x, +(y, z)) -> +(+(x, y), z)
   -(x, 0) -> x
   -(0, x) -> 0
   -(O(x), O(y)) -> O(-(x, y))
   -(O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(I(x), O(y)) -> I(-(x, y))
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(O(x), O(y)) -> ge(x, y)
   ge(O(x), I(y)) -> not(ge(y, x))
   ge(I(x), O(y)) -> ge(x, y)
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, O(x)) -> ge(0, x)
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0)
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(37) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

+(I(x), I(y)) ->^+ O(+(+(x, y), I(0)))

gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0].

The pumping substitution is [x / I(x), y / I(y)].

The result substitution is [ ].




----------------------------------------

(38)
Complex Obligation (BEST)

----------------------------------------

(39)
Obligation:
Proved the lower bound n^1 for the following obligation:

The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(O(x), O(y)) -> O(+(x, y))
   +(O(x), I(y)) -> I(+(x, y))
   +(I(x), O(y)) -> I(+(x, y))
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   +(x, +(y, z)) -> +(+(x, y), z)
   -(x, 0) -> x
   -(0, x) -> 0
   -(O(x), O(y)) -> O(-(x, y))
   -(O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(I(x), O(y)) -> I(-(x, y))
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(O(x), O(y)) -> ge(x, y)
   ge(O(x), I(y)) -> not(ge(y, x))
   ge(I(x), O(y)) -> ge(x, y)
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, O(x)) -> ge(0, x)
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0)
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(40) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(41)
BOUNDS(n^1, INF)

----------------------------------------

(42)
Obligation:
Analyzing the following TRS for decreasing loops:

The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(O(x), O(y)) -> O(+(x, y))
   +(O(x), I(y)) -> I(+(x, y))
   +(I(x), O(y)) -> I(+(x, y))
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   +(x, +(y, z)) -> +(+(x, y), z)
   -(x, 0) -> x
   -(0, x) -> 0
   -(O(x), O(y)) -> O(-(x, y))
   -(O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(I(x), O(y)) -> I(-(x, y))
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(O(x), O(y)) -> ge(x, y)
   ge(O(x), I(y)) -> not(ge(y, x))
   ge(I(x), O(y)) -> ge(x, y)
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, O(x)) -> ge(0, x)
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0)
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))

S is empty.
Rewrite Strategy: FULL