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