325.11/291.46 WORST_CASE(Omega(n^1), O(n^2)) 325.11/291.47 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 325.11/291.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 325.11/291.47 325.11/291.47 325.11/291.47 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 325.11/291.47 325.11/291.47 (0) CpxTRS 325.11/291.47 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 3 ms] 325.11/291.47 (2) CdtProblem 325.11/291.47 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 325.11/291.47 (4) CdtProblem 325.11/291.47 (5) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 108 ms] 325.11/291.47 (6) CdtProblem 325.11/291.47 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 67 ms] 325.11/291.47 (8) CdtProblem 325.11/291.47 (9) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 325.11/291.47 (10) CdtProblem 325.11/291.47 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 73 ms] 325.11/291.47 (12) CdtProblem 325.11/291.47 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 325.11/291.47 (14) BOUNDS(1, 1) 325.11/291.47 (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 325.11/291.47 (16) CpxTRS 325.11/291.47 (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 325.11/291.47 (18) typed CpxTrs 325.11/291.47 (19) OrderProof [LOWER BOUND(ID), 0 ms] 325.11/291.47 (20) typed CpxTrs 325.11/291.47 (21) RewriteLemmaProof [LOWER BOUND(ID), 457 ms] 325.11/291.47 (22) BEST 325.11/291.47 (23) proven lower bound 325.11/291.47 (24) LowerBoundPropagationProof [FINISHED, 0 ms] 325.11/291.47 (25) BOUNDS(n^1, INF) 325.11/291.47 (26) typed CpxTrs 325.11/291.47 (27) RewriteLemmaProof [LOWER BOUND(ID), 361 ms] 325.11/291.47 (28) BOUNDS(1, INF) 325.11/291.47 325.11/291.47 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (0) 325.11/291.47 Obligation: 325.11/291.47 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 325.11/291.47 325.11/291.47 325.11/291.47 The TRS R consists of the following rules: 325.11/291.47 325.11/291.47 sort(nil) -> nil 325.11/291.47 sort(cons(x, y)) -> insert(x, sort(y)) 325.11/291.47 insert(x, nil) -> cons(x, nil) 325.11/291.47 insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v) 325.11/291.47 choose(x, cons(v, w), y, 0) -> cons(x, cons(v, w)) 325.11/291.47 choose(x, cons(v, w), 0, s(z)) -> cons(v, insert(x, w)) 325.11/291.47 choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z) 325.11/291.47 325.11/291.47 S is empty. 325.11/291.47 Rewrite Strategy: INNERMOST 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 325.11/291.47 Converted Cpx (relative) TRS to CDT 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (2) 325.11/291.47 Obligation: 325.11/291.47 Complexity Dependency Tuples Problem 325.11/291.47 325.11/291.47 Rules: 325.11/291.47 sort(nil) -> nil 325.11/291.47 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.47 insert(z0, nil) -> cons(z0, nil) 325.11/291.47 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.47 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.47 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.47 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.47 Tuples: 325.11/291.47 SORT(nil) -> c 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 INSERT(z0, nil) -> c2 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), z3, 0) -> c4 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 S tuples: 325.11/291.47 SORT(nil) -> c 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 INSERT(z0, nil) -> c2 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), z3, 0) -> c4 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 K tuples:none 325.11/291.47 Defined Rule Symbols: sort_1, insert_2, choose_4 325.11/291.47 325.11/291.47 Defined Pair Symbols: SORT_1, INSERT_2, CHOOSE_4 325.11/291.47 325.11/291.47 Compound Symbols: c, c1_2, c2, c3_1, c4, c5_1, c6_1 325.11/291.47 325.11/291.47 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 325.11/291.47 Removed 3 trailing nodes: 325.11/291.47 SORT(nil) -> c 325.11/291.47 CHOOSE(z0, cons(z1, z2), z3, 0) -> c4 325.11/291.47 INSERT(z0, nil) -> c2 325.11/291.47 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (4) 325.11/291.47 Obligation: 325.11/291.47 Complexity Dependency Tuples Problem 325.11/291.47 325.11/291.47 Rules: 325.11/291.47 sort(nil) -> nil 325.11/291.47 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.47 insert(z0, nil) -> cons(z0, nil) 325.11/291.47 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.47 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.47 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.47 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.47 Tuples: 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 S tuples: 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 K tuples:none 325.11/291.47 Defined Rule Symbols: sort_1, insert_2, choose_4 325.11/291.47 325.11/291.47 Defined Pair Symbols: SORT_1, INSERT_2, CHOOSE_4 325.11/291.47 325.11/291.47 Compound Symbols: c1_2, c3_1, c5_1, c6_1 325.11/291.47 325.11/291.47 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (5) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 325.11/291.47 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 We considered the (Usable) Rules:none 325.11/291.47 And the Tuples: 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 The order we found is given by the following interpretation: 325.11/291.47 325.11/291.47 Polynomial interpretation : 325.11/291.47 325.11/291.47 POL(0) = [1] 325.11/291.47 POL(CHOOSE(x_1, x_2, x_3, x_4)) = x_1 325.11/291.47 POL(INSERT(x_1, x_2)) = x_1 325.11/291.47 POL(SORT(x_1)) = x_1 325.11/291.47 POL(c1(x_1, x_2)) = x_1 + x_2 325.11/291.47 POL(c3(x_1)) = x_1 325.11/291.47 POL(c5(x_1)) = x_1 325.11/291.47 POL(c6(x_1)) = x_1 325.11/291.47 POL(choose(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_2 325.11/291.47 POL(cons(x_1, x_2)) = [1] + x_1 + x_2 325.11/291.47 POL(insert(x_1, x_2)) = [1] + x_1 + x_2 325.11/291.47 POL(nil) = [1] 325.11/291.47 POL(s(x_1)) = [1] + x_1 325.11/291.47 POL(sort(x_1)) = [1] + x_1 325.11/291.47 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (6) 325.11/291.47 Obligation: 325.11/291.47 Complexity Dependency Tuples Problem 325.11/291.47 325.11/291.47 Rules: 325.11/291.47 sort(nil) -> nil 325.11/291.47 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.47 insert(z0, nil) -> cons(z0, nil) 325.11/291.47 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.47 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.47 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.47 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.47 Tuples: 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 S tuples: 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 K tuples: 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 Defined Rule Symbols: sort_1, insert_2, choose_4 325.11/291.47 325.11/291.47 Defined Pair Symbols: SORT_1, INSERT_2, CHOOSE_4 325.11/291.47 325.11/291.47 Compound Symbols: c1_2, c3_1, c5_1, c6_1 325.11/291.47 325.11/291.47 325.11/291.47 ---------------------------------------- 325.11/291.47 325.11/291.47 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 325.11/291.47 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 We considered the (Usable) Rules: 325.11/291.47 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.47 sort(nil) -> nil 325.11/291.47 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.47 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.47 insert(z0, nil) -> cons(z0, nil) 325.11/291.47 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.47 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.47 And the Tuples: 325.11/291.47 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.47 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.47 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.47 The order we found is given by the following interpretation: 325.11/291.47 325.11/291.47 Polynomial interpretation : 325.11/291.47 325.11/291.47 POL(0) = 0 325.11/291.47 POL(CHOOSE(x_1, x_2, x_3, x_4)) = [2]x_2 325.11/291.47 POL(INSERT(x_1, x_2)) = [2]x_2 325.11/291.47 POL(SORT(x_1)) = [2]x_1^2 325.11/291.48 POL(c1(x_1, x_2)) = x_1 + x_2 325.11/291.48 POL(c3(x_1)) = x_1 325.11/291.48 POL(c5(x_1)) = x_1 325.11/291.48 POL(c6(x_1)) = x_1 325.11/291.48 POL(choose(x_1, x_2, x_3, x_4)) = [1] + x_2 325.11/291.48 POL(cons(x_1, x_2)) = [1] + x_2 325.11/291.48 POL(insert(x_1, x_2)) = [1] + x_2 325.11/291.48 POL(nil) = 0 325.11/291.48 POL(s(x_1)) = 0 325.11/291.48 POL(sort(x_1)) = x_1 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (8) 325.11/291.48 Obligation: 325.11/291.48 Complexity Dependency Tuples Problem 325.11/291.48 325.11/291.48 Rules: 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.48 insert(z0, nil) -> cons(z0, nil) 325.11/291.48 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.48 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.48 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.48 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.48 Tuples: 325.11/291.48 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 S tuples: 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 K tuples: 325.11/291.48 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 Defined Rule Symbols: sort_1, insert_2, choose_4 325.11/291.48 325.11/291.48 Defined Pair Symbols: SORT_1, INSERT_2, CHOOSE_4 325.11/291.48 325.11/291.48 Compound Symbols: c1_2, c3_1, c5_1, c6_1 325.11/291.48 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (9) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 325.11/291.48 The following tuples could be moved from S to K by knowledge propagation: 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (10) 325.11/291.48 Obligation: 325.11/291.48 Complexity Dependency Tuples Problem 325.11/291.48 325.11/291.48 Rules: 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.48 insert(z0, nil) -> cons(z0, nil) 325.11/291.48 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.48 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.48 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.48 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.48 Tuples: 325.11/291.48 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 S tuples: 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 K tuples: 325.11/291.48 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 Defined Rule Symbols: sort_1, insert_2, choose_4 325.11/291.48 325.11/291.48 Defined Pair Symbols: SORT_1, INSERT_2, CHOOSE_4 325.11/291.48 325.11/291.48 Compound Symbols: c1_2, c3_1, c5_1, c6_1 325.11/291.48 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 325.11/291.48 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 We considered the (Usable) Rules: 325.11/291.48 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.48 sort(nil) -> nil 325.11/291.48 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.48 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.48 insert(z0, nil) -> cons(z0, nil) 325.11/291.48 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.48 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.48 And the Tuples: 325.11/291.48 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 The order we found is given by the following interpretation: 325.11/291.48 325.11/291.48 Polynomial interpretation : 325.11/291.48 325.11/291.48 POL(0) = 0 325.11/291.48 POL(CHOOSE(x_1, x_2, x_3, x_4)) = [2]x_3 + x_1*x_2 325.11/291.48 POL(INSERT(x_1, x_2)) = [2]x_1 + x_1*x_2 325.11/291.48 POL(SORT(x_1)) = [2]x_1^2 325.11/291.48 POL(c1(x_1, x_2)) = x_1 + x_2 325.11/291.48 POL(c3(x_1)) = x_1 325.11/291.48 POL(c5(x_1)) = x_1 325.11/291.48 POL(c6(x_1)) = x_1 325.11/291.48 POL(choose(x_1, x_2, x_3, x_4)) = [2] + x_1 + x_2 325.11/291.48 POL(cons(x_1, x_2)) = [2] + x_1 + x_2 325.11/291.48 POL(insert(x_1, x_2)) = [2] + x_1 + x_2 325.11/291.48 POL(nil) = 0 325.11/291.48 POL(s(x_1)) = [2] + x_1 325.11/291.48 POL(sort(x_1)) = [2] + x_1 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (12) 325.11/291.48 Obligation: 325.11/291.48 Complexity Dependency Tuples Problem 325.11/291.48 325.11/291.48 Rules: 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(z0, z1)) -> insert(z0, sort(z1)) 325.11/291.48 insert(z0, nil) -> cons(z0, nil) 325.11/291.48 insert(z0, cons(z1, z2)) -> choose(z0, cons(z1, z2), z0, z1) 325.11/291.48 choose(z0, cons(z1, z2), z3, 0) -> cons(z0, cons(z1, z2)) 325.11/291.48 choose(z0, cons(z1, z2), 0, s(z3)) -> cons(z1, insert(z0, z2)) 325.11/291.48 choose(z0, cons(z1, z2), s(z3), s(z4)) -> choose(z0, cons(z1, z2), z3, z4) 325.11/291.48 Tuples: 325.11/291.48 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 S tuples:none 325.11/291.48 K tuples: 325.11/291.48 SORT(cons(z0, z1)) -> c1(INSERT(z0, sort(z1)), SORT(z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), 0, s(z3)) -> c5(INSERT(z0, z2)) 325.11/291.48 INSERT(z0, cons(z1, z2)) -> c3(CHOOSE(z0, cons(z1, z2), z0, z1)) 325.11/291.48 CHOOSE(z0, cons(z1, z2), s(z3), s(z4)) -> c6(CHOOSE(z0, cons(z1, z2), z3, z4)) 325.11/291.48 Defined Rule Symbols: sort_1, insert_2, choose_4 325.11/291.48 325.11/291.48 Defined Pair Symbols: SORT_1, INSERT_2, CHOOSE_4 325.11/291.48 325.11/291.48 Compound Symbols: c1_2, c3_1, c5_1, c6_1 325.11/291.48 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 325.11/291.48 The set S is empty 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (14) 325.11/291.48 BOUNDS(1, 1) 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (15) RenamingProof (BOTH BOUNDS(ID, ID)) 325.11/291.48 Renamed function symbols to avoid clashes with predefined symbol. 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (16) 325.11/291.48 Obligation: 325.11/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 325.11/291.48 325.11/291.48 325.11/291.48 The TRS R consists of the following rules: 325.11/291.48 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(x, y)) -> insert(x, sort(y)) 325.11/291.48 insert(x, nil) -> cons(x, nil) 325.11/291.48 insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v) 325.11/291.48 choose(x, cons(v, w), y, 0') -> cons(x, cons(v, w)) 325.11/291.48 choose(x, cons(v, w), 0', s(z)) -> cons(v, insert(x, w)) 325.11/291.48 choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z) 325.11/291.48 325.11/291.48 S is empty. 325.11/291.48 Rewrite Strategy: INNERMOST 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 325.11/291.48 Infered types. 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (18) 325.11/291.48 Obligation: 325.11/291.48 Innermost TRS: 325.11/291.48 Rules: 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(x, y)) -> insert(x, sort(y)) 325.11/291.48 insert(x, nil) -> cons(x, nil) 325.11/291.48 insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v) 325.11/291.48 choose(x, cons(v, w), y, 0') -> cons(x, cons(v, w)) 325.11/291.48 choose(x, cons(v, w), 0', s(z)) -> cons(v, insert(x, w)) 325.11/291.48 choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z) 325.11/291.48 325.11/291.48 Types: 325.11/291.48 sort :: nil:cons -> nil:cons 325.11/291.48 nil :: nil:cons 325.11/291.48 cons :: 0':s -> nil:cons -> nil:cons 325.11/291.48 insert :: 0':s -> nil:cons -> nil:cons 325.11/291.48 choose :: 0':s -> nil:cons -> 0':s -> 0':s -> nil:cons 325.11/291.48 0' :: 0':s 325.11/291.48 s :: 0':s -> 0':s 325.11/291.48 hole_nil:cons1_0 :: nil:cons 325.11/291.48 hole_0':s2_0 :: 0':s 325.11/291.48 gen_nil:cons3_0 :: Nat -> nil:cons 325.11/291.48 gen_0':s4_0 :: Nat -> 0':s 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (19) OrderProof (LOWER BOUND(ID)) 325.11/291.48 Heuristically decided to analyse the following defined symbols: 325.11/291.48 sort, insert, choose 325.11/291.48 325.11/291.48 They will be analysed ascendingly in the following order: 325.11/291.48 insert < sort 325.11/291.48 insert = choose 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (20) 325.11/291.48 Obligation: 325.11/291.48 Innermost TRS: 325.11/291.48 Rules: 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(x, y)) -> insert(x, sort(y)) 325.11/291.48 insert(x, nil) -> cons(x, nil) 325.11/291.48 insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v) 325.11/291.48 choose(x, cons(v, w), y, 0') -> cons(x, cons(v, w)) 325.11/291.48 choose(x, cons(v, w), 0', s(z)) -> cons(v, insert(x, w)) 325.11/291.48 choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z) 325.11/291.48 325.11/291.48 Types: 325.11/291.48 sort :: nil:cons -> nil:cons 325.11/291.48 nil :: nil:cons 325.11/291.48 cons :: 0':s -> nil:cons -> nil:cons 325.11/291.48 insert :: 0':s -> nil:cons -> nil:cons 325.11/291.48 choose :: 0':s -> nil:cons -> 0':s -> 0':s -> nil:cons 325.11/291.48 0' :: 0':s 325.11/291.48 s :: 0':s -> 0':s 325.11/291.48 hole_nil:cons1_0 :: nil:cons 325.11/291.48 hole_0':s2_0 :: 0':s 325.11/291.48 gen_nil:cons3_0 :: Nat -> nil:cons 325.11/291.48 gen_0':s4_0 :: Nat -> 0':s 325.11/291.48 325.11/291.48 325.11/291.48 Generator Equations: 325.11/291.48 gen_nil:cons3_0(0) <=> nil 325.11/291.48 gen_nil:cons3_0(+(x, 1)) <=> cons(0', gen_nil:cons3_0(x)) 325.11/291.48 gen_0':s4_0(0) <=> 0' 325.11/291.48 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 325.11/291.48 325.11/291.48 325.11/291.48 The following defined symbols remain to be analysed: 325.11/291.48 choose, sort, insert 325.11/291.48 325.11/291.48 They will be analysed ascendingly in the following order: 325.11/291.48 insert < sort 325.11/291.48 insert = choose 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (21) RewriteLemmaProof (LOWER BOUND(ID)) 325.11/291.48 Proved the following rewrite lemma: 325.11/291.48 choose(gen_0':s4_0(a), gen_nil:cons3_0(1), gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> cons(gen_0':s4_0(a), gen_nil:cons3_0(1)), rt in Omega(1 + n6_0) 325.11/291.48 325.11/291.48 Induction Base: 325.11/291.48 choose(gen_0':s4_0(a), gen_nil:cons3_0(1), gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 325.11/291.48 cons(gen_0':s4_0(a), cons(0', gen_nil:cons3_0(0))) 325.11/291.48 325.11/291.48 Induction Step: 325.11/291.48 choose(gen_0':s4_0(a), gen_nil:cons3_0(1), gen_0':s4_0(+(n6_0, 1)), gen_0':s4_0(+(n6_0, 1))) ->_R^Omega(1) 325.11/291.48 choose(gen_0':s4_0(a), cons(0', gen_nil:cons3_0(0)), gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) ->_IH 325.11/291.48 cons(gen_0':s4_0(a), gen_nil:cons3_0(1)) 325.11/291.48 325.11/291.48 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (22) 325.11/291.48 Complex Obligation (BEST) 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (23) 325.11/291.48 Obligation: 325.11/291.48 Proved the lower bound n^1 for the following obligation: 325.11/291.48 325.11/291.48 Innermost TRS: 325.11/291.48 Rules: 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(x, y)) -> insert(x, sort(y)) 325.11/291.48 insert(x, nil) -> cons(x, nil) 325.11/291.48 insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v) 325.11/291.48 choose(x, cons(v, w), y, 0') -> cons(x, cons(v, w)) 325.11/291.48 choose(x, cons(v, w), 0', s(z)) -> cons(v, insert(x, w)) 325.11/291.48 choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z) 325.11/291.48 325.11/291.48 Types: 325.11/291.48 sort :: nil:cons -> nil:cons 325.11/291.48 nil :: nil:cons 325.11/291.48 cons :: 0':s -> nil:cons -> nil:cons 325.11/291.48 insert :: 0':s -> nil:cons -> nil:cons 325.11/291.48 choose :: 0':s -> nil:cons -> 0':s -> 0':s -> nil:cons 325.11/291.48 0' :: 0':s 325.11/291.48 s :: 0':s -> 0':s 325.11/291.48 hole_nil:cons1_0 :: nil:cons 325.11/291.48 hole_0':s2_0 :: 0':s 325.11/291.48 gen_nil:cons3_0 :: Nat -> nil:cons 325.11/291.48 gen_0':s4_0 :: Nat -> 0':s 325.11/291.48 325.11/291.48 325.11/291.48 Generator Equations: 325.11/291.48 gen_nil:cons3_0(0) <=> nil 325.11/291.48 gen_nil:cons3_0(+(x, 1)) <=> cons(0', gen_nil:cons3_0(x)) 325.11/291.48 gen_0':s4_0(0) <=> 0' 325.11/291.48 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 325.11/291.48 325.11/291.48 325.11/291.48 The following defined symbols remain to be analysed: 325.11/291.48 choose, sort, insert 325.11/291.48 325.11/291.48 They will be analysed ascendingly in the following order: 325.11/291.48 insert < sort 325.11/291.48 insert = choose 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (24) LowerBoundPropagationProof (FINISHED) 325.11/291.48 Propagated lower bound. 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (25) 325.11/291.48 BOUNDS(n^1, INF) 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (26) 325.11/291.48 Obligation: 325.11/291.48 Innermost TRS: 325.11/291.48 Rules: 325.11/291.48 sort(nil) -> nil 325.11/291.48 sort(cons(x, y)) -> insert(x, sort(y)) 325.11/291.48 insert(x, nil) -> cons(x, nil) 325.11/291.48 insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v) 325.11/291.48 choose(x, cons(v, w), y, 0') -> cons(x, cons(v, w)) 325.11/291.48 choose(x, cons(v, w), 0', s(z)) -> cons(v, insert(x, w)) 325.11/291.48 choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z) 325.11/291.48 325.11/291.48 Types: 325.11/291.48 sort :: nil:cons -> nil:cons 325.11/291.48 nil :: nil:cons 325.11/291.48 cons :: 0':s -> nil:cons -> nil:cons 325.11/291.48 insert :: 0':s -> nil:cons -> nil:cons 325.11/291.48 choose :: 0':s -> nil:cons -> 0':s -> 0':s -> nil:cons 325.11/291.48 0' :: 0':s 325.11/291.48 s :: 0':s -> 0':s 325.11/291.48 hole_nil:cons1_0 :: nil:cons 325.11/291.48 hole_0':s2_0 :: 0':s 325.11/291.48 gen_nil:cons3_0 :: Nat -> nil:cons 325.11/291.48 gen_0':s4_0 :: Nat -> 0':s 325.11/291.48 325.11/291.48 325.11/291.48 Lemmas: 325.11/291.48 choose(gen_0':s4_0(a), gen_nil:cons3_0(1), gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> cons(gen_0':s4_0(a), gen_nil:cons3_0(1)), rt in Omega(1 + n6_0) 325.11/291.48 325.11/291.48 325.11/291.48 Generator Equations: 325.11/291.48 gen_nil:cons3_0(0) <=> nil 325.11/291.48 gen_nil:cons3_0(+(x, 1)) <=> cons(0', gen_nil:cons3_0(x)) 325.11/291.48 gen_0':s4_0(0) <=> 0' 325.11/291.48 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 325.11/291.48 325.11/291.48 325.11/291.48 The following defined symbols remain to be analysed: 325.11/291.48 insert, sort 325.11/291.48 325.11/291.48 They will be analysed ascendingly in the following order: 325.11/291.48 insert < sort 325.11/291.48 insert = choose 325.11/291.48 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (27) RewriteLemmaProof (LOWER BOUND(ID)) 325.11/291.48 Proved the following rewrite lemma: 325.11/291.48 sort(gen_nil:cons3_0(n3137_0)) -> *5_0, rt in Omega(n3137_0) 325.11/291.48 325.11/291.48 Induction Base: 325.11/291.48 sort(gen_nil:cons3_0(0)) 325.11/291.48 325.11/291.48 Induction Step: 325.11/291.48 sort(gen_nil:cons3_0(+(n3137_0, 1))) ->_R^Omega(1) 325.11/291.48 insert(0', sort(gen_nil:cons3_0(n3137_0))) ->_IH 325.11/291.48 insert(0', *5_0) 325.11/291.48 325.11/291.48 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 325.11/291.48 ---------------------------------------- 325.11/291.48 325.11/291.48 (28) 325.11/291.48 BOUNDS(1, INF) 325.21/291.51 EOF