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