12.24/3.89 WORST_CASE(Omega(n^3), O(n^3)) 12.24/3.90 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 12.24/3.90 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.24/3.90 12.24/3.90 12.24/3.90 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 12.24/3.90 12.24/3.90 (0) CpxTRS 12.24/3.90 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 12.24/3.90 (2) CdtProblem 12.24/3.90 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 12.24/3.90 (4) CdtProblem 12.24/3.90 (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 12.24/3.90 (6) CdtProblem 12.24/3.90 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 49 ms] 12.24/3.90 (8) CdtProblem 12.24/3.90 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 35 ms] 12.24/3.90 (10) CdtProblem 12.24/3.90 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 69 ms] 12.24/3.90 (12) CdtProblem 12.24/3.90 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 12.24/3.90 (14) BOUNDS(1, 1) 12.24/3.90 (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 12.24/3.90 (16) CpxTRS 12.24/3.90 (17) SlicingProof [LOWER BOUND(ID), 0 ms] 12.24/3.90 (18) CpxTRS 12.24/3.90 (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 12.24/3.90 (20) typed CpxTrs 12.24/3.90 (21) OrderProof [LOWER BOUND(ID), 0 ms] 12.24/3.90 (22) typed CpxTrs 12.24/3.90 (23) RewriteLemmaProof [LOWER BOUND(ID), 282 ms] 12.24/3.90 (24) BEST 12.24/3.90 (25) proven lower bound 12.24/3.90 (26) LowerBoundPropagationProof [FINISHED, 0 ms] 12.24/3.90 (27) BOUNDS(n^1, INF) 12.24/3.90 (28) typed CpxTrs 12.24/3.90 (29) RewriteLemmaProof [LOWER BOUND(ID), 59 ms] 12.24/3.90 (30) BEST 12.24/3.90 (31) proven lower bound 12.24/3.90 (32) LowerBoundPropagationProof [FINISHED, 0 ms] 12.24/3.90 (33) BOUNDS(n^2, INF) 12.24/3.90 (34) typed CpxTrs 12.24/3.90 (35) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 12.24/3.90 (36) proven lower bound 12.24/3.90 (37) LowerBoundPropagationProof [FINISHED, 0 ms] 12.24/3.90 (38) BOUNDS(n^3, INF) 12.24/3.90 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (0) 12.24/3.90 Obligation: 12.24/3.90 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 12.24/3.90 12.24/3.90 12.24/3.90 The TRS R consists of the following rules: 12.24/3.90 12.24/3.90 app(nil, y) -> y 12.24/3.90 app(add(n, x), y) -> add(n, app(x, y)) 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 12.24/3.90 shuffle(nil) -> nil 12.24/3.90 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) 12.24/3.90 12.24/3.90 S is empty. 12.24/3.90 Rewrite Strategy: INNERMOST 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 12.24/3.90 Converted Cpx (relative) TRS to CDT 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (2) 12.24/3.90 Obligation: 12.24/3.90 Complexity Dependency Tuples Problem 12.24/3.90 12.24/3.90 Rules: 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 shuffle(nil) -> nil 12.24/3.90 shuffle(add(z0, z1)) -> add(z0, shuffle(reverse(z1))) 12.24/3.90 Tuples: 12.24/3.90 APP(nil, z0) -> c 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(nil) -> c2 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(nil) -> c4 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 S tuples: 12.24/3.90 APP(nil, z0) -> c 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(nil) -> c2 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(nil) -> c4 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 K tuples:none 12.24/3.90 Defined Rule Symbols: app_2, reverse_1, shuffle_1 12.24/3.90 12.24/3.90 Defined Pair Symbols: APP_2, REVERSE_1, SHUFFLE_1 12.24/3.90 12.24/3.90 Compound Symbols: c, c1_1, c2, c3_2, c4, c5_2 12.24/3.90 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 12.24/3.90 Removed 3 trailing nodes: 12.24/3.90 SHUFFLE(nil) -> c4 12.24/3.90 REVERSE(nil) -> c2 12.24/3.90 APP(nil, z0) -> c 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (4) 12.24/3.90 Obligation: 12.24/3.90 Complexity Dependency Tuples Problem 12.24/3.90 12.24/3.90 Rules: 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 shuffle(nil) -> nil 12.24/3.90 shuffle(add(z0, z1)) -> add(z0, shuffle(reverse(z1))) 12.24/3.90 Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 S tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 K tuples:none 12.24/3.90 Defined Rule Symbols: app_2, reverse_1, shuffle_1 12.24/3.90 12.24/3.90 Defined Pair Symbols: APP_2, REVERSE_1, SHUFFLE_1 12.24/3.90 12.24/3.90 Compound Symbols: c1_1, c3_2, c5_2 12.24/3.90 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 12.24/3.90 The following rules are not usable and were removed: 12.24/3.90 shuffle(nil) -> nil 12.24/3.90 shuffle(add(z0, z1)) -> add(z0, shuffle(reverse(z1))) 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (6) 12.24/3.90 Obligation: 12.24/3.90 Complexity Dependency Tuples Problem 12.24/3.90 12.24/3.90 Rules: 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 S tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 K tuples:none 12.24/3.90 Defined Rule Symbols: reverse_1, app_2 12.24/3.90 12.24/3.90 Defined Pair Symbols: APP_2, REVERSE_1, SHUFFLE_1 12.24/3.90 12.24/3.90 Compound Symbols: c1_1, c3_2, c5_2 12.24/3.90 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 12.24/3.90 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 We considered the (Usable) Rules: 12.24/3.90 reverse(nil) -> nil 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 And the Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 The order we found is given by the following interpretation: 12.24/3.90 12.24/3.90 Polynomial interpretation : 12.24/3.90 12.24/3.90 POL(APP(x_1, x_2)) = 0 12.24/3.90 POL(REVERSE(x_1)) = 0 12.24/3.90 POL(SHUFFLE(x_1)) = x_1 12.24/3.90 POL(add(x_1, x_2)) = [2] + x_1 + x_2 12.24/3.90 POL(app(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(c1(x_1)) = x_1 12.24/3.90 POL(c3(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(c5(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(nil) = 0 12.24/3.90 POL(reverse(x_1)) = x_1 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (8) 12.24/3.90 Obligation: 12.24/3.90 Complexity Dependency Tuples Problem 12.24/3.90 12.24/3.90 Rules: 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 S tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 K tuples: 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 Defined Rule Symbols: reverse_1, app_2 12.24/3.90 12.24/3.90 Defined Pair Symbols: APP_2, REVERSE_1, SHUFFLE_1 12.24/3.90 12.24/3.90 Compound Symbols: c1_1, c3_2, c5_2 12.24/3.90 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 12.24/3.90 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 We considered the (Usable) Rules: 12.24/3.90 reverse(nil) -> nil 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 And the Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 The order we found is given by the following interpretation: 12.24/3.90 12.24/3.90 Polynomial interpretation : 12.24/3.90 12.24/3.90 POL(APP(x_1, x_2)) = 0 12.24/3.90 POL(REVERSE(x_1)) = x_1 12.24/3.90 POL(SHUFFLE(x_1)) = x_1^2 12.24/3.90 POL(add(x_1, x_2)) = [1] + x_2 12.24/3.90 POL(app(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(c1(x_1)) = x_1 12.24/3.90 POL(c3(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(c5(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(nil) = 0 12.24/3.90 POL(reverse(x_1)) = x_1 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (10) 12.24/3.90 Obligation: 12.24/3.90 Complexity Dependency Tuples Problem 12.24/3.90 12.24/3.90 Rules: 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 S tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 K tuples: 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 Defined Rule Symbols: reverse_1, app_2 12.24/3.90 12.24/3.90 Defined Pair Symbols: APP_2, REVERSE_1, SHUFFLE_1 12.24/3.90 12.24/3.90 Compound Symbols: c1_1, c3_2, c5_2 12.24/3.90 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3))) 12.24/3.90 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 We considered the (Usable) Rules: 12.24/3.90 reverse(nil) -> nil 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 And the Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 The order we found is given by the following interpretation: 12.24/3.90 12.24/3.90 Polynomial interpretation : 12.24/3.90 12.24/3.90 POL(APP(x_1, x_2)) = x_1 + x_1*x_2^2 12.24/3.90 POL(REVERSE(x_1)) = x_1^2 12.24/3.90 POL(SHUFFLE(x_1)) = x_1^3 12.24/3.90 POL(add(x_1, x_2)) = [1] + x_2 12.24/3.90 POL(app(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(c1(x_1)) = x_1 12.24/3.90 POL(c3(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(c5(x_1, x_2)) = x_1 + x_2 12.24/3.90 POL(nil) = 0 12.24/3.90 POL(reverse(x_1)) = x_1 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (12) 12.24/3.90 Obligation: 12.24/3.90 Complexity Dependency Tuples Problem 12.24/3.90 12.24/3.90 Rules: 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil)) 12.24/3.90 app(nil, z0) -> z0 12.24/3.90 app(add(z0, z1), z2) -> add(z0, app(z1, z2)) 12.24/3.90 Tuples: 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 S tuples:none 12.24/3.90 K tuples: 12.24/3.90 SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1)) 12.24/3.90 REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1)) 12.24/3.90 APP(add(z0, z1), z2) -> c1(APP(z1, z2)) 12.24/3.90 Defined Rule Symbols: reverse_1, app_2 12.24/3.90 12.24/3.90 Defined Pair Symbols: APP_2, REVERSE_1, SHUFFLE_1 12.24/3.90 12.24/3.90 Compound Symbols: c1_1, c3_2, c5_2 12.24/3.90 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 12.24/3.90 The set S is empty 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (14) 12.24/3.90 BOUNDS(1, 1) 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (15) RenamingProof (BOTH BOUNDS(ID, ID)) 12.24/3.90 Renamed function symbols to avoid clashes with predefined symbol. 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (16) 12.24/3.90 Obligation: 12.24/3.90 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 12.24/3.90 12.24/3.90 12.24/3.90 The TRS R consists of the following rules: 12.24/3.90 12.24/3.90 app(nil, y) -> y 12.24/3.90 app(add(n, x), y) -> add(n, app(x, y)) 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 12.24/3.90 shuffle(nil) -> nil 12.24/3.90 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) 12.24/3.90 12.24/3.90 S is empty. 12.24/3.90 Rewrite Strategy: INNERMOST 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (17) SlicingProof (LOWER BOUND(ID)) 12.24/3.90 Sliced the following arguments: 12.24/3.90 add/0 12.24/3.90 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (18) 12.24/3.90 Obligation: 12.24/3.90 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 12.24/3.90 12.24/3.90 12.24/3.90 The TRS R consists of the following rules: 12.24/3.90 12.24/3.90 app(nil, y) -> y 12.24/3.90 app(add(x), y) -> add(app(x, y)) 12.24/3.90 reverse(nil) -> nil 12.24/3.90 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.90 shuffle(nil) -> nil 12.24/3.90 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.90 12.24/3.90 S is empty. 12.24/3.90 Rewrite Strategy: INNERMOST 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.90 (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 12.24/3.90 Infered types. 12.24/3.90 ---------------------------------------- 12.24/3.90 12.24/3.91 (20) 12.24/3.91 Obligation: 12.24/3.91 Innermost TRS: 12.24/3.91 Rules: 12.24/3.91 app(nil, y) -> y 12.24/3.91 app(add(x), y) -> add(app(x, y)) 12.24/3.91 reverse(nil) -> nil 12.24/3.91 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.91 shuffle(nil) -> nil 12.24/3.91 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.91 12.24/3.91 Types: 12.24/3.91 app :: nil:add -> nil:add -> nil:add 12.24/3.91 nil :: nil:add 12.24/3.91 add :: nil:add -> nil:add 12.24/3.91 reverse :: nil:add -> nil:add 12.24/3.91 shuffle :: nil:add -> nil:add 12.24/3.91 hole_nil:add1_0 :: nil:add 12.24/3.91 gen_nil:add2_0 :: Nat -> nil:add 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (21) OrderProof (LOWER BOUND(ID)) 12.24/3.91 Heuristically decided to analyse the following defined symbols: 12.24/3.91 app, reverse, shuffle 12.24/3.91 12.24/3.91 They will be analysed ascendingly in the following order: 12.24/3.91 app < reverse 12.24/3.91 reverse < shuffle 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (22) 12.24/3.91 Obligation: 12.24/3.91 Innermost TRS: 12.24/3.91 Rules: 12.24/3.91 app(nil, y) -> y 12.24/3.91 app(add(x), y) -> add(app(x, y)) 12.24/3.91 reverse(nil) -> nil 12.24/3.91 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.91 shuffle(nil) -> nil 12.24/3.91 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.91 12.24/3.91 Types: 12.24/3.91 app :: nil:add -> nil:add -> nil:add 12.24/3.91 nil :: nil:add 12.24/3.91 add :: nil:add -> nil:add 12.24/3.91 reverse :: nil:add -> nil:add 12.24/3.91 shuffle :: nil:add -> nil:add 12.24/3.91 hole_nil:add1_0 :: nil:add 12.24/3.91 gen_nil:add2_0 :: Nat -> nil:add 12.24/3.91 12.24/3.91 12.24/3.91 Generator Equations: 12.24/3.91 gen_nil:add2_0(0) <=> nil 12.24/3.91 gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x)) 12.24/3.91 12.24/3.91 12.24/3.91 The following defined symbols remain to be analysed: 12.24/3.91 app, reverse, shuffle 12.24/3.91 12.24/3.91 They will be analysed ascendingly in the following order: 12.24/3.91 app < reverse 12.24/3.91 reverse < shuffle 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (23) RewriteLemmaProof (LOWER BOUND(ID)) 12.24/3.91 Proved the following rewrite lemma: 12.24/3.91 app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0) 12.24/3.91 12.24/3.91 Induction Base: 12.24/3.91 app(gen_nil:add2_0(0), gen_nil:add2_0(b)) ->_R^Omega(1) 12.24/3.91 gen_nil:add2_0(b) 12.24/3.91 12.24/3.91 Induction Step: 12.24/3.91 app(gen_nil:add2_0(+(n4_0, 1)), gen_nil:add2_0(b)) ->_R^Omega(1) 12.24/3.91 add(app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b))) ->_IH 12.24/3.91 add(gen_nil:add2_0(+(b, c5_0))) 12.24/3.91 12.24/3.91 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (24) 12.24/3.91 Complex Obligation (BEST) 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (25) 12.24/3.91 Obligation: 12.24/3.91 Proved the lower bound n^1 for the following obligation: 12.24/3.91 12.24/3.91 Innermost TRS: 12.24/3.91 Rules: 12.24/3.91 app(nil, y) -> y 12.24/3.91 app(add(x), y) -> add(app(x, y)) 12.24/3.91 reverse(nil) -> nil 12.24/3.91 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.91 shuffle(nil) -> nil 12.24/3.91 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.91 12.24/3.91 Types: 12.24/3.91 app :: nil:add -> nil:add -> nil:add 12.24/3.91 nil :: nil:add 12.24/3.91 add :: nil:add -> nil:add 12.24/3.91 reverse :: nil:add -> nil:add 12.24/3.91 shuffle :: nil:add -> nil:add 12.24/3.91 hole_nil:add1_0 :: nil:add 12.24/3.91 gen_nil:add2_0 :: Nat -> nil:add 12.24/3.91 12.24/3.91 12.24/3.91 Generator Equations: 12.24/3.91 gen_nil:add2_0(0) <=> nil 12.24/3.91 gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x)) 12.24/3.91 12.24/3.91 12.24/3.91 The following defined symbols remain to be analysed: 12.24/3.91 app, reverse, shuffle 12.24/3.91 12.24/3.91 They will be analysed ascendingly in the following order: 12.24/3.91 app < reverse 12.24/3.91 reverse < shuffle 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (26) LowerBoundPropagationProof (FINISHED) 12.24/3.91 Propagated lower bound. 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (27) 12.24/3.91 BOUNDS(n^1, INF) 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (28) 12.24/3.91 Obligation: 12.24/3.91 Innermost TRS: 12.24/3.91 Rules: 12.24/3.91 app(nil, y) -> y 12.24/3.91 app(add(x), y) -> add(app(x, y)) 12.24/3.91 reverse(nil) -> nil 12.24/3.91 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.91 shuffle(nil) -> nil 12.24/3.91 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.91 12.24/3.91 Types: 12.24/3.91 app :: nil:add -> nil:add -> nil:add 12.24/3.91 nil :: nil:add 12.24/3.91 add :: nil:add -> nil:add 12.24/3.91 reverse :: nil:add -> nil:add 12.24/3.91 shuffle :: nil:add -> nil:add 12.24/3.91 hole_nil:add1_0 :: nil:add 12.24/3.91 gen_nil:add2_0 :: Nat -> nil:add 12.24/3.91 12.24/3.91 12.24/3.91 Lemmas: 12.24/3.91 app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0) 12.24/3.91 12.24/3.91 12.24/3.91 Generator Equations: 12.24/3.91 gen_nil:add2_0(0) <=> nil 12.24/3.91 gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x)) 12.24/3.91 12.24/3.91 12.24/3.91 The following defined symbols remain to be analysed: 12.24/3.91 reverse, shuffle 12.24/3.91 12.24/3.91 They will be analysed ascendingly in the following order: 12.24/3.91 reverse < shuffle 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (29) RewriteLemmaProof (LOWER BOUND(ID)) 12.24/3.91 Proved the following rewrite lemma: 12.24/3.91 reverse(gen_nil:add2_0(n487_0)) -> gen_nil:add2_0(n487_0), rt in Omega(1 + n487_0 + n487_0^2) 12.24/3.91 12.24/3.91 Induction Base: 12.24/3.91 reverse(gen_nil:add2_0(0)) ->_R^Omega(1) 12.24/3.91 nil 12.24/3.91 12.24/3.91 Induction Step: 12.24/3.91 reverse(gen_nil:add2_0(+(n487_0, 1))) ->_R^Omega(1) 12.24/3.91 app(reverse(gen_nil:add2_0(n487_0)), add(nil)) ->_IH 12.24/3.91 app(gen_nil:add2_0(c488_0), add(nil)) ->_L^Omega(1 + n487_0) 12.24/3.91 gen_nil:add2_0(+(n487_0, +(0, 1))) 12.24/3.91 12.24/3.91 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (30) 12.24/3.91 Complex Obligation (BEST) 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (31) 12.24/3.91 Obligation: 12.24/3.91 Proved the lower bound n^2 for the following obligation: 12.24/3.91 12.24/3.91 Innermost TRS: 12.24/3.91 Rules: 12.24/3.91 app(nil, y) -> y 12.24/3.91 app(add(x), y) -> add(app(x, y)) 12.24/3.91 reverse(nil) -> nil 12.24/3.91 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.91 shuffle(nil) -> nil 12.24/3.91 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.91 12.24/3.91 Types: 12.24/3.91 app :: nil:add -> nil:add -> nil:add 12.24/3.91 nil :: nil:add 12.24/3.91 add :: nil:add -> nil:add 12.24/3.91 reverse :: nil:add -> nil:add 12.24/3.91 shuffle :: nil:add -> nil:add 12.24/3.91 hole_nil:add1_0 :: nil:add 12.24/3.91 gen_nil:add2_0 :: Nat -> nil:add 12.24/3.91 12.24/3.91 12.24/3.91 Lemmas: 12.24/3.91 app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0) 12.24/3.91 12.24/3.91 12.24/3.91 Generator Equations: 12.24/3.91 gen_nil:add2_0(0) <=> nil 12.24/3.91 gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x)) 12.24/3.91 12.24/3.91 12.24/3.91 The following defined symbols remain to be analysed: 12.24/3.91 reverse, shuffle 12.24/3.91 12.24/3.91 They will be analysed ascendingly in the following order: 12.24/3.91 reverse < shuffle 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (32) LowerBoundPropagationProof (FINISHED) 12.24/3.91 Propagated lower bound. 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (33) 12.24/3.91 BOUNDS(n^2, INF) 12.24/3.91 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (34) 12.24/3.91 Obligation: 12.24/3.91 Innermost TRS: 12.24/3.91 Rules: 12.24/3.91 app(nil, y) -> y 12.24/3.91 app(add(x), y) -> add(app(x, y)) 12.24/3.91 reverse(nil) -> nil 12.24/3.91 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.91 shuffle(nil) -> nil 12.24/3.91 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.91 12.24/3.91 Types: 12.24/3.91 app :: nil:add -> nil:add -> nil:add 12.24/3.91 nil :: nil:add 12.24/3.91 add :: nil:add -> nil:add 12.24/3.91 reverse :: nil:add -> nil:add 12.24/3.91 shuffle :: nil:add -> nil:add 12.24/3.91 hole_nil:add1_0 :: nil:add 12.24/3.91 gen_nil:add2_0 :: Nat -> nil:add 12.24/3.91 12.24/3.91 12.24/3.91 Lemmas: 12.24/3.91 app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0) 12.24/3.91 reverse(gen_nil:add2_0(n487_0)) -> gen_nil:add2_0(n487_0), rt in Omega(1 + n487_0 + n487_0^2) 12.24/3.91 12.24/3.91 12.24/3.91 Generator Equations: 12.24/3.91 gen_nil:add2_0(0) <=> nil 12.24/3.91 gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x)) 12.24/3.91 12.24/3.91 12.24/3.91 The following defined symbols remain to be analysed: 12.24/3.91 shuffle 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (35) RewriteLemmaProof (LOWER BOUND(ID)) 12.24/3.91 Proved the following rewrite lemma: 12.24/3.91 shuffle(gen_nil:add2_0(n701_0)) -> gen_nil:add2_0(n701_0), rt in Omega(1 + n701_0 + n701_0^2 + n701_0^3) 12.24/3.91 12.24/3.91 Induction Base: 12.24/3.91 shuffle(gen_nil:add2_0(0)) ->_R^Omega(1) 12.24/3.91 nil 12.24/3.91 12.24/3.91 Induction Step: 12.24/3.91 shuffle(gen_nil:add2_0(+(n701_0, 1))) ->_R^Omega(1) 12.24/3.91 add(shuffle(reverse(gen_nil:add2_0(n701_0)))) ->_L^Omega(1 + n701_0 + n701_0^2) 12.24/3.91 add(shuffle(gen_nil:add2_0(n701_0))) ->_IH 12.24/3.91 add(gen_nil:add2_0(c702_0)) 12.24/3.91 12.24/3.91 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (36) 12.24/3.91 Obligation: 12.24/3.91 Proved the lower bound n^3 for the following obligation: 12.24/3.91 12.24/3.91 Innermost TRS: 12.24/3.91 Rules: 12.24/3.91 app(nil, y) -> y 12.24/3.91 app(add(x), y) -> add(app(x, y)) 12.24/3.91 reverse(nil) -> nil 12.24/3.91 reverse(add(x)) -> app(reverse(x), add(nil)) 12.24/3.91 shuffle(nil) -> nil 12.24/3.91 shuffle(add(x)) -> add(shuffle(reverse(x))) 12.24/3.91 12.24/3.91 Types: 12.24/3.91 app :: nil:add -> nil:add -> nil:add 12.24/3.91 nil :: nil:add 12.24/3.91 add :: nil:add -> nil:add 12.24/3.91 reverse :: nil:add -> nil:add 12.24/3.91 shuffle :: nil:add -> nil:add 12.24/3.91 hole_nil:add1_0 :: nil:add 12.24/3.91 gen_nil:add2_0 :: Nat -> nil:add 12.24/3.91 12.24/3.91 12.24/3.91 Lemmas: 12.24/3.91 app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0) 12.24/3.91 reverse(gen_nil:add2_0(n487_0)) -> gen_nil:add2_0(n487_0), rt in Omega(1 + n487_0 + n487_0^2) 12.24/3.91 12.24/3.91 12.24/3.91 Generator Equations: 12.24/3.91 gen_nil:add2_0(0) <=> nil 12.24/3.91 gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x)) 12.24/3.91 12.24/3.91 12.24/3.91 The following defined symbols remain to be analysed: 12.24/3.91 shuffle 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (37) LowerBoundPropagationProof (FINISHED) 12.24/3.91 Propagated lower bound. 12.24/3.91 ---------------------------------------- 12.24/3.91 12.24/3.91 (38) 12.24/3.91 BOUNDS(n^3, INF) 12.24/3.94 EOF