325.20/291.51 WORST_CASE(Omega(n^1), O(n^2)) 325.20/291.52 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 325.20/291.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 325.20/291.52 325.20/291.52 325.20/291.52 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 325.20/291.52 325.20/291.52 (0) CpxTRS 325.20/291.52 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 325.20/291.52 (2) CpxTRS 325.20/291.52 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 325.20/291.52 (4) CdtProblem 325.20/291.52 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 325.20/291.52 (6) CdtProblem 325.20/291.52 (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 325.20/291.52 (8) CdtProblem 325.20/291.52 (9) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 325.20/291.52 (10) CdtProblem 325.20/291.52 (11) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 325.20/291.52 (12) CdtProblem 325.20/291.52 (13) CdtInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms] 325.20/291.52 (14) CdtProblem 325.20/291.52 (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 10 ms] 325.20/291.52 (16) CdtProblem 325.20/291.52 (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 44 ms] 325.20/291.52 (18) CdtProblem 325.20/291.52 (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 42 ms] 325.20/291.52 (20) CdtProblem 325.20/291.52 (21) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 325.20/291.52 (22) BOUNDS(1, 1) 325.20/291.52 (23) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 325.20/291.52 (24) TRS for Loop Detection 325.20/291.52 (25) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 325.20/291.52 (26) BEST 325.20/291.52 (27) proven lower bound 325.20/291.52 (28) LowerBoundPropagationProof [FINISHED, 0 ms] 325.20/291.52 (29) BOUNDS(n^1, INF) 325.20/291.52 (30) TRS for Loop Detection 325.20/291.52 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (0) 325.20/291.52 Obligation: 325.20/291.52 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 325.20/291.52 325.20/291.52 325.20/291.52 The TRS R consists of the following rules: 325.20/291.52 325.20/291.52 r(xs, ys, zs, nil) -> xs 325.20/291.52 r(xs, nil, zs, cons(w, ws)) -> r(xs, xs, cons(succ(zero), zs), ws) 325.20/291.52 r(xs, cons(y, ys), nil, cons(w, ws)) -> r(xs, xs, cons(succ(zero), nil), ws) 325.20/291.52 r(xs, cons(y, ys), cons(z, zs), cons(w, ws)) -> r(ys, cons(y, ys), zs, cons(succ(zero), cons(w, ws))) 325.20/291.52 325.20/291.52 S is empty. 325.20/291.52 Rewrite Strategy: FULL 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 325.20/291.52 Converted rc-obligation to irc-obligation. 325.20/291.52 325.20/291.52 As the TRS does not nest defined symbols, we have rc = irc. 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (2) 325.20/291.52 Obligation: 325.20/291.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 325.20/291.52 325.20/291.52 325.20/291.52 The TRS R consists of the following rules: 325.20/291.52 325.20/291.52 r(xs, ys, zs, nil) -> xs 325.20/291.52 r(xs, nil, zs, cons(w, ws)) -> r(xs, xs, cons(succ(zero), zs), ws) 325.20/291.52 r(xs, cons(y, ys), nil, cons(w, ws)) -> r(xs, xs, cons(succ(zero), nil), ws) 325.20/291.52 r(xs, cons(y, ys), cons(z, zs), cons(w, ws)) -> r(ys, cons(y, ys), zs, cons(succ(zero), cons(w, ws))) 325.20/291.52 325.20/291.52 S is empty. 325.20/291.52 Rewrite Strategy: INNERMOST 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 325.20/291.52 Converted Cpx (relative) TRS to CDT 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (4) 325.20/291.52 Obligation: 325.20/291.52 Complexity Dependency Tuples Problem 325.20/291.52 325.20/291.52 Rules: 325.20/291.52 r(z0, z1, z2, nil) -> z0 325.20/291.52 r(z0, nil, z1, cons(z2, z3)) -> r(z0, z0, cons(succ(zero), z1), z3) 325.20/291.52 r(z0, cons(z1, z2), nil, cons(z3, z4)) -> r(z0, z0, cons(succ(zero), nil), z4) 325.20/291.52 r(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> r(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6))) 325.20/291.52 Tuples: 325.20/291.52 R(z0, z1, z2, nil) -> c 325.20/291.52 R(z0, nil, z1, cons(z2, z3)) -> c1(R(z0, z0, cons(succ(zero), z1), z3)) 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 S tuples: 325.20/291.52 R(z0, z1, z2, nil) -> c 325.20/291.52 R(z0, nil, z1, cons(z2, z3)) -> c1(R(z0, z0, cons(succ(zero), z1), z3)) 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 K tuples:none 325.20/291.52 Defined Rule Symbols: r_4 325.20/291.52 325.20/291.52 Defined Pair Symbols: R_4 325.20/291.52 325.20/291.52 Compound Symbols: c, c1_1, c2_1, c3_1 325.20/291.52 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 325.20/291.52 Removed 1 trailing nodes: 325.20/291.52 R(z0, z1, z2, nil) -> c 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (6) 325.20/291.52 Obligation: 325.20/291.52 Complexity Dependency Tuples Problem 325.20/291.52 325.20/291.52 Rules: 325.20/291.52 r(z0, z1, z2, nil) -> z0 325.20/291.52 r(z0, nil, z1, cons(z2, z3)) -> r(z0, z0, cons(succ(zero), z1), z3) 325.20/291.52 r(z0, cons(z1, z2), nil, cons(z3, z4)) -> r(z0, z0, cons(succ(zero), nil), z4) 325.20/291.52 r(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> r(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6))) 325.20/291.52 Tuples: 325.20/291.52 R(z0, nil, z1, cons(z2, z3)) -> c1(R(z0, z0, cons(succ(zero), z1), z3)) 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 S tuples: 325.20/291.52 R(z0, nil, z1, cons(z2, z3)) -> c1(R(z0, z0, cons(succ(zero), z1), z3)) 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 K tuples:none 325.20/291.52 Defined Rule Symbols: r_4 325.20/291.52 325.20/291.52 Defined Pair Symbols: R_4 325.20/291.52 325.20/291.52 Compound Symbols: c1_1, c2_1, c3_1 325.20/291.52 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 325.20/291.52 The following rules are not usable and were removed: 325.20/291.52 r(z0, z1, z2, nil) -> z0 325.20/291.52 r(z0, nil, z1, cons(z2, z3)) -> r(z0, z0, cons(succ(zero), z1), z3) 325.20/291.52 r(z0, cons(z1, z2), nil, cons(z3, z4)) -> r(z0, z0, cons(succ(zero), nil), z4) 325.20/291.52 r(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> r(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6))) 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (8) 325.20/291.52 Obligation: 325.20/291.52 Complexity Dependency Tuples Problem 325.20/291.52 325.20/291.52 Rules:none 325.20/291.52 Tuples: 325.20/291.52 R(z0, nil, z1, cons(z2, z3)) -> c1(R(z0, z0, cons(succ(zero), z1), z3)) 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 S tuples: 325.20/291.52 R(z0, nil, z1, cons(z2, z3)) -> c1(R(z0, z0, cons(succ(zero), z1), z3)) 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 K tuples:none 325.20/291.52 Defined Rule Symbols:none 325.20/291.52 325.20/291.52 Defined Pair Symbols: R_4 325.20/291.52 325.20/291.52 Compound Symbols: c1_1, c2_1, c3_1 325.20/291.52 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (9) CdtForwardInstantiationProof (BOTH BOUNDS(ID, ID)) 325.20/291.52 Use forward instantiation to replace R(z0, nil, z1, cons(z2, z3)) -> c1(R(z0, z0, cons(succ(zero), z1), z3)) by 325.20/291.52 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.52 R(cons(y1, y2), nil, z1, cons(z2, cons(y5, y6))) -> c1(R(cons(y1, y2), cons(y1, y2), cons(succ(zero), z1), cons(y5, y6))) 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (10) 325.20/291.52 Obligation: 325.20/291.52 Complexity Dependency Tuples Problem 325.20/291.52 325.20/291.52 Rules:none 325.20/291.52 Tuples: 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.52 R(cons(y1, y2), nil, z1, cons(z2, cons(y5, y6))) -> c1(R(cons(y1, y2), cons(y1, y2), cons(succ(zero), z1), cons(y5, y6))) 325.20/291.52 S tuples: 325.20/291.52 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.52 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.52 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.52 R(cons(y1, y2), nil, z1, cons(z2, cons(y5, y6))) -> c1(R(cons(y1, y2), cons(y1, y2), cons(succ(zero), z1), cons(y5, y6))) 325.20/291.52 K tuples:none 325.20/291.52 Defined Rule Symbols:none 325.20/291.52 325.20/291.52 Defined Pair Symbols: R_4 325.20/291.52 325.20/291.52 Compound Symbols: c2_1, c3_1, c1_1 325.20/291.52 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (11) CdtLeafRemovalProof (ComplexityIfPolyImplication) 325.20/291.52 Removed 1 leading nodes: 325.20/291.52 R(cons(y1, y2), nil, z1, cons(z2, cons(y5, y6))) -> c1(R(cons(y1, y2), cons(y1, y2), cons(succ(zero), z1), cons(y5, y6))) 325.20/291.52 325.20/291.52 ---------------------------------------- 325.20/291.52 325.20/291.52 (12) 325.20/291.52 Obligation: 325.20/291.52 Complexity Dependency Tuples Problem 325.20/291.52 325.20/291.52 Rules:none 325.20/291.52 Tuples: 325.20/291.53 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 S tuples: 325.20/291.53 R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 K tuples:none 325.20/291.53 Defined Rule Symbols:none 325.20/291.53 325.20/291.53 Defined Pair Symbols: R_4 325.20/291.53 325.20/291.53 Compound Symbols: c2_1, c3_1, c1_1 325.20/291.53 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (13) CdtInstantiationProof (BOTH BOUNDS(ID, ID)) 325.20/291.53 Use instantiation to replace R(z0, cons(z1, z2), nil, cons(z3, z4)) -> c2(R(z0, z0, cons(succ(zero), nil), z4)) by 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (14) 325.20/291.53 Obligation: 325.20/291.53 Complexity Dependency Tuples Problem 325.20/291.53 325.20/291.53 Rules:none 325.20/291.53 Tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 S tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 K tuples:none 325.20/291.53 Defined Rule Symbols:none 325.20/291.53 325.20/291.53 Defined Pair Symbols: R_4 325.20/291.53 325.20/291.53 Compound Symbols: c3_1, c1_1, c2_1 325.20/291.53 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 325.20/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 We considered the (Usable) Rules:none 325.20/291.53 And the Tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 The order we found is given by the following interpretation: 325.20/291.53 325.20/291.53 Polynomial interpretation : 325.20/291.53 325.20/291.53 POL(R(x_1, x_2, x_3, x_4)) = x_2 325.20/291.53 POL(c1(x_1)) = x_1 325.20/291.53 POL(c2(x_1)) = x_1 325.20/291.53 POL(c3(x_1)) = x_1 325.20/291.53 POL(cons(x_1, x_2)) = [1] + x_1 + x_2 325.20/291.53 POL(nil) = [1] 325.20/291.53 POL(succ(x_1)) = [1] + x_1 325.20/291.53 POL(zero) = [1] 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (16) 325.20/291.53 Obligation: 325.20/291.53 Complexity Dependency Tuples Problem 325.20/291.53 325.20/291.53 Rules:none 325.20/291.53 Tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 S tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 K tuples: 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 Defined Rule Symbols:none 325.20/291.53 325.20/291.53 Defined Pair Symbols: R_4 325.20/291.53 325.20/291.53 Compound Symbols: c3_1, c1_1, c2_1 325.20/291.53 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 325.20/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 We considered the (Usable) Rules:none 325.20/291.53 And the Tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 The order we found is given by the following interpretation: 325.20/291.53 325.20/291.53 Polynomial interpretation : 325.20/291.53 325.20/291.53 POL(R(x_1, x_2, x_3, x_4)) = [2]x_3 + [2]x_4 + [2]x_2*x_3 + x_2^2 325.20/291.53 POL(c1(x_1)) = x_1 325.20/291.53 POL(c2(x_1)) = x_1 325.20/291.53 POL(c3(x_1)) = x_1 325.20/291.53 POL(cons(x_1, x_2)) = [1] + x_2 325.20/291.53 POL(nil) = 0 325.20/291.53 POL(succ(x_1)) = 0 325.20/291.53 POL(zero) = 0 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (18) 325.20/291.53 Obligation: 325.20/291.53 Complexity Dependency Tuples Problem 325.20/291.53 325.20/291.53 Rules:none 325.20/291.53 Tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 S tuples: 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 K tuples: 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 Defined Rule Symbols:none 325.20/291.53 325.20/291.53 Defined Pair Symbols: R_4 325.20/291.53 325.20/291.53 Compound Symbols: c3_1, c1_1, c2_1 325.20/291.53 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 325.20/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 We considered the (Usable) Rules:none 325.20/291.53 And the Tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 The order we found is given by the following interpretation: 325.20/291.53 325.20/291.53 Polynomial interpretation : 325.20/291.53 325.20/291.53 POL(R(x_1, x_2, x_3, x_4)) = x_2 + [2]x_4 + [2]x_2*x_3 + x_2^2 325.20/291.53 POL(c1(x_1)) = x_1 325.20/291.53 POL(c2(x_1)) = x_1 325.20/291.53 POL(c3(x_1)) = x_1 325.20/291.53 POL(cons(x_1, x_2)) = [1] + x_1 + x_2 325.20/291.53 POL(nil) = 0 325.20/291.53 POL(succ(x_1)) = 0 325.20/291.53 POL(zero) = 0 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (20) 325.20/291.53 Obligation: 325.20/291.53 Complexity Dependency Tuples Problem 325.20/291.53 325.20/291.53 Rules:none 325.20/291.53 Tuples: 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 S tuples:none 325.20/291.53 K tuples: 325.20/291.53 R(x2, cons(x1, x2), nil, cons(succ(zero), cons(x5, x6))) -> c2(R(x2, x2, cons(succ(zero), nil), cons(x5, x6))) 325.20/291.53 R(z0, cons(z1, z2), cons(z3, z4), cons(z5, z6)) -> c3(R(z2, cons(z1, z2), z4, cons(succ(zero), cons(z5, z6)))) 325.20/291.53 R(nil, nil, z1, cons(z2, cons(y2, y3))) -> c1(R(nil, nil, cons(succ(zero), z1), cons(y2, y3))) 325.20/291.53 Defined Rule Symbols:none 325.20/291.53 325.20/291.53 Defined Pair Symbols: R_4 325.20/291.53 325.20/291.53 Compound Symbols: c3_1, c1_1, c2_1 325.20/291.53 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (21) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 325.20/291.53 The set S is empty 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (22) 325.20/291.53 BOUNDS(1, 1) 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (23) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 325.20/291.53 Transformed a relative TRS into a decreasing-loop problem. 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (24) 325.20/291.53 Obligation: 325.20/291.53 Analyzing the following TRS for decreasing loops: 325.20/291.53 325.20/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 325.20/291.53 325.20/291.53 325.20/291.53 The TRS R consists of the following rules: 325.20/291.53 325.20/291.53 r(xs, ys, zs, nil) -> xs 325.20/291.53 r(xs, nil, zs, cons(w, ws)) -> r(xs, xs, cons(succ(zero), zs), ws) 325.20/291.53 r(xs, cons(y, ys), nil, cons(w, ws)) -> r(xs, xs, cons(succ(zero), nil), ws) 325.20/291.53 r(xs, cons(y, ys), cons(z, zs), cons(w, ws)) -> r(ys, cons(y, ys), zs, cons(succ(zero), cons(w, ws))) 325.20/291.53 325.20/291.53 S is empty. 325.20/291.53 Rewrite Strategy: FULL 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (25) DecreasingLoopProof (LOWER BOUND(ID)) 325.20/291.53 The following loop(s) give(s) rise to the lower bound Omega(n^1): 325.20/291.53 325.20/291.53 The rewrite sequence 325.20/291.53 325.20/291.53 r(xs, cons(y, ys), cons(z, zs), cons(w, ws)) ->^+ r(ys, cons(y, ys), zs, cons(succ(zero), cons(w, ws))) 325.20/291.53 325.20/291.53 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 325.20/291.53 325.20/291.53 The pumping substitution is [zs / cons(z, zs)]. 325.20/291.53 325.20/291.53 The result substitution is [xs / ys, w / succ(zero), ws / cons(w, ws)]. 325.20/291.53 325.20/291.53 325.20/291.53 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (26) 325.20/291.53 Complex Obligation (BEST) 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (27) 325.20/291.53 Obligation: 325.20/291.53 Proved the lower bound n^1 for the following obligation: 325.20/291.53 325.20/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 325.20/291.53 325.20/291.53 325.20/291.53 The TRS R consists of the following rules: 325.20/291.53 325.20/291.53 r(xs, ys, zs, nil) -> xs 325.20/291.53 r(xs, nil, zs, cons(w, ws)) -> r(xs, xs, cons(succ(zero), zs), ws) 325.20/291.53 r(xs, cons(y, ys), nil, cons(w, ws)) -> r(xs, xs, cons(succ(zero), nil), ws) 325.20/291.53 r(xs, cons(y, ys), cons(z, zs), cons(w, ws)) -> r(ys, cons(y, ys), zs, cons(succ(zero), cons(w, ws))) 325.20/291.53 325.20/291.53 S is empty. 325.20/291.53 Rewrite Strategy: FULL 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (28) LowerBoundPropagationProof (FINISHED) 325.20/291.53 Propagated lower bound. 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (29) 325.20/291.53 BOUNDS(n^1, INF) 325.20/291.53 325.20/291.53 ---------------------------------------- 325.20/291.53 325.20/291.53 (30) 325.20/291.53 Obligation: 325.20/291.53 Analyzing the following TRS for decreasing loops: 325.20/291.53 325.20/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 325.20/291.53 325.20/291.53 325.20/291.53 The TRS R consists of the following rules: 325.20/291.53 325.20/291.53 r(xs, ys, zs, nil) -> xs 325.20/291.53 r(xs, nil, zs, cons(w, ws)) -> r(xs, xs, cons(succ(zero), zs), ws) 325.20/291.53 r(xs, cons(y, ys), nil, cons(w, ws)) -> r(xs, xs, cons(succ(zero), nil), ws) 325.20/291.53 r(xs, cons(y, ys), cons(z, zs), cons(w, ws)) -> r(ys, cons(y, ys), zs, cons(succ(zero), cons(w, ws))) 325.20/291.53 325.20/291.53 S is empty. 325.20/291.53 Rewrite Strategy: FULL 325.27/291.55 EOF