16.70/5.10 WORST_CASE(Omega(n^1), O(n^1)) 16.70/5.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 16.70/5.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 16.70/5.11 16.70/5.11 16.70/5.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 16.70/5.11 16.70/5.11 (0) CpxTRS 16.70/5.11 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 16.70/5.11 (2) CpxTRS 16.70/5.11 (3) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms] 16.70/5.11 (4) CpxRelTRS 16.70/5.11 (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 16.70/5.11 (6) CpxRelTRS 16.70/5.11 (7) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 16.70/5.11 (8) CdtProblem 16.70/5.11 (9) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 16.70/5.11 (10) CdtProblem 16.70/5.11 (11) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 16.70/5.11 (12) CdtProblem 16.70/5.11 (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 16.70/5.11 (14) CdtProblem 16.70/5.11 (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 66 ms] 16.70/5.11 (16) CdtProblem 16.70/5.11 (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 21 ms] 16.70/5.11 (18) CdtProblem 16.70/5.11 (19) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 16.70/5.11 (20) BOUNDS(1, 1) 16.70/5.11 (21) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 16.70/5.11 (22) CpxTRS 16.70/5.11 (23) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 16.70/5.11 (24) typed CpxTrs 16.70/5.11 (25) OrderProof [LOWER BOUND(ID), 0 ms] 16.70/5.11 (26) typed CpxTrs 16.70/5.11 (27) RewriteLemmaProof [LOWER BOUND(ID), 574 ms] 16.70/5.11 (28) BEST 16.70/5.11 (29) proven lower bound 16.70/5.11 (30) LowerBoundPropagationProof [FINISHED, 0 ms] 16.70/5.11 (31) BOUNDS(n^1, INF) 16.70/5.11 (32) typed CpxTrs 16.70/5.11 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (0) 16.70/5.11 Obligation: 16.70/5.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 16.70/5.11 16.70/5.11 16.70/5.11 The TRS R consists of the following rules: 16.70/5.11 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(b(x, y)) -> b(D(x), D(y)) 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 S is empty. 16.70/5.11 Rewrite Strategy: FULL 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 16.70/5.11 The following defined symbols can occur below the 0th argument of b: b, D 16.70/5.11 The following defined symbols can occur below the 1th argument of b: b, D 16.70/5.11 16.70/5.11 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 16.70/5.11 D(b(x, y)) -> b(D(x), D(y)) 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (2) 16.70/5.11 Obligation: 16.70/5.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 16.70/5.11 16.70/5.11 16.70/5.11 The TRS R consists of the following rules: 16.70/5.11 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 S is empty. 16.70/5.11 Rewrite Strategy: FULL 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (3) NonCtorToCtorProof (UPPER BOUND(ID)) 16.70/5.11 transformed non-ctor to ctor-system 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (4) 16.70/5.11 Obligation: 16.70/5.11 The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). 16.70/5.11 16.70/5.11 16.70/5.11 The TRS R consists of the following rules: 16.70/5.11 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(c_b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 The (relative) TRS S consists of the following rules: 16.70/5.11 16.70/5.11 b(x0, x1) -> c_b(x0, x1) 16.70/5.11 16.70/5.11 Rewrite Strategy: FULL 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (5) RcToIrcProof (BOTH BOUNDS(ID, ID)) 16.70/5.11 Converted rc-obligation to irc-obligation. 16.70/5.11 16.70/5.11 The duplicating contexts are: 16.70/5.11 D(c(x, [])) 16.70/5.11 D(c([], y)) 16.70/5.11 D(div([], y)) 16.70/5.11 D(div(x, [])) 16.70/5.11 D(ln([])) 16.70/5.11 D(pow(x, [])) 16.70/5.11 D(pow([], y)) 16.70/5.11 16.70/5.11 16.70/5.11 The defined contexts are: 16.70/5.11 b(x0, []) 16.70/5.11 b(c(x0, []), c(x2, x3)) 16.70/5.11 b(c(x0, x1), c(x2, [])) 16.70/5.11 b(c(c(x0, pow(x1, m(x2, 1))), []), c(c(pow(x4, x5), ln(x6)), x7)) 16.70/5.11 b(c(c(x0, pow(x1, m(x2, 1))), x3), c(c(pow(x4, x5), ln(x6)), [])) 16.70/5.11 16.70/5.11 16.70/5.11 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (6) 16.70/5.11 Obligation: 16.70/5.11 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). 16.70/5.11 16.70/5.11 16.70/5.11 The TRS R consists of the following rules: 16.70/5.11 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(c_b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 The (relative) TRS S consists of the following rules: 16.70/5.11 16.70/5.11 b(x0, x1) -> c_b(x0, x1) 16.70/5.11 16.70/5.11 Rewrite Strategy: INNERMOST 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (7) CpxTrsToCdtProof (UPPER BOUND(ID)) 16.70/5.11 Converted Cpx (relative) TRS to CDT 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (8) 16.70/5.11 Obligation: 16.70/5.11 Complexity Dependency Tuples Problem 16.70/5.11 16.70/5.11 Rules: 16.70/5.11 b(z0, z1) -> c_b(z0, z1) 16.70/5.11 b(h, z0) -> z0 16.70/5.11 b(z0, h) -> z0 16.70/5.11 b(s(z0), s(z1)) -> s(s(b(z0, z1))) 16.70/5.11 b(c_b(z0, z1), z2) -> b(z0, b(z1, z2)) 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(c(z0, z1)) -> b(c(z1, D(z0)), c(z0, D(z1))) 16.70/5.11 D(m(z0, z1)) -> m(D(z0), D(z1)) 16.70/5.11 D(opp(z0)) -> opp(D(z0)) 16.70/5.11 D(div(z0, z1)) -> m(div(D(z0), z1), div(c(z0, D(z1)), pow(z1, 2))) 16.70/5.11 D(ln(z0)) -> div(D(z0), z0) 16.70/5.11 D(pow(z0, z1)) -> b(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))) 16.70/5.11 Tuples: 16.70/5.11 B(z0, z1) -> c1 16.70/5.11 B(h, z0) -> c2 16.70/5.11 B(z0, h) -> c3 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(t) -> c6 16.70/5.11 D'(constant) -> c7 16.70/5.11 D'(c(z0, z1)) -> c8(B(c(z1, D(z0)), c(z0, D(z1))), D'(z0), D'(z1)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(pow(z0, z1)) -> c13(B(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))), D'(z0), D'(z1)) 16.70/5.11 S tuples: 16.70/5.11 B(h, z0) -> c2 16.70/5.11 B(z0, h) -> c3 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(t) -> c6 16.70/5.11 D'(constant) -> c7 16.70/5.11 D'(c(z0, z1)) -> c8(B(c(z1, D(z0)), c(z0, D(z1))), D'(z0), D'(z1)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(pow(z0, z1)) -> c13(B(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))), D'(z0), D'(z1)) 16.70/5.11 K tuples:none 16.70/5.11 Defined Rule Symbols: D_1, b_2 16.70/5.11 16.70/5.11 Defined Pair Symbols: B_2, D'_1 16.70/5.11 16.70/5.11 Compound Symbols: c1, c2, c3, c4_1, c5_2, c6, c7, c8_3, c9_2, c10_1, c11_2, c12_1, c13_3 16.70/5.11 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (9) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 16.70/5.11 Removed 5 trailing nodes: 16.70/5.11 D'(t) -> c6 16.70/5.11 D'(constant) -> c7 16.70/5.11 B(h, z0) -> c2 16.70/5.11 B(z0, h) -> c3 16.70/5.11 B(z0, z1) -> c1 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (10) 16.70/5.11 Obligation: 16.70/5.11 Complexity Dependency Tuples Problem 16.70/5.11 16.70/5.11 Rules: 16.70/5.11 b(z0, z1) -> c_b(z0, z1) 16.70/5.11 b(h, z0) -> z0 16.70/5.11 b(z0, h) -> z0 16.70/5.11 b(s(z0), s(z1)) -> s(s(b(z0, z1))) 16.70/5.11 b(c_b(z0, z1), z2) -> b(z0, b(z1, z2)) 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(c(z0, z1)) -> b(c(z1, D(z0)), c(z0, D(z1))) 16.70/5.11 D(m(z0, z1)) -> m(D(z0), D(z1)) 16.70/5.11 D(opp(z0)) -> opp(D(z0)) 16.70/5.11 D(div(z0, z1)) -> m(div(D(z0), z1), div(c(z0, D(z1)), pow(z1, 2))) 16.70/5.11 D(ln(z0)) -> div(D(z0), z0) 16.70/5.11 D(pow(z0, z1)) -> b(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))) 16.70/5.11 Tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(c(z0, z1)) -> c8(B(c(z1, D(z0)), c(z0, D(z1))), D'(z0), D'(z1)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(pow(z0, z1)) -> c13(B(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))), D'(z0), D'(z1)) 16.70/5.11 S tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(c(z0, z1)) -> c8(B(c(z1, D(z0)), c(z0, D(z1))), D'(z0), D'(z1)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(pow(z0, z1)) -> c13(B(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))), D'(z0), D'(z1)) 16.70/5.11 K tuples:none 16.70/5.11 Defined Rule Symbols: D_1, b_2 16.70/5.11 16.70/5.11 Defined Pair Symbols: B_2, D'_1 16.70/5.11 16.70/5.11 Compound Symbols: c4_1, c5_2, c8_3, c9_2, c10_1, c11_2, c12_1, c13_3 16.70/5.11 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (11) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 16.70/5.11 Removed 2 trailing tuple parts 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (12) 16.70/5.11 Obligation: 16.70/5.11 Complexity Dependency Tuples Problem 16.70/5.11 16.70/5.11 Rules: 16.70/5.11 b(z0, z1) -> c_b(z0, z1) 16.70/5.11 b(h, z0) -> z0 16.70/5.11 b(z0, h) -> z0 16.70/5.11 b(s(z0), s(z1)) -> s(s(b(z0, z1))) 16.70/5.11 b(c_b(z0, z1), z2) -> b(z0, b(z1, z2)) 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(c(z0, z1)) -> b(c(z1, D(z0)), c(z0, D(z1))) 16.70/5.11 D(m(z0, z1)) -> m(D(z0), D(z1)) 16.70/5.11 D(opp(z0)) -> opp(D(z0)) 16.70/5.11 D(div(z0, z1)) -> m(div(D(z0), z1), div(c(z0, D(z1)), pow(z1, 2))) 16.70/5.11 D(ln(z0)) -> div(D(z0), z0) 16.70/5.11 D(pow(z0, z1)) -> b(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))) 16.70/5.11 Tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 S tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 K tuples:none 16.70/5.11 Defined Rule Symbols: D_1, b_2 16.70/5.11 16.70/5.11 Defined Pair Symbols: B_2, D'_1 16.70/5.11 16.70/5.11 Compound Symbols: c4_1, c5_2, c9_2, c10_1, c11_2, c12_1, c8_2, c13_2 16.70/5.11 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 16.70/5.11 The following rules are not usable and were removed: 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(c(z0, z1)) -> b(c(z1, D(z0)), c(z0, D(z1))) 16.70/5.11 D(m(z0, z1)) -> m(D(z0), D(z1)) 16.70/5.11 D(opp(z0)) -> opp(D(z0)) 16.70/5.11 D(div(z0, z1)) -> m(div(D(z0), z1), div(c(z0, D(z1)), pow(z1, 2))) 16.70/5.11 D(ln(z0)) -> div(D(z0), z0) 16.70/5.11 D(pow(z0, z1)) -> b(c(c(z1, pow(z0, m(z1, 1))), D(z0)), c(c(pow(z0, z1), ln(z0)), D(z1))) 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (14) 16.70/5.11 Obligation: 16.70/5.11 Complexity Dependency Tuples Problem 16.70/5.11 16.70/5.11 Rules: 16.70/5.11 b(z0, z1) -> c_b(z0, z1) 16.70/5.11 b(h, z0) -> z0 16.70/5.11 b(z0, h) -> z0 16.70/5.11 b(s(z0), s(z1)) -> s(s(b(z0, z1))) 16.70/5.11 b(c_b(z0, z1), z2) -> b(z0, b(z1, z2)) 16.70/5.11 Tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 S tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 K tuples:none 16.70/5.11 Defined Rule Symbols: b_2 16.70/5.11 16.70/5.11 Defined Pair Symbols: B_2, D'_1 16.70/5.11 16.70/5.11 Compound Symbols: c4_1, c5_2, c9_2, c10_1, c11_2, c12_1, c8_2, c13_2 16.70/5.11 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 16.70/5.11 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 We considered the (Usable) Rules:none 16.70/5.11 And the Tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 The order we found is given by the following interpretation: 16.70/5.11 16.70/5.11 Polynomial interpretation : 16.70/5.11 16.70/5.11 POL(B(x_1, x_2)) = x_1 16.70/5.11 POL(D'(x_1)) = x_1 16.70/5.11 POL(b(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(c(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(c10(x_1)) = x_1 16.70/5.11 POL(c11(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c12(x_1)) = x_1 16.70/5.11 POL(c13(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c4(x_1)) = x_1 16.70/5.11 POL(c5(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c8(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c9(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c_b(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(div(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(h) = 0 16.70/5.11 POL(ln(x_1)) = [1] + x_1 16.70/5.11 POL(m(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(opp(x_1)) = [1] + x_1 16.70/5.11 POL(pow(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(s(x_1)) = x_1 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (16) 16.70/5.11 Obligation: 16.70/5.11 Complexity Dependency Tuples Problem 16.70/5.11 16.70/5.11 Rules: 16.70/5.11 b(z0, z1) -> c_b(z0, z1) 16.70/5.11 b(h, z0) -> z0 16.70/5.11 b(z0, h) -> z0 16.70/5.11 b(s(z0), s(z1)) -> s(s(b(z0, z1))) 16.70/5.11 b(c_b(z0, z1), z2) -> b(z0, b(z1, z2)) 16.70/5.11 Tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 S tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 K tuples: 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 Defined Rule Symbols: b_2 16.70/5.11 16.70/5.11 Defined Pair Symbols: B_2, D'_1 16.70/5.11 16.70/5.11 Compound Symbols: c4_1, c5_2, c9_2, c10_1, c11_2, c12_1, c8_2, c13_2 16.70/5.11 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 16.70/5.11 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 We considered the (Usable) Rules:none 16.70/5.11 And the Tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 The order we found is given by the following interpretation: 16.70/5.11 16.70/5.11 Polynomial interpretation : 16.70/5.11 16.70/5.11 POL(B(x_1, x_2)) = [1] + x_1 16.70/5.11 POL(D'(x_1)) = 0 16.70/5.11 POL(b(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(c(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(c10(x_1)) = x_1 16.70/5.11 POL(c11(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c12(x_1)) = x_1 16.70/5.11 POL(c13(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c4(x_1)) = x_1 16.70/5.11 POL(c5(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c8(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c9(x_1, x_2)) = x_1 + x_2 16.70/5.11 POL(c_b(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(div(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(h) = 0 16.70/5.11 POL(ln(x_1)) = x_1 16.70/5.11 POL(m(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(opp(x_1)) = x_1 16.70/5.11 POL(pow(x_1, x_2)) = [1] + x_1 + x_2 16.70/5.11 POL(s(x_1)) = [1] + x_1 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (18) 16.70/5.11 Obligation: 16.70/5.11 Complexity Dependency Tuples Problem 16.70/5.11 16.70/5.11 Rules: 16.70/5.11 b(z0, z1) -> c_b(z0, z1) 16.70/5.11 b(h, z0) -> z0 16.70/5.11 b(z0, h) -> z0 16.70/5.11 b(s(z0), s(z1)) -> s(s(b(z0, z1))) 16.70/5.11 b(c_b(z0, z1), z2) -> b(z0, b(z1, z2)) 16.70/5.11 Tuples: 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 S tuples:none 16.70/5.11 K tuples: 16.70/5.11 B(c_b(z0, z1), z2) -> c5(B(z0, b(z1, z2)), B(z1, z2)) 16.70/5.11 D'(m(z0, z1)) -> c9(D'(z0), D'(z1)) 16.70/5.11 D'(opp(z0)) -> c10(D'(z0)) 16.70/5.11 D'(div(z0, z1)) -> c11(D'(z0), D'(z1)) 16.70/5.11 D'(ln(z0)) -> c12(D'(z0)) 16.70/5.11 D'(c(z0, z1)) -> c8(D'(z0), D'(z1)) 16.70/5.11 D'(pow(z0, z1)) -> c13(D'(z0), D'(z1)) 16.70/5.11 B(s(z0), s(z1)) -> c4(B(z0, z1)) 16.70/5.11 Defined Rule Symbols: b_2 16.70/5.11 16.70/5.11 Defined Pair Symbols: B_2, D'_1 16.70/5.11 16.70/5.11 Compound Symbols: c4_1, c5_2, c9_2, c10_1, c11_2, c12_1, c8_2, c13_2 16.70/5.11 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (19) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 16.70/5.11 The set S is empty 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (20) 16.70/5.11 BOUNDS(1, 1) 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (21) RenamingProof (BOTH BOUNDS(ID, ID)) 16.70/5.11 Renamed function symbols to avoid clashes with predefined symbol. 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (22) 16.70/5.11 Obligation: 16.70/5.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 16.70/5.11 16.70/5.11 16.70/5.11 The TRS R consists of the following rules: 16.70/5.11 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(b(x, y)) -> b(D(x), D(y)) 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2'))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1'))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 S is empty. 16.70/5.11 Rewrite Strategy: FULL 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (23) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 16.70/5.11 Infered types. 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (24) 16.70/5.11 Obligation: 16.70/5.11 TRS: 16.70/5.11 Rules: 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(b(x, y)) -> b(D(x), D(y)) 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2'))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1'))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 Types: 16.70/5.11 D :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 t :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 s :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 h :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 constant :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 b :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 c :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 m :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 opp :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 div :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 pow :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 2' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 ln :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 1' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 hole_t:h:s:constant:c:m:opp:div:2':pow:ln:1'1_0 :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0 :: Nat -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (25) OrderProof (LOWER BOUND(ID)) 16.70/5.11 Heuristically decided to analyse the following defined symbols: 16.70/5.11 D, b 16.70/5.11 16.70/5.11 They will be analysed ascendingly in the following order: 16.70/5.11 b < D 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (26) 16.70/5.11 Obligation: 16.70/5.11 TRS: 16.70/5.11 Rules: 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(b(x, y)) -> b(D(x), D(y)) 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2'))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1'))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 Types: 16.70/5.11 D :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 t :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 s :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 h :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 constant :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 b :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 c :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 m :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 opp :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 div :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 pow :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 2' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 ln :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 1' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 hole_t:h:s:constant:c:m:opp:div:2':pow:ln:1'1_0 :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0 :: Nat -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 16.70/5.11 16.70/5.11 Generator Equations: 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(0) <=> t 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(x, 1)) <=> s(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(x)) 16.70/5.11 16.70/5.11 16.70/5.11 The following defined symbols remain to be analysed: 16.70/5.11 b, D 16.70/5.11 16.70/5.11 They will be analysed ascendingly in the following order: 16.70/5.11 b < D 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (27) RewriteLemmaProof (LOWER BOUND(ID)) 16.70/5.11 Proved the following rewrite lemma: 16.70/5.11 b(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, n4_0)), gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0) 16.70/5.11 16.70/5.11 Induction Base: 16.70/5.11 b(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, 0)), gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, 0))) 16.70/5.11 16.70/5.11 Induction Step: 16.70/5.11 b(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, +(n4_0, 1))), gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1) 16.70/5.11 s(s(b(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, n4_0)), gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, n4_0))))) ->_IH 16.70/5.11 s(s(*3_0)) 16.70/5.11 16.70/5.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (28) 16.70/5.11 Complex Obligation (BEST) 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (29) 16.70/5.11 Obligation: 16.70/5.11 Proved the lower bound n^1 for the following obligation: 16.70/5.11 16.70/5.11 TRS: 16.70/5.11 Rules: 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(b(x, y)) -> b(D(x), D(y)) 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2'))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1'))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 Types: 16.70/5.11 D :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 t :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 s :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 h :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 constant :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 b :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 c :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 m :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 opp :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 div :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 pow :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 2' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 ln :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 1' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 hole_t:h:s:constant:c:m:opp:div:2':pow:ln:1'1_0 :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0 :: Nat -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 16.70/5.11 16.70/5.11 Generator Equations: 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(0) <=> t 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(x, 1)) <=> s(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(x)) 16.70/5.11 16.70/5.11 16.70/5.11 The following defined symbols remain to be analysed: 16.70/5.11 b, D 16.70/5.11 16.70/5.11 They will be analysed ascendingly in the following order: 16.70/5.11 b < D 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (30) LowerBoundPropagationProof (FINISHED) 16.70/5.11 Propagated lower bound. 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (31) 16.70/5.11 BOUNDS(n^1, INF) 16.70/5.11 16.70/5.11 ---------------------------------------- 16.70/5.11 16.70/5.11 (32) 16.70/5.11 Obligation: 16.70/5.11 TRS: 16.70/5.11 Rules: 16.70/5.11 D(t) -> s(h) 16.70/5.11 D(constant) -> h 16.70/5.11 D(b(x, y)) -> b(D(x), D(y)) 16.70/5.11 D(c(x, y)) -> b(c(y, D(x)), c(x, D(y))) 16.70/5.11 D(m(x, y)) -> m(D(x), D(y)) 16.70/5.11 D(opp(x)) -> opp(D(x)) 16.70/5.11 D(div(x, y)) -> m(div(D(x), y), div(c(x, D(y)), pow(y, 2'))) 16.70/5.11 D(ln(x)) -> div(D(x), x) 16.70/5.11 D(pow(x, y)) -> b(c(c(y, pow(x, m(y, 1'))), D(x)), c(c(pow(x, y), ln(x)), D(y))) 16.70/5.11 b(h, x) -> x 16.70/5.11 b(x, h) -> x 16.70/5.11 b(s(x), s(y)) -> s(s(b(x, y))) 16.70/5.11 b(b(x, y), z) -> b(x, b(y, z)) 16.70/5.11 16.70/5.11 Types: 16.70/5.11 D :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 t :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 s :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 h :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 constant :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 b :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 c :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 m :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 opp :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 div :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 pow :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 2' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 ln :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 1' :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 hole_t:h:s:constant:c:m:opp:div:2':pow:ln:1'1_0 :: t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0 :: Nat -> t:h:s:constant:c:m:opp:div:2':pow:ln:1' 16.70/5.11 16.70/5.11 16.70/5.11 Lemmas: 16.70/5.11 b(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, n4_0)), gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0) 16.70/5.11 16.70/5.11 16.70/5.11 Generator Equations: 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(0) <=> t 16.70/5.11 gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(+(x, 1)) <=> s(gen_t:h:s:constant:c:m:opp:div:2':pow:ln:1'2_0(x)) 16.70/5.11 16.70/5.11 16.70/5.11 The following defined symbols remain to be analysed: 16.70/5.11 D 16.85/5.18 EOF