622.70/291.53 WORST_CASE(Omega(n^1), O(n^2)) 622.70/291.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 622.70/291.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 622.70/291.55 622.70/291.55 622.70/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 622.70/291.55 622.70/291.55 (0) CpxTRS 622.70/291.55 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 622.70/291.55 (2) CpxTRS 622.70/291.55 (3) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms] 622.70/291.55 (4) CpxRelTRS 622.70/291.55 (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 48 ms] 622.70/291.55 (6) CpxRelTRS 622.70/291.55 (7) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 622.70/291.55 (8) CdtProblem 622.70/291.55 (9) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (10) CdtProblem 622.70/291.55 (11) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (12) CdtProblem 622.70/291.55 (13) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (14) CdtProblem 622.70/291.55 (15) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 622.70/291.55 (16) CdtProblem 622.70/291.55 (17) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (18) CdtProblem 622.70/291.55 (19) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (20) CdtProblem 622.70/291.55 (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 174 ms] 622.70/291.55 (22) CdtProblem 622.70/291.55 (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 67 ms] 622.70/291.55 (24) CdtProblem 622.70/291.55 (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 38 ms] 622.70/291.55 (26) CdtProblem 622.70/291.55 (27) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 43 ms] 622.70/291.55 (28) CdtProblem 622.70/291.55 (29) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 367 ms] 622.70/291.55 (30) CdtProblem 622.70/291.55 (31) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 372 ms] 622.70/291.55 (32) CdtProblem 622.70/291.55 (33) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (34) BOUNDS(1, 1) 622.70/291.55 (35) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (36) CpxTRS 622.70/291.55 (37) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 622.70/291.55 (38) typed CpxTrs 622.70/291.55 (39) OrderProof [LOWER BOUND(ID), 0 ms] 622.70/291.55 (40) typed CpxTrs 622.70/291.55 (41) RewriteLemmaProof [LOWER BOUND(ID), 2293 ms] 622.70/291.55 (42) BEST 622.70/291.55 (43) proven lower bound 622.70/291.55 (44) LowerBoundPropagationProof [FINISHED, 0 ms] 622.70/291.55 (45) BOUNDS(n^1, INF) 622.70/291.55 (46) typed CpxTrs 622.70/291.55 (47) RewriteLemmaProof [LOWER BOUND(ID), 65 ms] 622.70/291.55 (48) typed CpxTrs 622.70/291.55 (49) RewriteLemmaProof [LOWER BOUND(ID), 104 ms] 622.70/291.55 (50) typed CpxTrs 622.70/291.55 (51) RewriteLemmaProof [LOWER BOUND(ID), 452 ms] 622.70/291.55 (52) typed CpxTrs 622.70/291.55 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (0) 622.70/291.55 Obligation: 622.70/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 622.70/291.55 622.70/291.55 622.70/291.55 The TRS R consists of the following rules: 622.70/291.55 622.70/291.55 O(0) -> 0 622.70/291.55 +(0, x) -> x 622.70/291.55 +(x, 0) -> x 622.70/291.55 +(O(x), O(y)) -> O(+(x, y)) 622.70/291.55 +(O(x), I(y)) -> I(+(x, y)) 622.70/291.55 +(I(x), O(y)) -> I(+(x, y)) 622.70/291.55 +(I(x), I(y)) -> O(+(+(x, y), I(0))) 622.70/291.55 +(x, +(y, z)) -> +(+(x, y), z) 622.70/291.55 -(x, 0) -> x 622.70/291.55 -(0, x) -> 0 622.70/291.55 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.55 -(O(x), I(y)) -> I(-(-(x, y), I(1))) 622.70/291.55 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.55 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(x, true) -> x 622.70/291.55 and(x, false) -> false 622.70/291.55 if(true, x, y) -> x 622.70/291.55 if(false, x, y) -> y 622.70/291.55 ge(O(x), O(y)) -> ge(x, y) 622.70/291.55 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.55 ge(I(x), O(y)) -> ge(x, y) 622.70/291.55 ge(I(x), I(y)) -> ge(x, y) 622.70/291.55 ge(x, 0) -> true 622.70/291.55 ge(0, O(x)) -> ge(0, x) 622.70/291.55 ge(0, I(x)) -> false 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(x)) -> +(Log'(x), I(0)) 622.70/291.55 Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) 622.70/291.55 Log(x) -> -(Log'(x), I(0)) 622.70/291.55 Val(L(x)) -> x 622.70/291.55 Val(N(x, l, r)) -> x 622.70/291.55 Min(L(x)) -> x 622.70/291.55 Min(N(x, l, r)) -> Min(l) 622.70/291.55 Max(L(x)) -> x 622.70/291.55 Max(N(x, l, r)) -> Max(r) 622.70/291.55 BS(L(x)) -> true 622.70/291.55 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.55 Size(L(x)) -> I(0) 622.70/291.55 Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(x)) -> true 622.70/291.55 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))) 622.70/291.55 622.70/291.55 S is empty. 622.70/291.55 Rewrite Strategy: FULL 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 622.70/291.55 The following defined symbols can occur below the 0th argument of ge: Size, O, +, ge, -, not, Min, Max 622.70/291.55 The following defined symbols can occur below the 1th argument of ge: Size, O, +, ge, -, not, Max, Min 622.70/291.55 The following defined symbols can occur below the 0th argument of and: Size, O, +, if, ge, -, not, and, WB, Max, Min, BS 622.70/291.55 The following defined symbols can occur below the 1th argument of and: Size, O, +, if, ge, -, and, not, WB, Max, Min, BS 622.70/291.55 The following defined symbols can occur below the 0th argument of if: Size, O, +, ge, -, not 622.70/291.55 The following defined symbols can occur below the 1th argument of if: Size, O, +, ge, -, not 622.70/291.55 The following defined symbols can occur below the 2th argument of if: Size, O, +, ge, -, not 622.70/291.55 The following defined symbols can occur below the 0th argument of -: Size, O, +, ge, -, not, Log' 622.70/291.55 The following defined symbols can occur below the 1th argument of -: Size, O, +, ge, -, not 622.70/291.55 The following defined symbols can occur below the 0th argument of +: Size, O, +, ge, -, not, Log' 622.70/291.55 The following defined symbols can occur below the 1th argument of +: Size, O, +, ge, -, not 622.70/291.55 The following defined symbols can occur below the 0th argument of O: O, +, ge, -, not, Size, Log' 622.70/291.55 The following defined symbols can occur below the 0th argument of not: ge, not, Size, O, +, -, Min, Max 622.70/291.55 622.70/291.55 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 622.70/291.55 Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0) 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (2) 622.70/291.55 Obligation: 622.70/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 622.70/291.55 622.70/291.55 622.70/291.55 The TRS R consists of the following rules: 622.70/291.55 622.70/291.55 O(0) -> 0 622.70/291.55 +(0, x) -> x 622.70/291.55 +(x, 0) -> x 622.70/291.55 +(O(x), O(y)) -> O(+(x, y)) 622.70/291.55 +(O(x), I(y)) -> I(+(x, y)) 622.70/291.55 +(I(x), O(y)) -> I(+(x, y)) 622.70/291.55 +(I(x), I(y)) -> O(+(+(x, y), I(0))) 622.70/291.55 +(x, +(y, z)) -> +(+(x, y), z) 622.70/291.55 -(x, 0) -> x 622.70/291.55 -(0, x) -> 0 622.70/291.55 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.55 -(O(x), I(y)) -> I(-(-(x, y), I(1))) 622.70/291.55 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.55 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(x, true) -> x 622.70/291.55 and(x, false) -> false 622.70/291.55 if(true, x, y) -> x 622.70/291.55 if(false, x, y) -> y 622.70/291.55 ge(O(x), O(y)) -> ge(x, y) 622.70/291.55 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.55 ge(I(x), O(y)) -> ge(x, y) 622.70/291.55 ge(I(x), I(y)) -> ge(x, y) 622.70/291.55 ge(x, 0) -> true 622.70/291.55 ge(0, O(x)) -> ge(0, x) 622.70/291.55 ge(0, I(x)) -> false 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(x)) -> +(Log'(x), I(0)) 622.70/291.55 Log(x) -> -(Log'(x), I(0)) 622.70/291.55 Val(L(x)) -> x 622.70/291.55 Val(N(x, l, r)) -> x 622.70/291.55 Min(L(x)) -> x 622.70/291.55 Min(N(x, l, r)) -> Min(l) 622.70/291.55 Max(L(x)) -> x 622.70/291.55 Max(N(x, l, r)) -> Max(r) 622.70/291.55 BS(L(x)) -> true 622.70/291.55 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.55 Size(L(x)) -> I(0) 622.70/291.55 Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(x)) -> true 622.70/291.55 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))) 622.70/291.55 622.70/291.55 S is empty. 622.70/291.55 Rewrite Strategy: FULL 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (3) NonCtorToCtorProof (UPPER BOUND(ID)) 622.70/291.55 transformed non-ctor to ctor-system 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (4) 622.70/291.55 Obligation: 622.70/291.55 The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). 622.70/291.55 622.70/291.55 622.70/291.55 The TRS R consists of the following rules: 622.70/291.55 622.70/291.55 O(0) -> 0 622.70/291.55 +(0, x) -> x 622.70/291.55 +(x, 0) -> x 622.70/291.55 +(I(x), I(y)) -> O(+(+(x, y), I(0))) 622.70/291.55 -(x, 0) -> x 622.70/291.55 -(0, x) -> 0 622.70/291.55 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(x, true) -> x 622.70/291.55 and(x, false) -> false 622.70/291.55 if(true, x, y) -> x 622.70/291.55 if(false, x, y) -> y 622.70/291.55 ge(I(x), I(y)) -> ge(x, y) 622.70/291.55 ge(x, 0) -> true 622.70/291.55 ge(0, I(x)) -> false 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(x)) -> +(Log'(x), I(0)) 622.70/291.55 Log(x) -> -(Log'(x), I(0)) 622.70/291.55 Val(L(x)) -> x 622.70/291.55 Val(N(x, l, r)) -> x 622.70/291.55 Min(L(x)) -> x 622.70/291.55 Min(N(x, l, r)) -> Min(l) 622.70/291.55 Max(L(x)) -> x 622.70/291.55 Max(N(x, l, r)) -> Max(r) 622.70/291.55 BS(L(x)) -> true 622.70/291.55 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.55 Size(L(x)) -> I(0) 622.70/291.55 Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(x)) -> true 622.70/291.55 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))) 622.70/291.55 ge(0, c_O(x)) -> ge(0, x) 622.70/291.55 ge(c_O(x), I(y)) -> not(ge(y, x)) 622.70/291.55 ge(c_O(x), c_O(y)) -> ge(x, y) 622.70/291.55 +(c_O(x), I(y)) -> I(+(x, y)) 622.70/291.55 +(I(x), c_O(y)) -> I(+(x, y)) 622.70/291.55 -(I(x), c_O(y)) -> I(-(x, y)) 622.70/291.55 +(c_O(x), c_O(y)) -> O(+(x, y)) 622.70/291.55 -(c_O(x), I(y)) -> I(-(-(x, y), I(1))) 622.70/291.55 -(c_O(x), c_O(y)) -> O(-(x, y)) 622.70/291.55 +(x, c_+(y, z)) -> +(+(x, y), z) 622.70/291.55 ge(I(x), c_O(y)) -> ge(x, y) 622.70/291.55 622.70/291.55 The (relative) TRS S consists of the following rules: 622.70/291.55 622.70/291.55 O(x0) -> c_O(x0) 622.70/291.55 +(x0, x1) -> c_+(x0, x1) 622.70/291.55 622.70/291.55 Rewrite Strategy: FULL 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (5) RcToIrcProof (BOTH BOUNDS(ID, ID)) 622.70/291.55 Converted rc-obligation to irc-obligation. 622.70/291.55 622.70/291.55 The duplicating contexts are: 622.70/291.55 BS(N([], l, r)) 622.70/291.55 622.70/291.55 622.70/291.55 The defined contexts are: 622.70/291.55 and([], x1) 622.70/291.55 if([], x1, x2) 622.70/291.55 ge([], x1) 622.70/291.55 ge(x0, []) 622.70/291.55 if(x0, [], x2) 622.70/291.55 ge(I(0), []) 622.70/291.55 -([], x1) 622.70/291.55 -(x0, []) 622.70/291.55 if(x0, x1, []) 622.70/291.55 and(x0, []) 622.70/291.55 +([], I(1)) 622.70/291.55 +([], x1) 622.70/291.55 +(x0, []) 622.70/291.55 -([], I(1)) 622.70/291.55 O([]) 622.70/291.55 +([], I(0)) 622.70/291.55 -([], I(0)) 622.70/291.55 not([]) 622.70/291.55 ge(0, []) 622.70/291.55 622.70/291.55 622.70/291.55 [] just represents basic- or constructor-terms in the following defined contexts: 622.70/291.55 ge([], x1) 622.70/291.55 ge(x0, []) 622.70/291.55 622.70/291.55 622.70/291.55 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (6) 622.70/291.55 Obligation: 622.70/291.55 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). 622.70/291.55 622.70/291.55 622.70/291.55 The TRS R consists of the following rules: 622.70/291.55 622.70/291.55 O(0) -> 0 622.70/291.55 +(0, x) -> x 622.70/291.55 +(x, 0) -> x 622.70/291.55 +(I(x), I(y)) -> O(+(+(x, y), I(0))) 622.70/291.55 -(x, 0) -> x 622.70/291.55 -(0, x) -> 0 622.70/291.55 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(x, true) -> x 622.70/291.55 and(x, false) -> false 622.70/291.55 if(true, x, y) -> x 622.70/291.55 if(false, x, y) -> y 622.70/291.55 ge(I(x), I(y)) -> ge(x, y) 622.70/291.55 ge(x, 0) -> true 622.70/291.55 ge(0, I(x)) -> false 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(x)) -> +(Log'(x), I(0)) 622.70/291.55 Log(x) -> -(Log'(x), I(0)) 622.70/291.55 Val(L(x)) -> x 622.70/291.55 Val(N(x, l, r)) -> x 622.70/291.55 Min(L(x)) -> x 622.70/291.55 Min(N(x, l, r)) -> Min(l) 622.70/291.55 Max(L(x)) -> x 622.70/291.55 Max(N(x, l, r)) -> Max(r) 622.70/291.55 BS(L(x)) -> true 622.70/291.55 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.55 Size(L(x)) -> I(0) 622.70/291.55 Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(x)) -> true 622.70/291.55 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))) 622.70/291.55 ge(0, c_O(x)) -> ge(0, x) 622.70/291.55 ge(c_O(x), I(y)) -> not(ge(y, x)) 622.70/291.55 ge(c_O(x), c_O(y)) -> ge(x, y) 622.70/291.55 +(c_O(x), I(y)) -> I(+(x, y)) 622.70/291.55 +(I(x), c_O(y)) -> I(+(x, y)) 622.70/291.55 -(I(x), c_O(y)) -> I(-(x, y)) 622.70/291.55 +(c_O(x), c_O(y)) -> O(+(x, y)) 622.70/291.55 -(c_O(x), I(y)) -> I(-(-(x, y), I(1))) 622.70/291.55 -(c_O(x), c_O(y)) -> O(-(x, y)) 622.70/291.55 +(x, c_+(y, z)) -> +(+(x, y), z) 622.70/291.55 ge(I(x), c_O(y)) -> ge(x, y) 622.70/291.55 622.70/291.55 The (relative) TRS S consists of the following rules: 622.70/291.55 622.70/291.55 O(x0) -> c_O(x0) 622.70/291.55 +(x0, x1) -> c_+(x0, x1) 622.70/291.55 622.70/291.55 Rewrite Strategy: INNERMOST 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (7) CpxTrsToCdtProof (UPPER BOUND(ID)) 622.70/291.55 Converted Cpx (relative) TRS to CDT 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (8) 622.70/291.55 Obligation: 622.70/291.55 Complexity Dependency Tuples Problem 622.70/291.55 622.70/291.55 Rules: 622.70/291.55 O(z0) -> c_O(z0) 622.70/291.55 O(0) -> 0 622.70/291.55 +(z0, z1) -> c_+(z0, z1) 622.70/291.55 +(0, z0) -> z0 622.70/291.55 +(z0, 0) -> z0 622.70/291.55 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.55 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.55 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.55 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.55 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.55 -(z0, 0) -> z0 622.70/291.55 -(0, z0) -> 0 622.70/291.55 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.55 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.55 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.55 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(z0, true) -> z0 622.70/291.55 and(z0, false) -> false 622.70/291.55 if(true, z0, z1) -> z0 622.70/291.55 if(false, z0, z1) -> z1 622.70/291.55 ge(I(z0), I(z1)) -> ge(z0, z1) 622.70/291.55 ge(z0, 0) -> true 622.70/291.55 ge(0, I(z0)) -> false 622.70/291.55 ge(0, c_O(z0)) -> ge(0, z0) 622.70/291.55 ge(c_O(z0), I(z1)) -> not(ge(z1, z0)) 622.70/291.55 ge(c_O(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 ge(I(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.55 Log(z0) -> -(Log'(z0), I(0)) 622.70/291.55 Val(L(z0)) -> z0 622.70/291.55 Val(N(z0, l, r)) -> z0 622.70/291.55 Min(L(z0)) -> z0 622.70/291.55 Min(N(z0, l, r)) -> Min(l) 622.70/291.55 Max(L(z0)) -> z0 622.70/291.55 Max(N(z0, l, r)) -> Max(r) 622.70/291.55 BS(L(z0)) -> true 622.70/291.55 BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))) 622.70/291.55 Size(L(z0)) -> I(0) 622.70/291.55 Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(z0)) -> true 622.70/291.55 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))) 622.70/291.55 Tuples: 622.70/291.55 O'(z0) -> c 622.70/291.55 O'(0) -> c1 622.70/291.55 +'(z0, z1) -> c2 622.70/291.55 +'(0, z0) -> c3 622.70/291.55 +'(z0, 0) -> c4 622.70/291.55 +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(z0, 0) -> c10 622.70/291.55 -'(0, z0) -> c11 622.70/291.55 -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 NOT(true) -> c16 622.70/291.55 NOT(false) -> c17 622.70/291.55 AND(z0, true) -> c18 622.70/291.55 AND(z0, false) -> c19 622.70/291.55 IF(true, z0, z1) -> c20 622.70/291.55 IF(false, z0, z1) -> c21 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(z0, 0) -> c23 622.70/291.55 GE(0, I(z0)) -> c24 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(0) -> c29 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 VAL(L(z0)) -> c32 622.70/291.55 VAL(N(z0, l, r)) -> c33 622.70/291.55 MIN(L(z0)) -> c34 622.70/291.55 MIN(N(z0, l, r)) -> c35(MIN(l)) 622.70/291.55 MAX(L(z0)) -> c36 622.70/291.55 MAX(N(z0, l, r)) -> c37(MAX(r)) 622.70/291.55 BS'(L(z0)) -> c38 622.70/291.55 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)) 622.70/291.55 SIZE(L(z0)) -> c40 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r)) 622.70/291.55 WB'(L(z0)) -> c42 622.70/291.55 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)) 622.70/291.55 S tuples: 622.70/291.55 O'(0) -> c1 622.70/291.55 +'(0, z0) -> c3 622.70/291.55 +'(z0, 0) -> c4 622.70/291.55 +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(z0, 0) -> c10 622.70/291.55 -'(0, z0) -> c11 622.70/291.55 -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 NOT(true) -> c16 622.70/291.55 NOT(false) -> c17 622.70/291.55 AND(z0, true) -> c18 622.70/291.55 AND(z0, false) -> c19 622.70/291.55 IF(true, z0, z1) -> c20 622.70/291.55 IF(false, z0, z1) -> c21 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(z0, 0) -> c23 622.70/291.55 GE(0, I(z0)) -> c24 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(0) -> c29 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 VAL(L(z0)) -> c32 622.70/291.55 VAL(N(z0, l, r)) -> c33 622.70/291.55 MIN(L(z0)) -> c34 622.70/291.55 MIN(N(z0, l, r)) -> c35(MIN(l)) 622.70/291.55 MAX(L(z0)) -> c36 622.70/291.55 MAX(N(z0, l, r)) -> c37(MAX(r)) 622.70/291.55 BS'(L(z0)) -> c38 622.70/291.55 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)) 622.70/291.55 SIZE(L(z0)) -> c40 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r)) 622.70/291.55 WB'(L(z0)) -> c42 622.70/291.55 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)) 622.70/291.55 K tuples:none 622.70/291.55 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 622.70/291.55 622.70/291.55 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 622.70/291.55 622.70/291.55 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 622.70/291.55 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (9) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 622.70/291.55 Removed 27 trailing nodes: 622.70/291.55 AND(z0, true) -> c18 622.70/291.55 -'(0, z0) -> c11 622.70/291.55 MAX(L(z0)) -> c36 622.70/291.55 GE(z0, 0) -> c23 622.70/291.55 NOT(true) -> c16 622.70/291.55 MIN(L(z0)) -> c34 622.70/291.55 +'(0, z0) -> c3 622.70/291.55 VAL(L(z0)) -> c32 622.70/291.55 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)) 622.70/291.55 SIZE(L(z0)) -> c40 622.70/291.55 LOG'(0) -> c29 622.70/291.55 AND(z0, false) -> c19 622.70/291.55 MAX(N(z0, l, r)) -> c37(MAX(r)) 622.70/291.55 MIN(N(z0, l, r)) -> c35(MIN(l)) 622.70/291.55 O'(z0) -> c 622.70/291.55 -'(z0, 0) -> c10 622.70/291.55 NOT(false) -> c17 622.70/291.55 IF(false, z0, z1) -> c21 622.70/291.55 O'(0) -> c1 622.70/291.55 VAL(N(z0, l, r)) -> c33 622.70/291.55 GE(0, I(z0)) -> c24 622.70/291.55 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)) 622.70/291.55 BS'(L(z0)) -> c38 622.70/291.55 +'(z0, z1) -> c2 622.70/291.55 WB'(L(z0)) -> c42 622.70/291.55 +'(z0, 0) -> c4 622.70/291.55 IF(true, z0, z1) -> c20 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (10) 622.70/291.55 Obligation: 622.70/291.55 Complexity Dependency Tuples Problem 622.70/291.55 622.70/291.55 Rules: 622.70/291.55 O(z0) -> c_O(z0) 622.70/291.55 O(0) -> 0 622.70/291.55 +(z0, z1) -> c_+(z0, z1) 622.70/291.55 +(0, z0) -> z0 622.70/291.55 +(z0, 0) -> z0 622.70/291.55 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.55 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.55 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.55 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.55 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.55 -(z0, 0) -> z0 622.70/291.55 -(0, z0) -> 0 622.70/291.55 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.55 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.55 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.55 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(z0, true) -> z0 622.70/291.55 and(z0, false) -> false 622.70/291.55 if(true, z0, z1) -> z0 622.70/291.55 if(false, z0, z1) -> z1 622.70/291.55 ge(I(z0), I(z1)) -> ge(z0, z1) 622.70/291.55 ge(z0, 0) -> true 622.70/291.55 ge(0, I(z0)) -> false 622.70/291.55 ge(0, c_O(z0)) -> ge(0, z0) 622.70/291.55 ge(c_O(z0), I(z1)) -> not(ge(z1, z0)) 622.70/291.55 ge(c_O(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 ge(I(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.55 Log(z0) -> -(Log'(z0), I(0)) 622.70/291.55 Val(L(z0)) -> z0 622.70/291.55 Val(N(z0, l, r)) -> z0 622.70/291.55 Min(L(z0)) -> z0 622.70/291.55 Min(N(z0, l, r)) -> Min(l) 622.70/291.55 Max(L(z0)) -> z0 622.70/291.55 Max(N(z0, l, r)) -> Max(r) 622.70/291.55 BS(L(z0)) -> true 622.70/291.55 BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))) 622.70/291.55 Size(L(z0)) -> I(0) 622.70/291.55 Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(z0)) -> true 622.70/291.55 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))) 622.70/291.55 Tuples: 622.70/291.55 +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r)) 622.70/291.55 S tuples: 622.70/291.55 +'(I(z0), I(z1)) -> c5(O'(+(+(z0, z1), I(0))), +'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(O'(+(z0, z1)), +'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(O'(-(z0, z1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(NOT(ge(z1, z0)), GE(z1, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1)), +'(Size(l), Size(r)), SIZE(l), SIZE(r)) 622.70/291.55 K tuples:none 622.70/291.55 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 622.70/291.55 622.70/291.55 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, LOG_1, SIZE_1 622.70/291.55 622.70/291.55 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 622.70/291.55 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (11) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 622.70/291.55 Removed 8 trailing tuple parts 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (12) 622.70/291.55 Obligation: 622.70/291.55 Complexity Dependency Tuples Problem 622.70/291.55 622.70/291.55 Rules: 622.70/291.55 O(z0) -> c_O(z0) 622.70/291.55 O(0) -> 0 622.70/291.55 +(z0, z1) -> c_+(z0, z1) 622.70/291.55 +(0, z0) -> z0 622.70/291.55 +(z0, 0) -> z0 622.70/291.55 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.55 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.55 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.55 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.55 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.55 -(z0, 0) -> z0 622.70/291.55 -(0, z0) -> 0 622.70/291.55 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.55 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.55 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.55 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(z0, true) -> z0 622.70/291.55 and(z0, false) -> false 622.70/291.55 if(true, z0, z1) -> z0 622.70/291.55 if(false, z0, z1) -> z1 622.70/291.55 ge(I(z0), I(z1)) -> ge(z0, z1) 622.70/291.55 ge(z0, 0) -> true 622.70/291.55 ge(0, I(z0)) -> false 622.70/291.55 ge(0, c_O(z0)) -> ge(0, z0) 622.70/291.55 ge(c_O(z0), I(z1)) -> not(ge(z1, z0)) 622.70/291.55 ge(c_O(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 ge(I(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.55 Log(z0) -> -(Log'(z0), I(0)) 622.70/291.55 Val(L(z0)) -> z0 622.70/291.55 Val(N(z0, l, r)) -> z0 622.70/291.55 Min(L(z0)) -> z0 622.70/291.55 Min(N(z0, l, r)) -> Min(l) 622.70/291.55 Max(L(z0)) -> z0 622.70/291.55 Max(N(z0, l, r)) -> Max(r) 622.70/291.55 BS(L(z0)) -> true 622.70/291.55 BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))) 622.70/291.55 Size(L(z0)) -> I(0) 622.70/291.55 Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(z0)) -> true 622.70/291.55 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))) 622.70/291.55 Tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 S tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 LOG(z0) -> c31(-'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 K tuples:none 622.70/291.55 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 622.70/291.55 622.70/291.55 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, LOG_1, SIZE_1 622.70/291.55 622.70/291.55 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 622.70/291.55 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (13) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) 622.70/291.55 Split RHS of tuples not part of any SCC 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (14) 622.70/291.55 Obligation: 622.70/291.55 Complexity Dependency Tuples Problem 622.70/291.55 622.70/291.55 Rules: 622.70/291.55 O(z0) -> c_O(z0) 622.70/291.55 O(0) -> 0 622.70/291.55 +(z0, z1) -> c_+(z0, z1) 622.70/291.55 +(0, z0) -> z0 622.70/291.55 +(z0, 0) -> z0 622.70/291.55 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.55 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.55 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.55 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.55 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.55 -(z0, 0) -> z0 622.70/291.55 -(0, z0) -> 0 622.70/291.55 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.55 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.55 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.55 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(z0, true) -> z0 622.70/291.55 and(z0, false) -> false 622.70/291.55 if(true, z0, z1) -> z0 622.70/291.55 if(false, z0, z1) -> z1 622.70/291.55 ge(I(z0), I(z1)) -> ge(z0, z1) 622.70/291.55 ge(z0, 0) -> true 622.70/291.55 ge(0, I(z0)) -> false 622.70/291.55 ge(0, c_O(z0)) -> ge(0, z0) 622.70/291.55 ge(c_O(z0), I(z1)) -> not(ge(z1, z0)) 622.70/291.55 ge(c_O(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 ge(I(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.55 Log(z0) -> -(Log'(z0), I(0)) 622.70/291.55 Val(L(z0)) -> z0 622.70/291.55 Val(N(z0, l, r)) -> z0 622.70/291.55 Min(L(z0)) -> z0 622.70/291.55 Min(N(z0, l, r)) -> Min(l) 622.70/291.55 Max(L(z0)) -> z0 622.70/291.55 Max(N(z0, l, r)) -> Max(r) 622.70/291.55 BS(L(z0)) -> true 622.70/291.55 BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))) 622.70/291.55 Size(L(z0)) -> I(0) 622.70/291.55 Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(z0)) -> true 622.70/291.55 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))) 622.70/291.55 Tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.55 LOG(z0) -> c(LOG'(z0)) 622.70/291.55 S tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.55 LOG(z0) -> c(LOG'(z0)) 622.70/291.55 K tuples:none 622.70/291.55 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 622.70/291.55 622.70/291.55 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.55 622.70/291.55 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 622.70/291.55 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (15) CdtLeafRemovalProof (ComplexityIfPolyImplication) 622.70/291.55 Removed 1 leading nodes: 622.70/291.55 LOG(z0) -> c(LOG'(z0)) 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (16) 622.70/291.55 Obligation: 622.70/291.55 Complexity Dependency Tuples Problem 622.70/291.55 622.70/291.55 Rules: 622.70/291.55 O(z0) -> c_O(z0) 622.70/291.55 O(0) -> 0 622.70/291.55 +(z0, z1) -> c_+(z0, z1) 622.70/291.55 +(0, z0) -> z0 622.70/291.55 +(z0, 0) -> z0 622.70/291.55 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.55 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.55 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.55 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.55 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.55 -(z0, 0) -> z0 622.70/291.55 -(0, z0) -> 0 622.70/291.55 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.55 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.55 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.55 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(z0, true) -> z0 622.70/291.55 and(z0, false) -> false 622.70/291.55 if(true, z0, z1) -> z0 622.70/291.55 if(false, z0, z1) -> z1 622.70/291.55 ge(I(z0), I(z1)) -> ge(z0, z1) 622.70/291.55 ge(z0, 0) -> true 622.70/291.55 ge(0, I(z0)) -> false 622.70/291.55 ge(0, c_O(z0)) -> ge(0, z0) 622.70/291.55 ge(c_O(z0), I(z1)) -> not(ge(z1, z0)) 622.70/291.55 ge(c_O(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 ge(I(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.55 Log(z0) -> -(Log'(z0), I(0)) 622.70/291.55 Val(L(z0)) -> z0 622.70/291.55 Val(N(z0, l, r)) -> z0 622.70/291.55 Min(L(z0)) -> z0 622.70/291.55 Min(N(z0, l, r)) -> Min(l) 622.70/291.55 Max(L(z0)) -> z0 622.70/291.55 Max(N(z0, l, r)) -> Max(r) 622.70/291.55 BS(L(z0)) -> true 622.70/291.55 BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))) 622.70/291.55 Size(L(z0)) -> I(0) 622.70/291.55 Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(z0)) -> true 622.70/291.55 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))) 622.70/291.55 Tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.55 S tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.55 K tuples:none 622.70/291.55 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 622.70/291.55 622.70/291.55 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.55 622.70/291.55 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 622.70/291.55 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (17) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 622.70/291.55 The following tuples could be moved from S to K by knowledge propagation: 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.55 622.70/291.55 ---------------------------------------- 622.70/291.55 622.70/291.55 (18) 622.70/291.55 Obligation: 622.70/291.55 Complexity Dependency Tuples Problem 622.70/291.55 622.70/291.55 Rules: 622.70/291.55 O(z0) -> c_O(z0) 622.70/291.55 O(0) -> 0 622.70/291.55 +(z0, z1) -> c_+(z0, z1) 622.70/291.55 +(0, z0) -> z0 622.70/291.55 +(z0, 0) -> z0 622.70/291.55 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.55 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.55 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.55 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.55 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.55 -(z0, 0) -> z0 622.70/291.55 -(0, z0) -> 0 622.70/291.55 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.55 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.55 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.55 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.55 not(true) -> false 622.70/291.55 not(false) -> true 622.70/291.55 and(z0, true) -> z0 622.70/291.55 and(z0, false) -> false 622.70/291.55 if(true, z0, z1) -> z0 622.70/291.55 if(false, z0, z1) -> z1 622.70/291.55 ge(I(z0), I(z1)) -> ge(z0, z1) 622.70/291.55 ge(z0, 0) -> true 622.70/291.55 ge(0, I(z0)) -> false 622.70/291.55 ge(0, c_O(z0)) -> ge(0, z0) 622.70/291.55 ge(c_O(z0), I(z1)) -> not(ge(z1, z0)) 622.70/291.55 ge(c_O(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 ge(I(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.55 Log'(0) -> 0 622.70/291.55 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.55 Log(z0) -> -(Log'(z0), I(0)) 622.70/291.55 Val(L(z0)) -> z0 622.70/291.55 Val(N(z0, l, r)) -> z0 622.70/291.55 Min(L(z0)) -> z0 622.70/291.55 Min(N(z0, l, r)) -> Min(l) 622.70/291.55 Max(L(z0)) -> z0 622.70/291.55 Max(N(z0, l, r)) -> Max(r) 622.70/291.55 BS(L(z0)) -> true 622.70/291.55 BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))) 622.70/291.55 Size(L(z0)) -> I(0) 622.70/291.55 Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.55 WB(L(z0)) -> true 622.70/291.55 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))) 622.70/291.55 Tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.55 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.55 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.55 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.55 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.55 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.55 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.55 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.55 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.55 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.55 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.55 S tuples: 622.70/291.55 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.55 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.55 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.55 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.55 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.55 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 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 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (19) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 622.70/291.56 The following rules are not usable and were removed: 622.70/291.56 not(true) -> false 622.70/291.56 not(false) -> true 622.70/291.56 and(z0, true) -> z0 622.70/291.56 and(z0, false) -> false 622.70/291.56 if(true, z0, z1) -> z0 622.70/291.56 if(false, z0, z1) -> z1 622.70/291.56 ge(I(z0), I(z1)) -> ge(z0, z1) 622.70/291.56 ge(z0, 0) -> true 622.70/291.56 ge(0, I(z0)) -> false 622.70/291.56 ge(0, c_O(z0)) -> ge(0, z0) 622.70/291.56 ge(c_O(z0), I(z1)) -> not(ge(z1, z0)) 622.70/291.56 ge(c_O(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.56 ge(I(z0), c_O(z1)) -> ge(z0, z1) 622.70/291.56 Log(z0) -> -(Log'(z0), I(0)) 622.70/291.56 Val(L(z0)) -> z0 622.70/291.56 Val(N(z0, l, r)) -> z0 622.70/291.56 Min(L(z0)) -> z0 622.70/291.56 Min(N(z0, l, r)) -> Min(l) 622.70/291.56 Max(L(z0)) -> z0 622.70/291.56 Max(N(z0, l, r)) -> Max(r) 622.70/291.56 BS(L(z0)) -> true 622.70/291.56 BS(N(z0, l, r)) -> and(and(ge(z0, Max(l)), ge(Min(r), z0)), and(BS(l), BS(r))) 622.70/291.56 Size(L(z0)) -> I(0) 622.70/291.56 Size(N(z0, l, r)) -> +(+(Size(l), Size(r)), I(1)) 622.70/291.56 WB(L(z0)) -> true 622.70/291.56 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))) 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (20) 622.70/291.56 Obligation: 622.70/291.56 Complexity Dependency Tuples Problem 622.70/291.56 622.70/291.56 Rules: 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 O(0) -> 0 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 S tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 Defined Rule Symbols: +_2, O_1, -_2, Log'_1 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 622.70/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 We considered the (Usable) Rules:none 622.70/291.56 And the Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 The order we found is given by the following interpretation: 622.70/291.56 622.70/291.56 Polynomial interpretation : 622.70/291.56 622.70/291.56 POL(+(x_1, x_2)) = 0 622.70/291.56 POL(+'(x_1, x_2)) = x_2 622.70/291.56 POL(-(x_1, x_2)) = 0 622.70/291.56 POL(-'(x_1, x_2)) = 0 622.70/291.56 POL(0) = 0 622.70/291.56 POL(1) = 0 622.70/291.56 POL(GE(x_1, x_2)) = 0 622.70/291.56 POL(I(x_1)) = [1] + x_1 622.70/291.56 POL(LOG(x_1)) = 0 622.70/291.56 POL(LOG'(x_1)) = x_1 622.70/291.56 POL(Log'(x_1)) = x_1 622.70/291.56 POL(N(x_1, x_2, x_3)) = [1] + x_2 622.70/291.56 POL(O(x_1)) = 0 622.70/291.56 POL(SIZE(x_1)) = x_1 622.70/291.56 POL(Size(x_1)) = [1] + x_1 622.70/291.56 POL(c(x_1)) = x_1 622.70/291.56 POL(c12(x_1)) = x_1 622.70/291.56 POL(c13(x_1)) = x_1 622.70/291.56 POL(c14(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c15(x_1)) = x_1 622.70/291.56 POL(c22(x_1)) = x_1 622.70/291.56 POL(c25(x_1)) = x_1 622.70/291.56 POL(c26(x_1)) = x_1 622.70/291.56 POL(c27(x_1)) = x_1 622.70/291.56 POL(c28(x_1)) = x_1 622.70/291.56 POL(c30(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c41(x_1)) = x_1 622.70/291.56 POL(c5(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c6(x_1)) = x_1 622.70/291.56 POL(c7(x_1)) = x_1 622.70/291.56 POL(c8(x_1)) = x_1 622.70/291.56 POL(c9(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_+(x_1, x_2)) = [1] + x_1 + x_2 622.70/291.56 POL(c_O(x_1)) = [1] + x_1 622.70/291.56 POL(l) = 0 622.70/291.56 POL(r) = [1] 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (22) 622.70/291.56 Obligation: 622.70/291.56 Complexity Dependency Tuples Problem 622.70/291.56 622.70/291.56 Rules: 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 O(0) -> 0 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 S tuples: 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 Defined Rule Symbols: +_2, O_1, -_2, Log'_1 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (23) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 622.70/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 We considered the (Usable) Rules:none 622.70/291.56 And the Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 The order we found is given by the following interpretation: 622.70/291.56 622.70/291.56 Polynomial interpretation : 622.70/291.56 622.70/291.56 POL(+(x_1, x_2)) = 0 622.70/291.56 POL(+'(x_1, x_2)) = 0 622.70/291.56 POL(-(x_1, x_2)) = 0 622.70/291.56 POL(-'(x_1, x_2)) = 0 622.70/291.56 POL(0) = [1] 622.70/291.56 POL(1) = [1] 622.70/291.56 POL(GE(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(I(x_1)) = x_1 622.70/291.56 POL(LOG(x_1)) = 0 622.70/291.56 POL(LOG'(x_1)) = x_1 622.70/291.56 POL(Log'(x_1)) = x_1 622.70/291.56 POL(N(x_1, x_2, x_3)) = [1] + x_2 + x_3 622.70/291.56 POL(O(x_1)) = 0 622.70/291.56 POL(SIZE(x_1)) = [1] + x_1 622.70/291.56 POL(Size(x_1)) = [1] + x_1 622.70/291.56 POL(c(x_1)) = x_1 622.70/291.56 POL(c12(x_1)) = x_1 622.70/291.56 POL(c13(x_1)) = x_1 622.70/291.56 POL(c14(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c15(x_1)) = x_1 622.70/291.56 POL(c22(x_1)) = x_1 622.70/291.56 POL(c25(x_1)) = x_1 622.70/291.56 POL(c26(x_1)) = x_1 622.70/291.56 POL(c27(x_1)) = x_1 622.70/291.56 POL(c28(x_1)) = x_1 622.70/291.56 POL(c30(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c41(x_1)) = x_1 622.70/291.56 POL(c5(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c6(x_1)) = x_1 622.70/291.56 POL(c7(x_1)) = x_1 622.70/291.56 POL(c8(x_1)) = x_1 622.70/291.56 POL(c9(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_+(x_1, x_2)) = 0 622.70/291.56 POL(c_O(x_1)) = [1] + x_1 622.70/291.56 POL(l) = [1] 622.70/291.56 POL(r) = [1] 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (24) 622.70/291.56 Obligation: 622.70/291.56 Complexity Dependency Tuples Problem 622.70/291.56 622.70/291.56 Rules: 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 O(0) -> 0 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 S tuples: 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 Defined Rule Symbols: +_2, O_1, -_2, Log'_1 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (25) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 622.70/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 We considered the (Usable) Rules:none 622.70/291.56 And the Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 The order we found is given by the following interpretation: 622.70/291.56 622.70/291.56 Polynomial interpretation : 622.70/291.56 622.70/291.56 POL(+(x_1, x_2)) = 0 622.70/291.56 POL(+'(x_1, x_2)) = 0 622.70/291.56 POL(-(x_1, x_2)) = [1] 622.70/291.56 POL(-'(x_1, x_2)) = x_2 622.70/291.56 POL(0) = 0 622.70/291.56 POL(1) = 0 622.70/291.56 POL(GE(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(I(x_1)) = x_1 622.70/291.56 POL(LOG(x_1)) = 0 622.70/291.56 POL(LOG'(x_1)) = x_1 622.70/291.56 POL(Log'(x_1)) = [1] + x_1 622.70/291.56 POL(N(x_1, x_2, x_3)) = [1] + x_2 + x_3 622.70/291.56 POL(O(x_1)) = 0 622.70/291.56 POL(SIZE(x_1)) = [1] + x_1 622.70/291.56 POL(Size(x_1)) = [1] + x_1 622.70/291.56 POL(c(x_1)) = x_1 622.70/291.56 POL(c12(x_1)) = x_1 622.70/291.56 POL(c13(x_1)) = x_1 622.70/291.56 POL(c14(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c15(x_1)) = x_1 622.70/291.56 POL(c22(x_1)) = x_1 622.70/291.56 POL(c25(x_1)) = x_1 622.70/291.56 POL(c26(x_1)) = x_1 622.70/291.56 POL(c27(x_1)) = x_1 622.70/291.56 POL(c28(x_1)) = x_1 622.70/291.56 POL(c30(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c41(x_1)) = x_1 622.70/291.56 POL(c5(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c6(x_1)) = x_1 622.70/291.56 POL(c7(x_1)) = x_1 622.70/291.56 POL(c8(x_1)) = x_1 622.70/291.56 POL(c9(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_+(x_1, x_2)) = 0 622.70/291.56 POL(c_O(x_1)) = [1] + x_1 622.70/291.56 POL(l) = [1] 622.70/291.56 POL(r) = [1] 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (26) 622.70/291.56 Obligation: 622.70/291.56 Complexity Dependency Tuples Problem 622.70/291.56 622.70/291.56 Rules: 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 O(0) -> 0 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 S tuples: 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 Defined Rule Symbols: +_2, O_1, -_2, Log'_1 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (27) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 622.70/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 We considered the (Usable) Rules:none 622.70/291.56 And the Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 The order we found is given by the following interpretation: 622.70/291.56 622.70/291.56 Polynomial interpretation : 622.70/291.56 622.70/291.56 POL(+(x_1, x_2)) = 0 622.70/291.56 POL(+'(x_1, x_2)) = 0 622.70/291.56 POL(-(x_1, x_2)) = 0 622.70/291.56 POL(-'(x_1, x_2)) = x_2 622.70/291.56 POL(0) = 0 622.70/291.56 POL(1) = 0 622.70/291.56 POL(GE(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(I(x_1)) = [1] + x_1 622.70/291.56 POL(LOG(x_1)) = [1] 622.70/291.56 POL(LOG'(x_1)) = x_1 622.70/291.56 POL(Log'(x_1)) = [1] + x_1 622.70/291.56 POL(N(x_1, x_2, x_3)) = x_2 + x_3 622.70/291.56 POL(O(x_1)) = 0 622.70/291.56 POL(SIZE(x_1)) = [1] + x_1 622.70/291.56 POL(Size(x_1)) = [1] + x_1 622.70/291.56 POL(c(x_1)) = x_1 622.70/291.56 POL(c12(x_1)) = x_1 622.70/291.56 POL(c13(x_1)) = x_1 622.70/291.56 POL(c14(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c15(x_1)) = x_1 622.70/291.56 POL(c22(x_1)) = x_1 622.70/291.56 POL(c25(x_1)) = x_1 622.70/291.56 POL(c26(x_1)) = x_1 622.70/291.56 POL(c27(x_1)) = x_1 622.70/291.56 POL(c28(x_1)) = x_1 622.70/291.56 POL(c30(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c41(x_1)) = x_1 622.70/291.56 POL(c5(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c6(x_1)) = x_1 622.70/291.56 POL(c7(x_1)) = x_1 622.70/291.56 POL(c8(x_1)) = x_1 622.70/291.56 POL(c9(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_+(x_1, x_2)) = 0 622.70/291.56 POL(c_O(x_1)) = [1] + x_1 622.70/291.56 POL(l) = 0 622.70/291.56 POL(r) = [1] 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (28) 622.70/291.56 Obligation: 622.70/291.56 Complexity Dependency Tuples Problem 622.70/291.56 622.70/291.56 Rules: 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 O(0) -> 0 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 S tuples: 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 Defined Rule Symbols: +_2, O_1, -_2, Log'_1 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (29) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 622.70/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 We considered the (Usable) Rules: 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 O(0) -> 0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 Log'(0) -> 0 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 And the Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 The order we found is given by the following interpretation: 622.70/291.56 622.70/291.56 Polynomial interpretation : 622.70/291.56 622.70/291.56 POL(+(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(+'(x_1, x_2)) = x_2^2 + [2]x_1*x_2 622.70/291.56 POL(-(x_1, x_2)) = 0 622.70/291.56 POL(-'(x_1, x_2)) = 0 622.70/291.56 POL(0) = 0 622.70/291.56 POL(1) = 0 622.70/291.56 POL(GE(x_1, x_2)) = 0 622.70/291.56 POL(I(x_1)) = [1] + x_1 622.70/291.56 POL(LOG(x_1)) = [2] + x_1 + x_1^2 622.70/291.56 POL(LOG'(x_1)) = [2]x_1 + [2]x_1^2 622.70/291.56 POL(Log'(x_1)) = x_1 622.70/291.56 POL(N(x_1, x_2, x_3)) = 0 622.70/291.56 POL(O(x_1)) = x_1 622.70/291.56 POL(SIZE(x_1)) = [1] 622.70/291.56 POL(Size(x_1)) = 0 622.70/291.56 POL(c(x_1)) = x_1 622.70/291.56 POL(c12(x_1)) = x_1 622.70/291.56 POL(c13(x_1)) = x_1 622.70/291.56 POL(c14(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c15(x_1)) = x_1 622.70/291.56 POL(c22(x_1)) = x_1 622.70/291.56 POL(c25(x_1)) = x_1 622.70/291.56 POL(c26(x_1)) = x_1 622.70/291.56 POL(c27(x_1)) = x_1 622.70/291.56 POL(c28(x_1)) = x_1 622.70/291.56 POL(c30(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c41(x_1)) = x_1 622.70/291.56 POL(c5(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c6(x_1)) = x_1 622.70/291.56 POL(c7(x_1)) = x_1 622.70/291.56 POL(c8(x_1)) = x_1 622.70/291.56 POL(c9(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_+(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_O(x_1)) = x_1 622.70/291.56 POL(l) = 0 622.70/291.56 POL(r) = 0 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (30) 622.70/291.56 Obligation: 622.70/291.56 Complexity Dependency Tuples Problem 622.70/291.56 622.70/291.56 Rules: 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 O(0) -> 0 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 S tuples: 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 Defined Rule Symbols: +_2, O_1, -_2, Log'_1 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (31) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 622.70/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 We considered the (Usable) Rules: 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 O(0) -> 0 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 And the Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 The order we found is given by the following interpretation: 622.70/291.56 622.70/291.56 Polynomial interpretation : 622.70/291.56 622.70/291.56 POL(+(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(+'(x_1, x_2)) = 0 622.70/291.56 POL(-(x_1, x_2)) = x_1 622.70/291.56 POL(-'(x_1, x_2)) = x_2^2 + x_1*x_2 622.70/291.56 POL(0) = 0 622.70/291.56 POL(1) = 0 622.70/291.56 POL(GE(x_1, x_2)) = 0 622.70/291.56 POL(I(x_1)) = [1] + x_1 622.70/291.56 POL(LOG(x_1)) = [2] + x_1 + [2]x_1^2 622.70/291.56 POL(LOG'(x_1)) = x_1 622.70/291.56 POL(Log'(x_1)) = [1] + [2]x_1^2 622.70/291.56 POL(N(x_1, x_2, x_3)) = [2] + x_2 622.70/291.56 POL(O(x_1)) = [1] + x_1 622.70/291.56 POL(SIZE(x_1)) = [2] + [2]x_1 + x_1^2 622.70/291.56 POL(Size(x_1)) = 0 622.70/291.56 POL(c(x_1)) = x_1 622.70/291.56 POL(c12(x_1)) = x_1 622.70/291.56 POL(c13(x_1)) = x_1 622.70/291.56 POL(c14(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c15(x_1)) = x_1 622.70/291.56 POL(c22(x_1)) = x_1 622.70/291.56 POL(c25(x_1)) = x_1 622.70/291.56 POL(c26(x_1)) = x_1 622.70/291.56 POL(c27(x_1)) = x_1 622.70/291.56 POL(c28(x_1)) = x_1 622.70/291.56 POL(c30(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c41(x_1)) = x_1 622.70/291.56 POL(c5(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c6(x_1)) = x_1 622.70/291.56 POL(c7(x_1)) = x_1 622.70/291.56 POL(c8(x_1)) = x_1 622.70/291.56 POL(c9(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_+(x_1, x_2)) = x_1 + x_2 622.70/291.56 POL(c_O(x_1)) = [1] + x_1 622.70/291.56 POL(l) = [2] 622.70/291.56 POL(r) = 0 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (32) 622.70/291.56 Obligation: 622.70/291.56 Complexity Dependency Tuples Problem 622.70/291.56 622.70/291.56 Rules: 622.70/291.56 +(z0, z1) -> c_+(z0, z1) 622.70/291.56 +(0, z0) -> z0 622.70/291.56 +(z0, 0) -> z0 622.70/291.56 +(I(z0), I(z1)) -> O(+(+(z0, z1), I(0))) 622.70/291.56 +(c_O(z0), I(z1)) -> I(+(z0, z1)) 622.70/291.56 +(I(z0), c_O(z1)) -> I(+(z0, z1)) 622.70/291.56 +(c_O(z0), c_O(z1)) -> O(+(z0, z1)) 622.70/291.56 +(z0, c_+(z1, z2)) -> +(+(z0, z1), z2) 622.70/291.56 O(z0) -> c_O(z0) 622.70/291.56 O(0) -> 0 622.70/291.56 -(z0, 0) -> z0 622.70/291.56 -(0, z0) -> 0 622.70/291.56 -(I(z0), I(z1)) -> O(-(z0, z1)) 622.70/291.56 -(I(z0), c_O(z1)) -> I(-(z0, z1)) 622.70/291.56 -(c_O(z0), I(z1)) -> I(-(-(z0, z1), I(1))) 622.70/291.56 -(c_O(z0), c_O(z1)) -> O(-(z0, z1)) 622.70/291.56 Log'(0) -> 0 622.70/291.56 Log'(I(z0)) -> +(Log'(z0), I(0)) 622.70/291.56 Tuples: 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 S tuples:none 622.70/291.56 K tuples: 622.70/291.56 SIZE(N(z0, l, r)) -> c41(+'(+(Size(l), Size(r)), I(1))) 622.70/291.56 LOG(z0) -> c(-'(Log'(z0), I(0))) 622.70/291.56 +'(c_O(z0), I(z1)) -> c6(+'(z0, z1)) 622.70/291.56 +'(I(z0), c_O(z1)) -> c7(+'(z0, z1)) 622.70/291.56 +'(z0, c_+(z1, z2)) -> c9(+'(+(z0, z1), z2), +'(z0, z1)) 622.70/291.56 +'(c_O(z0), c_O(z1)) -> c8(+'(z0, z1)) 622.70/291.56 GE(0, c_O(z0)) -> c25(GE(0, z0)) 622.70/291.56 GE(c_O(z0), c_O(z1)) -> c27(GE(z0, z1)) 622.70/291.56 GE(I(z0), c_O(z1)) -> c28(GE(z0, z1)) 622.70/291.56 GE(c_O(z0), I(z1)) -> c26(GE(z1, z0)) 622.70/291.56 -'(I(z0), c_O(z1)) -> c13(-'(z0, z1)) 622.70/291.56 -'(c_O(z0), c_O(z1)) -> c15(-'(z0, z1)) 622.70/291.56 GE(I(z0), I(z1)) -> c22(GE(z0, z1)) 622.70/291.56 LOG'(I(z0)) -> c30(+'(Log'(z0), I(0)), LOG'(z0)) 622.70/291.56 -'(I(z0), I(z1)) -> c12(-'(z0, z1)) 622.70/291.56 +'(I(z0), I(z1)) -> c5(+'(+(z0, z1), I(0)), +'(z0, z1)) 622.70/291.56 -'(c_O(z0), I(z1)) -> c14(-'(-(z0, z1), I(1)), -'(z0, z1)) 622.70/291.56 Defined Rule Symbols: +_2, O_1, -_2, Log'_1 622.70/291.56 622.70/291.56 Defined Pair Symbols: +'_2, -'_2, GE_2, LOG'_1, SIZE_1, LOG_1 622.70/291.56 622.70/291.56 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 622.70/291.56 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (33) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 622.70/291.56 The set S is empty 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (34) 622.70/291.56 BOUNDS(1, 1) 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (35) RenamingProof (BOTH BOUNDS(ID, ID)) 622.70/291.56 Renamed function symbols to avoid clashes with predefined symbol. 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (36) 622.70/291.56 Obligation: 622.70/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 622.70/291.56 622.70/291.56 622.70/291.56 The TRS R consists of the following rules: 622.70/291.56 622.70/291.56 O(0') -> 0' 622.70/291.56 +'(0', x) -> x 622.70/291.56 +'(x, 0') -> x 622.70/291.56 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.56 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.56 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.56 -(x, 0') -> x 622.70/291.56 -(0', x) -> 0' 622.70/291.56 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.56 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.56 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.56 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.56 not(true) -> false 622.70/291.56 not(false) -> true 622.70/291.56 and(x, true) -> x 622.70/291.56 and(x, false) -> false 622.70/291.56 if(true, x, y) -> x 622.70/291.56 if(false, x, y) -> y 622.70/291.56 ge(O(x), O(y)) -> ge(x, y) 622.70/291.56 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.56 ge(I(x), O(y)) -> ge(x, y) 622.70/291.56 ge(I(x), I(y)) -> ge(x, y) 622.70/291.56 ge(x, 0') -> true 622.70/291.56 ge(0', O(x)) -> ge(0', x) 622.70/291.56 ge(0', I(x)) -> false 622.70/291.56 Log'(0') -> 0' 622.70/291.56 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.56 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.56 Log(x) -> -(Log'(x), I(0')) 622.70/291.56 Val(L(x)) -> x 622.70/291.56 Val(N(x, l, r)) -> x 622.70/291.56 Min(L(x)) -> x 622.70/291.56 Min(N(x, l, r)) -> Min(l) 622.70/291.56 Max(L(x)) -> x 622.70/291.56 Max(N(x, l, r)) -> Max(r) 622.70/291.56 BS(L(x)) -> true 622.70/291.56 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.56 Size(L(x)) -> I(0') 622.70/291.56 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.56 WB(L(x)) -> true 622.70/291.56 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))) 622.70/291.56 622.70/291.56 S is empty. 622.70/291.56 Rewrite Strategy: FULL 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (37) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 622.70/291.56 Infered types. 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (38) 622.70/291.56 Obligation: 622.70/291.56 TRS: 622.70/291.56 Rules: 622.70/291.56 O(0') -> 0' 622.70/291.56 +'(0', x) -> x 622.70/291.56 +'(x, 0') -> x 622.70/291.56 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.56 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.56 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.56 -(x, 0') -> x 622.70/291.56 -(0', x) -> 0' 622.70/291.56 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.56 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.56 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.56 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.56 not(true) -> false 622.70/291.56 not(false) -> true 622.70/291.56 and(x, true) -> x 622.70/291.56 and(x, false) -> false 622.70/291.56 if(true, x, y) -> x 622.70/291.56 if(false, x, y) -> y 622.70/291.56 ge(O(x), O(y)) -> ge(x, y) 622.70/291.56 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.56 ge(I(x), O(y)) -> ge(x, y) 622.70/291.56 ge(I(x), I(y)) -> ge(x, y) 622.70/291.56 ge(x, 0') -> true 622.70/291.56 ge(0', O(x)) -> ge(0', x) 622.70/291.56 ge(0', I(x)) -> false 622.70/291.56 Log'(0') -> 0' 622.70/291.56 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.56 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.56 Log(x) -> -(Log'(x), I(0')) 622.70/291.56 Val(L(x)) -> x 622.70/291.56 Val(N(x, l, r)) -> x 622.70/291.56 Min(L(x)) -> x 622.70/291.56 Min(N(x, l, r)) -> Min(l) 622.70/291.56 Max(L(x)) -> x 622.70/291.56 Max(N(x, l, r)) -> Max(r) 622.70/291.56 BS(L(x)) -> true 622.70/291.56 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.56 Size(L(x)) -> I(0') 622.70/291.56 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.56 WB(L(x)) -> true 622.70/291.56 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))) 622.70/291.56 622.70/291.56 Types: 622.70/291.56 O :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 0' :: 0':I:1':true:false 622.70/291.56 +' :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 I :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 - :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 1' :: 0':I:1':true:false 622.70/291.56 not :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 true :: 0':I:1':true:false 622.70/291.56 false :: 0':I:1':true:false 622.70/291.56 and :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 if :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 ge :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 Log' :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 Log :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 Val :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 L :: 0':I:1':true:false -> L:l:r:N 622.70/291.56 N :: 0':I:1':true:false -> L:l:r:N -> L:l:r:N -> L:l:r:N 622.70/291.56 l :: L:l:r:N 622.70/291.56 r :: L:l:r:N 622.70/291.56 Min :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 Max :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 BS :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 Size :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 WB :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 hole_0':I:1':true:false1_0 :: 0':I:1':true:false 622.70/291.56 hole_L:l:r:N2_0 :: L:l:r:N 622.70/291.56 gen_0':I:1':true:false3_0 :: Nat -> 0':I:1':true:false 622.70/291.56 gen_L:l:r:N4_0 :: Nat -> L:l:r:N 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (39) OrderProof (LOWER BOUND(ID)) 622.70/291.56 Heuristically decided to analyse the following defined symbols: 622.70/291.56 +', -, ge, Log', Min, Max, BS, Size, WB 622.70/291.56 622.70/291.56 They will be analysed ascendingly in the following order: 622.70/291.56 +' < Log' 622.70/291.56 +' < Size 622.70/291.56 - < WB 622.70/291.56 ge < Log' 622.70/291.56 ge < BS 622.70/291.56 ge < WB 622.70/291.56 Min < BS 622.70/291.56 Max < BS 622.70/291.56 Size < WB 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (40) 622.70/291.56 Obligation: 622.70/291.56 TRS: 622.70/291.56 Rules: 622.70/291.56 O(0') -> 0' 622.70/291.56 +'(0', x) -> x 622.70/291.56 +'(x, 0') -> x 622.70/291.56 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.56 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.56 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.56 -(x, 0') -> x 622.70/291.56 -(0', x) -> 0' 622.70/291.56 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.56 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.56 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.56 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.56 not(true) -> false 622.70/291.56 not(false) -> true 622.70/291.56 and(x, true) -> x 622.70/291.56 and(x, false) -> false 622.70/291.56 if(true, x, y) -> x 622.70/291.56 if(false, x, y) -> y 622.70/291.56 ge(O(x), O(y)) -> ge(x, y) 622.70/291.56 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.56 ge(I(x), O(y)) -> ge(x, y) 622.70/291.56 ge(I(x), I(y)) -> ge(x, y) 622.70/291.56 ge(x, 0') -> true 622.70/291.56 ge(0', O(x)) -> ge(0', x) 622.70/291.56 ge(0', I(x)) -> false 622.70/291.56 Log'(0') -> 0' 622.70/291.56 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.56 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.56 Log(x) -> -(Log'(x), I(0')) 622.70/291.56 Val(L(x)) -> x 622.70/291.56 Val(N(x, l, r)) -> x 622.70/291.56 Min(L(x)) -> x 622.70/291.56 Min(N(x, l, r)) -> Min(l) 622.70/291.56 Max(L(x)) -> x 622.70/291.56 Max(N(x, l, r)) -> Max(r) 622.70/291.56 BS(L(x)) -> true 622.70/291.56 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.56 Size(L(x)) -> I(0') 622.70/291.56 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.56 WB(L(x)) -> true 622.70/291.56 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))) 622.70/291.56 622.70/291.56 Types: 622.70/291.56 O :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 0' :: 0':I:1':true:false 622.70/291.56 +' :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 I :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 - :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 1' :: 0':I:1':true:false 622.70/291.56 not :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 true :: 0':I:1':true:false 622.70/291.56 false :: 0':I:1':true:false 622.70/291.56 and :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 if :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 ge :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 Log' :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 Log :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 Val :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 L :: 0':I:1':true:false -> L:l:r:N 622.70/291.56 N :: 0':I:1':true:false -> L:l:r:N -> L:l:r:N -> L:l:r:N 622.70/291.56 l :: L:l:r:N 622.70/291.56 r :: L:l:r:N 622.70/291.56 Min :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 Max :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 BS :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 Size :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 WB :: L:l:r:N -> 0':I:1':true:false 622.70/291.56 hole_0':I:1':true:false1_0 :: 0':I:1':true:false 622.70/291.56 hole_L:l:r:N2_0 :: L:l:r:N 622.70/291.56 gen_0':I:1':true:false3_0 :: Nat -> 0':I:1':true:false 622.70/291.56 gen_L:l:r:N4_0 :: Nat -> L:l:r:N 622.70/291.56 622.70/291.56 622.70/291.56 Generator Equations: 622.70/291.56 gen_0':I:1':true:false3_0(0) <=> 0' 622.70/291.56 gen_0':I:1':true:false3_0(+(x, 1)) <=> I(gen_0':I:1':true:false3_0(x)) 622.70/291.56 gen_L:l:r:N4_0(0) <=> L(0') 622.70/291.56 gen_L:l:r:N4_0(+(x, 1)) <=> N(0', L(0'), gen_L:l:r:N4_0(x)) 622.70/291.56 622.70/291.56 622.70/291.56 The following defined symbols remain to be analysed: 622.70/291.56 +', -, ge, Log', Min, Max, BS, Size, WB 622.70/291.56 622.70/291.56 They will be analysed ascendingly in the following order: 622.70/291.56 +' < Log' 622.70/291.56 +' < Size 622.70/291.56 - < WB 622.70/291.56 ge < Log' 622.70/291.56 ge < BS 622.70/291.56 ge < WB 622.70/291.56 Min < BS 622.70/291.56 Max < BS 622.70/291.56 Size < WB 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (41) RewriteLemmaProof (LOWER BOUND(ID)) 622.70/291.56 Proved the following rewrite lemma: 622.70/291.56 +'(gen_0':I:1':true:false3_0(+(1, n6_0)), gen_0':I:1':true:false3_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0) 622.70/291.56 622.70/291.56 Induction Base: 622.70/291.56 +'(gen_0':I:1':true:false3_0(+(1, 0)), gen_0':I:1':true:false3_0(+(1, 0))) 622.70/291.56 622.70/291.56 Induction Step: 622.70/291.56 +'(gen_0':I:1':true:false3_0(+(1, +(n6_0, 1))), gen_0':I:1':true:false3_0(+(1, +(n6_0, 1)))) ->_R^Omega(1) 622.70/291.56 O(+'(+'(gen_0':I:1':true:false3_0(+(1, n6_0)), gen_0':I:1':true:false3_0(+(1, n6_0))), I(0'))) ->_IH 622.70/291.56 O(+'(*5_0, I(0'))) 622.70/291.56 622.70/291.56 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (42) 622.70/291.56 Complex Obligation (BEST) 622.70/291.56 622.70/291.56 ---------------------------------------- 622.70/291.56 622.70/291.56 (43) 622.70/291.56 Obligation: 622.70/291.56 Proved the lower bound n^1 for the following obligation: 622.70/291.56 622.70/291.56 TRS: 622.70/291.56 Rules: 622.70/291.56 O(0') -> 0' 622.70/291.56 +'(0', x) -> x 622.70/291.56 +'(x, 0') -> x 622.70/291.56 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.56 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.56 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.56 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.56 -(x, 0') -> x 622.70/291.56 -(0', x) -> 0' 622.70/291.56 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.56 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.56 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.56 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.56 not(true) -> false 622.70/291.56 not(false) -> true 622.70/291.56 and(x, true) -> x 622.70/291.56 and(x, false) -> false 622.70/291.56 if(true, x, y) -> x 622.70/291.56 if(false, x, y) -> y 622.70/291.56 ge(O(x), O(y)) -> ge(x, y) 622.70/291.56 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.56 ge(I(x), O(y)) -> ge(x, y) 622.70/291.56 ge(I(x), I(y)) -> ge(x, y) 622.70/291.56 ge(x, 0') -> true 622.70/291.56 ge(0', O(x)) -> ge(0', x) 622.70/291.56 ge(0', I(x)) -> false 622.70/291.56 Log'(0') -> 0' 622.70/291.56 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.56 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.56 Log(x) -> -(Log'(x), I(0')) 622.70/291.56 Val(L(x)) -> x 622.70/291.56 Val(N(x, l, r)) -> x 622.70/291.56 Min(L(x)) -> x 622.70/291.56 Min(N(x, l, r)) -> Min(l) 622.70/291.56 Max(L(x)) -> x 622.70/291.56 Max(N(x, l, r)) -> Max(r) 622.70/291.56 BS(L(x)) -> true 622.70/291.56 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.56 Size(L(x)) -> I(0') 622.70/291.56 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.56 WB(L(x)) -> true 622.70/291.56 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))) 622.70/291.56 622.70/291.56 Types: 622.70/291.56 O :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 0' :: 0':I:1':true:false 622.70/291.56 +' :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 I :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 - :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 1' :: 0':I:1':true:false 622.70/291.56 not :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.56 true :: 0':I:1':true:false 622.70/291.56 false :: 0':I:1':true:false 622.70/291.57 and :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 if :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 ge :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log' :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Val :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 L :: 0':I:1':true:false -> L:l:r:N 622.70/291.57 N :: 0':I:1':true:false -> L:l:r:N -> L:l:r:N -> L:l:r:N 622.70/291.57 l :: L:l:r:N 622.70/291.57 r :: L:l:r:N 622.70/291.57 Min :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Max :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 BS :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Size :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 WB :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 hole_0':I:1':true:false1_0 :: 0':I:1':true:false 622.70/291.57 hole_L:l:r:N2_0 :: L:l:r:N 622.70/291.57 gen_0':I:1':true:false3_0 :: Nat -> 0':I:1':true:false 622.70/291.57 gen_L:l:r:N4_0 :: Nat -> L:l:r:N 622.70/291.57 622.70/291.57 622.70/291.57 Generator Equations: 622.70/291.57 gen_0':I:1':true:false3_0(0) <=> 0' 622.70/291.57 gen_0':I:1':true:false3_0(+(x, 1)) <=> I(gen_0':I:1':true:false3_0(x)) 622.70/291.57 gen_L:l:r:N4_0(0) <=> L(0') 622.70/291.57 gen_L:l:r:N4_0(+(x, 1)) <=> N(0', L(0'), gen_L:l:r:N4_0(x)) 622.70/291.57 622.70/291.57 622.70/291.57 The following defined symbols remain to be analysed: 622.70/291.57 +', -, ge, Log', Min, Max, BS, Size, WB 622.70/291.57 622.70/291.57 They will be analysed ascendingly in the following order: 622.70/291.57 +' < Log' 622.70/291.57 +' < Size 622.70/291.57 - < WB 622.70/291.57 ge < Log' 622.70/291.57 ge < BS 622.70/291.57 ge < WB 622.70/291.57 Min < BS 622.70/291.57 Max < BS 622.70/291.57 Size < WB 622.70/291.57 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (44) LowerBoundPropagationProof (FINISHED) 622.70/291.57 Propagated lower bound. 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (45) 622.70/291.57 BOUNDS(n^1, INF) 622.70/291.57 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (46) 622.70/291.57 Obligation: 622.70/291.57 TRS: 622.70/291.57 Rules: 622.70/291.57 O(0') -> 0' 622.70/291.57 +'(0', x) -> x 622.70/291.57 +'(x, 0') -> x 622.70/291.57 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.57 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.57 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.57 -(x, 0') -> x 622.70/291.57 -(0', x) -> 0' 622.70/291.57 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.57 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.57 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.57 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.57 not(true) -> false 622.70/291.57 not(false) -> true 622.70/291.57 and(x, true) -> x 622.70/291.57 and(x, false) -> false 622.70/291.57 if(true, x, y) -> x 622.70/291.57 if(false, x, y) -> y 622.70/291.57 ge(O(x), O(y)) -> ge(x, y) 622.70/291.57 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.57 ge(I(x), O(y)) -> ge(x, y) 622.70/291.57 ge(I(x), I(y)) -> ge(x, y) 622.70/291.57 ge(x, 0') -> true 622.70/291.57 ge(0', O(x)) -> ge(0', x) 622.70/291.57 ge(0', I(x)) -> false 622.70/291.57 Log'(0') -> 0' 622.70/291.57 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.57 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.57 Log(x) -> -(Log'(x), I(0')) 622.70/291.57 Val(L(x)) -> x 622.70/291.57 Val(N(x, l, r)) -> x 622.70/291.57 Min(L(x)) -> x 622.70/291.57 Min(N(x, l, r)) -> Min(l) 622.70/291.57 Max(L(x)) -> x 622.70/291.57 Max(N(x, l, r)) -> Max(r) 622.70/291.57 BS(L(x)) -> true 622.70/291.57 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.57 Size(L(x)) -> I(0') 622.70/291.57 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.57 WB(L(x)) -> true 622.70/291.57 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))) 622.70/291.57 622.70/291.57 Types: 622.70/291.57 O :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 0' :: 0':I:1':true:false 622.70/291.57 +' :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 I :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 - :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 1' :: 0':I:1':true:false 622.70/291.57 not :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 true :: 0':I:1':true:false 622.70/291.57 false :: 0':I:1':true:false 622.70/291.57 and :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 if :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 ge :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log' :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Val :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 L :: 0':I:1':true:false -> L:l:r:N 622.70/291.57 N :: 0':I:1':true:false -> L:l:r:N -> L:l:r:N -> L:l:r:N 622.70/291.57 l :: L:l:r:N 622.70/291.57 r :: L:l:r:N 622.70/291.57 Min :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Max :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 BS :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Size :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 WB :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 hole_0':I:1':true:false1_0 :: 0':I:1':true:false 622.70/291.57 hole_L:l:r:N2_0 :: L:l:r:N 622.70/291.57 gen_0':I:1':true:false3_0 :: Nat -> 0':I:1':true:false 622.70/291.57 gen_L:l:r:N4_0 :: Nat -> L:l:r:N 622.70/291.57 622.70/291.57 622.70/291.57 Lemmas: 622.70/291.57 +'(gen_0':I:1':true:false3_0(+(1, n6_0)), gen_0':I:1':true:false3_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0) 622.70/291.57 622.70/291.57 622.70/291.57 Generator Equations: 622.70/291.57 gen_0':I:1':true:false3_0(0) <=> 0' 622.70/291.57 gen_0':I:1':true:false3_0(+(x, 1)) <=> I(gen_0':I:1':true:false3_0(x)) 622.70/291.57 gen_L:l:r:N4_0(0) <=> L(0') 622.70/291.57 gen_L:l:r:N4_0(+(x, 1)) <=> N(0', L(0'), gen_L:l:r:N4_0(x)) 622.70/291.57 622.70/291.57 622.70/291.57 The following defined symbols remain to be analysed: 622.70/291.57 -, ge, Log', Min, Max, BS, Size, WB 622.70/291.57 622.70/291.57 They will be analysed ascendingly in the following order: 622.70/291.57 - < WB 622.70/291.57 ge < Log' 622.70/291.57 ge < BS 622.70/291.57 ge < WB 622.70/291.57 Min < BS 622.70/291.57 Max < BS 622.70/291.57 Size < WB 622.70/291.57 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (47) RewriteLemmaProof (LOWER BOUND(ID)) 622.70/291.57 Proved the following rewrite lemma: 622.70/291.57 -(gen_0':I:1':true:false3_0(n363279_0), gen_0':I:1':true:false3_0(n363279_0)) -> gen_0':I:1':true:false3_0(0), rt in Omega(1 + n363279_0) 622.70/291.57 622.70/291.57 Induction Base: 622.70/291.57 -(gen_0':I:1':true:false3_0(0), gen_0':I:1':true:false3_0(0)) ->_R^Omega(1) 622.70/291.57 gen_0':I:1':true:false3_0(0) 622.70/291.57 622.70/291.57 Induction Step: 622.70/291.57 -(gen_0':I:1':true:false3_0(+(n363279_0, 1)), gen_0':I:1':true:false3_0(+(n363279_0, 1))) ->_R^Omega(1) 622.70/291.57 O(-(gen_0':I:1':true:false3_0(n363279_0), gen_0':I:1':true:false3_0(n363279_0))) ->_IH 622.70/291.57 O(gen_0':I:1':true:false3_0(0)) ->_R^Omega(1) 622.70/291.57 0' 622.70/291.57 622.70/291.57 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (48) 622.70/291.57 Obligation: 622.70/291.57 TRS: 622.70/291.57 Rules: 622.70/291.57 O(0') -> 0' 622.70/291.57 +'(0', x) -> x 622.70/291.57 +'(x, 0') -> x 622.70/291.57 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.57 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.57 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.57 -(x, 0') -> x 622.70/291.57 -(0', x) -> 0' 622.70/291.57 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.57 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.57 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.57 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.57 not(true) -> false 622.70/291.57 not(false) -> true 622.70/291.57 and(x, true) -> x 622.70/291.57 and(x, false) -> false 622.70/291.57 if(true, x, y) -> x 622.70/291.57 if(false, x, y) -> y 622.70/291.57 ge(O(x), O(y)) -> ge(x, y) 622.70/291.57 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.57 ge(I(x), O(y)) -> ge(x, y) 622.70/291.57 ge(I(x), I(y)) -> ge(x, y) 622.70/291.57 ge(x, 0') -> true 622.70/291.57 ge(0', O(x)) -> ge(0', x) 622.70/291.57 ge(0', I(x)) -> false 622.70/291.57 Log'(0') -> 0' 622.70/291.57 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.57 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.57 Log(x) -> -(Log'(x), I(0')) 622.70/291.57 Val(L(x)) -> x 622.70/291.57 Val(N(x, l, r)) -> x 622.70/291.57 Min(L(x)) -> x 622.70/291.57 Min(N(x, l, r)) -> Min(l) 622.70/291.57 Max(L(x)) -> x 622.70/291.57 Max(N(x, l, r)) -> Max(r) 622.70/291.57 BS(L(x)) -> true 622.70/291.57 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.57 Size(L(x)) -> I(0') 622.70/291.57 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.57 WB(L(x)) -> true 622.70/291.57 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))) 622.70/291.57 622.70/291.57 Types: 622.70/291.57 O :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 0' :: 0':I:1':true:false 622.70/291.57 +' :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 I :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 - :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 1' :: 0':I:1':true:false 622.70/291.57 not :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 true :: 0':I:1':true:false 622.70/291.57 false :: 0':I:1':true:false 622.70/291.57 and :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 if :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 ge :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log' :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Val :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 L :: 0':I:1':true:false -> L:l:r:N 622.70/291.57 N :: 0':I:1':true:false -> L:l:r:N -> L:l:r:N -> L:l:r:N 622.70/291.57 l :: L:l:r:N 622.70/291.57 r :: L:l:r:N 622.70/291.57 Min :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Max :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 BS :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Size :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 WB :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 hole_0':I:1':true:false1_0 :: 0':I:1':true:false 622.70/291.57 hole_L:l:r:N2_0 :: L:l:r:N 622.70/291.57 gen_0':I:1':true:false3_0 :: Nat -> 0':I:1':true:false 622.70/291.57 gen_L:l:r:N4_0 :: Nat -> L:l:r:N 622.70/291.57 622.70/291.57 622.70/291.57 Lemmas: 622.70/291.57 +'(gen_0':I:1':true:false3_0(+(1, n6_0)), gen_0':I:1':true:false3_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0) 622.70/291.57 -(gen_0':I:1':true:false3_0(n363279_0), gen_0':I:1':true:false3_0(n363279_0)) -> gen_0':I:1':true:false3_0(0), rt in Omega(1 + n363279_0) 622.70/291.57 622.70/291.57 622.70/291.57 Generator Equations: 622.70/291.57 gen_0':I:1':true:false3_0(0) <=> 0' 622.70/291.57 gen_0':I:1':true:false3_0(+(x, 1)) <=> I(gen_0':I:1':true:false3_0(x)) 622.70/291.57 gen_L:l:r:N4_0(0) <=> L(0') 622.70/291.57 gen_L:l:r:N4_0(+(x, 1)) <=> N(0', L(0'), gen_L:l:r:N4_0(x)) 622.70/291.57 622.70/291.57 622.70/291.57 The following defined symbols remain to be analysed: 622.70/291.57 ge, Log', Min, Max, BS, Size, WB 622.70/291.57 622.70/291.57 They will be analysed ascendingly in the following order: 622.70/291.57 ge < Log' 622.70/291.57 ge < BS 622.70/291.57 ge < WB 622.70/291.57 Min < BS 622.70/291.57 Max < BS 622.70/291.57 Size < WB 622.70/291.57 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (49) RewriteLemmaProof (LOWER BOUND(ID)) 622.70/291.57 Proved the following rewrite lemma: 622.70/291.57 ge(gen_0':I:1':true:false3_0(n365401_0), gen_0':I:1':true:false3_0(n365401_0)) -> true, rt in Omega(1 + n365401_0) 622.70/291.57 622.70/291.57 Induction Base: 622.70/291.57 ge(gen_0':I:1':true:false3_0(0), gen_0':I:1':true:false3_0(0)) ->_R^Omega(1) 622.70/291.57 true 622.70/291.57 622.70/291.57 Induction Step: 622.70/291.57 ge(gen_0':I:1':true:false3_0(+(n365401_0, 1)), gen_0':I:1':true:false3_0(+(n365401_0, 1))) ->_R^Omega(1) 622.70/291.57 ge(gen_0':I:1':true:false3_0(n365401_0), gen_0':I:1':true:false3_0(n365401_0)) ->_IH 622.70/291.57 true 622.70/291.57 622.70/291.57 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (50) 622.70/291.57 Obligation: 622.70/291.57 TRS: 622.70/291.57 Rules: 622.70/291.57 O(0') -> 0' 622.70/291.57 +'(0', x) -> x 622.70/291.57 +'(x, 0') -> x 622.70/291.57 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.57 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.57 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.57 -(x, 0') -> x 622.70/291.57 -(0', x) -> 0' 622.70/291.57 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.57 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.57 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.57 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.57 not(true) -> false 622.70/291.57 not(false) -> true 622.70/291.57 and(x, true) -> x 622.70/291.57 and(x, false) -> false 622.70/291.57 if(true, x, y) -> x 622.70/291.57 if(false, x, y) -> y 622.70/291.57 ge(O(x), O(y)) -> ge(x, y) 622.70/291.57 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.57 ge(I(x), O(y)) -> ge(x, y) 622.70/291.57 ge(I(x), I(y)) -> ge(x, y) 622.70/291.57 ge(x, 0') -> true 622.70/291.57 ge(0', O(x)) -> ge(0', x) 622.70/291.57 ge(0', I(x)) -> false 622.70/291.57 Log'(0') -> 0' 622.70/291.57 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.57 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.57 Log(x) -> -(Log'(x), I(0')) 622.70/291.57 Val(L(x)) -> x 622.70/291.57 Val(N(x, l, r)) -> x 622.70/291.57 Min(L(x)) -> x 622.70/291.57 Min(N(x, l, r)) -> Min(l) 622.70/291.57 Max(L(x)) -> x 622.70/291.57 Max(N(x, l, r)) -> Max(r) 622.70/291.57 BS(L(x)) -> true 622.70/291.57 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.57 Size(L(x)) -> I(0') 622.70/291.57 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.57 WB(L(x)) -> true 622.70/291.57 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))) 622.70/291.57 622.70/291.57 Types: 622.70/291.57 O :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 0' :: 0':I:1':true:false 622.70/291.57 +' :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 I :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 - :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 1' :: 0':I:1':true:false 622.70/291.57 not :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 true :: 0':I:1':true:false 622.70/291.57 false :: 0':I:1':true:false 622.70/291.57 and :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 if :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 ge :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log' :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Val :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 L :: 0':I:1':true:false -> L:l:r:N 622.70/291.57 N :: 0':I:1':true:false -> L:l:r:N -> L:l:r:N -> L:l:r:N 622.70/291.57 l :: L:l:r:N 622.70/291.57 r :: L:l:r:N 622.70/291.57 Min :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Max :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 BS :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Size :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 WB :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 hole_0':I:1':true:false1_0 :: 0':I:1':true:false 622.70/291.57 hole_L:l:r:N2_0 :: L:l:r:N 622.70/291.57 gen_0':I:1':true:false3_0 :: Nat -> 0':I:1':true:false 622.70/291.57 gen_L:l:r:N4_0 :: Nat -> L:l:r:N 622.70/291.57 622.70/291.57 622.70/291.57 Lemmas: 622.70/291.57 +'(gen_0':I:1':true:false3_0(+(1, n6_0)), gen_0':I:1':true:false3_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0) 622.70/291.57 -(gen_0':I:1':true:false3_0(n363279_0), gen_0':I:1':true:false3_0(n363279_0)) -> gen_0':I:1':true:false3_0(0), rt in Omega(1 + n363279_0) 622.70/291.57 ge(gen_0':I:1':true:false3_0(n365401_0), gen_0':I:1':true:false3_0(n365401_0)) -> true, rt in Omega(1 + n365401_0) 622.70/291.57 622.70/291.57 622.70/291.57 Generator Equations: 622.70/291.57 gen_0':I:1':true:false3_0(0) <=> 0' 622.70/291.57 gen_0':I:1':true:false3_0(+(x, 1)) <=> I(gen_0':I:1':true:false3_0(x)) 622.70/291.57 gen_L:l:r:N4_0(0) <=> L(0') 622.70/291.57 gen_L:l:r:N4_0(+(x, 1)) <=> N(0', L(0'), gen_L:l:r:N4_0(x)) 622.70/291.57 622.70/291.57 622.70/291.57 The following defined symbols remain to be analysed: 622.70/291.57 Log', Min, Max, BS, Size, WB 622.70/291.57 622.70/291.57 They will be analysed ascendingly in the following order: 622.70/291.57 Min < BS 622.70/291.57 Max < BS 622.70/291.57 Size < WB 622.70/291.57 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (51) RewriteLemmaProof (LOWER BOUND(ID)) 622.70/291.57 Proved the following rewrite lemma: 622.70/291.57 Log'(gen_0':I:1':true:false3_0(+(1, n369008_0))) -> *5_0, rt in Omega(n369008_0) 622.70/291.57 622.70/291.57 Induction Base: 622.70/291.57 Log'(gen_0':I:1':true:false3_0(+(1, 0))) 622.70/291.57 622.70/291.57 Induction Step: 622.70/291.57 Log'(gen_0':I:1':true:false3_0(+(1, +(n369008_0, 1)))) ->_R^Omega(1) 622.70/291.57 +'(Log'(gen_0':I:1':true:false3_0(+(1, n369008_0))), I(0')) ->_IH 622.70/291.57 +'(*5_0, I(0')) 622.70/291.57 622.70/291.57 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 622.70/291.57 ---------------------------------------- 622.70/291.57 622.70/291.57 (52) 622.70/291.57 Obligation: 622.70/291.57 TRS: 622.70/291.57 Rules: 622.70/291.57 O(0') -> 0' 622.70/291.57 +'(0', x) -> x 622.70/291.57 +'(x, 0') -> x 622.70/291.57 +'(O(x), O(y)) -> O(+'(x, y)) 622.70/291.57 +'(O(x), I(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), O(y)) -> I(+'(x, y)) 622.70/291.57 +'(I(x), I(y)) -> O(+'(+'(x, y), I(0'))) 622.70/291.57 +'(x, +'(y, z)) -> +'(+'(x, y), z) 622.70/291.57 -(x, 0') -> x 622.70/291.57 -(0', x) -> 0' 622.70/291.57 -(O(x), O(y)) -> O(-(x, y)) 622.70/291.57 -(O(x), I(y)) -> I(-(-(x, y), I(1'))) 622.70/291.57 -(I(x), O(y)) -> I(-(x, y)) 622.70/291.57 -(I(x), I(y)) -> O(-(x, y)) 622.70/291.57 not(true) -> false 622.70/291.57 not(false) -> true 622.70/291.57 and(x, true) -> x 622.70/291.57 and(x, false) -> false 622.70/291.57 if(true, x, y) -> x 622.70/291.57 if(false, x, y) -> y 622.70/291.57 ge(O(x), O(y)) -> ge(x, y) 622.70/291.57 ge(O(x), I(y)) -> not(ge(y, x)) 622.70/291.57 ge(I(x), O(y)) -> ge(x, y) 622.70/291.57 ge(I(x), I(y)) -> ge(x, y) 622.70/291.57 ge(x, 0') -> true 622.70/291.57 ge(0', O(x)) -> ge(0', x) 622.70/291.57 ge(0', I(x)) -> false 622.70/291.57 Log'(0') -> 0' 622.70/291.57 Log'(I(x)) -> +'(Log'(x), I(0')) 622.70/291.57 Log'(O(x)) -> if(ge(x, I(0')), +'(Log'(x), I(0')), 0') 622.70/291.57 Log(x) -> -(Log'(x), I(0')) 622.70/291.57 Val(L(x)) -> x 622.70/291.57 Val(N(x, l, r)) -> x 622.70/291.57 Min(L(x)) -> x 622.70/291.57 Min(N(x, l, r)) -> Min(l) 622.70/291.57 Max(L(x)) -> x 622.70/291.57 Max(N(x, l, r)) -> Max(r) 622.70/291.57 BS(L(x)) -> true 622.70/291.57 BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r))) 622.70/291.57 Size(L(x)) -> I(0') 622.70/291.57 Size(N(x, l, r)) -> +'(+'(Size(l), Size(r)), I(1')) 622.70/291.57 WB(L(x)) -> true 622.70/291.57 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))) 622.70/291.57 622.70/291.57 Types: 622.70/291.57 O :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 0' :: 0':I:1':true:false 622.70/291.57 +' :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 I :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 - :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 1' :: 0':I:1':true:false 622.70/291.57 not :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 true :: 0':I:1':true:false 622.70/291.57 false :: 0':I:1':true:false 622.70/291.57 and :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 if :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 ge :: 0':I:1':true:false -> 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log' :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Log :: 0':I:1':true:false -> 0':I:1':true:false 622.70/291.57 Val :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 L :: 0':I:1':true:false -> L:l:r:N 622.70/291.57 N :: 0':I:1':true:false -> L:l:r:N -> L:l:r:N -> L:l:r:N 622.70/291.57 l :: L:l:r:N 622.70/291.57 r :: L:l:r:N 622.70/291.57 Min :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Max :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 BS :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 Size :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 WB :: L:l:r:N -> 0':I:1':true:false 622.70/291.57 hole_0':I:1':true:false1_0 :: 0':I:1':true:false 622.70/291.57 hole_L:l:r:N2_0 :: L:l:r:N 622.70/291.57 gen_0':I:1':true:false3_0 :: Nat -> 0':I:1':true:false 622.70/291.57 gen_L:l:r:N4_0 :: Nat -> L:l:r:N 622.70/291.57 622.70/291.57 622.70/291.57 Lemmas: 622.70/291.57 +'(gen_0':I:1':true:false3_0(+(1, n6_0)), gen_0':I:1':true:false3_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0) 622.70/291.57 -(gen_0':I:1':true:false3_0(n363279_0), gen_0':I:1':true:false3_0(n363279_0)) -> gen_0':I:1':true:false3_0(0), rt in Omega(1 + n363279_0) 622.70/291.57 ge(gen_0':I:1':true:false3_0(n365401_0), gen_0':I:1':true:false3_0(n365401_0)) -> true, rt in Omega(1 + n365401_0) 622.70/291.57 Log'(gen_0':I:1':true:false3_0(+(1, n369008_0))) -> *5_0, rt in Omega(n369008_0) 622.70/291.57 622.70/291.57 622.70/291.57 Generator Equations: 622.70/291.57 gen_0':I:1':true:false3_0(0) <=> 0' 622.70/291.57 gen_0':I:1':true:false3_0(+(x, 1)) <=> I(gen_0':I:1':true:false3_0(x)) 622.70/291.57 gen_L:l:r:N4_0(0) <=> L(0') 622.70/291.57 gen_L:l:r:N4_0(+(x, 1)) <=> N(0', L(0'), gen_L:l:r:N4_0(x)) 622.70/291.57 622.70/291.57 622.70/291.57 The following defined symbols remain to be analysed: 622.70/291.57 Min, Max, BS, Size, WB 622.70/291.57 622.70/291.57 They will be analysed ascendingly in the following order: 622.70/291.57 Min < BS 622.70/291.57 Max < BS 622.70/291.57 Size < WB 622.87/291.61 EOF