333.78/291.49 WORST_CASE(Omega(n^1), O(n^2)) 333.78/291.50 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 333.78/291.50 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 333.78/291.50 333.78/291.50 333.78/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.78/291.50 333.78/291.50 (0) CpxTRS 333.78/291.50 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 333.78/291.50 (2) CpxTRS 333.78/291.50 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 333.78/291.50 (4) CdtProblem 333.78/291.50 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 333.78/291.50 (6) CdtProblem 333.78/291.50 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 32 ms] 333.78/291.50 (8) CdtProblem 333.78/291.50 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 37 ms] 333.78/291.50 (10) CdtProblem 333.78/291.50 (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 333.78/291.50 (12) BOUNDS(1, 1) 333.78/291.50 (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 333.78/291.50 (14) TRS for Loop Detection 333.78/291.50 (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 333.78/291.50 (16) BEST 333.78/291.50 (17) proven lower bound 333.78/291.50 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 333.78/291.50 (19) BOUNDS(n^1, INF) 333.78/291.50 (20) TRS for Loop Detection 333.78/291.50 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (0) 333.78/291.50 Obligation: 333.78/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.78/291.50 333.78/291.50 333.78/291.50 The TRS R consists of the following rules: 333.78/291.50 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(x)) -> +(sum(x), s(x)) 333.78/291.50 +(x, 0) -> x 333.78/291.50 +(x, s(y)) -> s(+(x, y)) 333.78/291.50 333.78/291.50 S is empty. 333.78/291.50 Rewrite Strategy: FULL 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 333.78/291.50 Converted rc-obligation to irc-obligation. 333.78/291.50 333.78/291.50 The duplicating contexts are: 333.78/291.50 sum(s([])) 333.78/291.50 333.78/291.50 333.78/291.50 The defined contexts are: 333.78/291.50 +([], s(x1)) 333.78/291.50 +([], x1) 333.78/291.50 333.78/291.50 333.78/291.50 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (2) 333.78/291.50 Obligation: 333.78/291.50 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 333.78/291.50 333.78/291.50 333.78/291.50 The TRS R consists of the following rules: 333.78/291.50 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(x)) -> +(sum(x), s(x)) 333.78/291.50 +(x, 0) -> x 333.78/291.50 +(x, s(y)) -> s(+(x, y)) 333.78/291.50 333.78/291.50 S is empty. 333.78/291.50 Rewrite Strategy: INNERMOST 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 333.78/291.50 Converted Cpx (relative) TRS to CDT 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (4) 333.78/291.50 Obligation: 333.78/291.50 Complexity Dependency Tuples Problem 333.78/291.50 333.78/291.50 Rules: 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(z0)) -> +(sum(z0), s(z0)) 333.78/291.50 +(z0, 0) -> z0 333.78/291.50 +(z0, s(z1)) -> s(+(z0, z1)) 333.78/291.50 Tuples: 333.78/291.50 SUM(0) -> c 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, 0) -> c2 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 S tuples: 333.78/291.50 SUM(0) -> c 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, 0) -> c2 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 K tuples:none 333.78/291.50 Defined Rule Symbols: sum_1, +_2 333.78/291.50 333.78/291.50 Defined Pair Symbols: SUM_1, +'_2 333.78/291.50 333.78/291.50 Compound Symbols: c, c1_2, c2, c3_1 333.78/291.50 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 333.78/291.50 Removed 2 trailing nodes: 333.78/291.50 SUM(0) -> c 333.78/291.50 +'(z0, 0) -> c2 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (6) 333.78/291.50 Obligation: 333.78/291.50 Complexity Dependency Tuples Problem 333.78/291.50 333.78/291.50 Rules: 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(z0)) -> +(sum(z0), s(z0)) 333.78/291.50 +(z0, 0) -> z0 333.78/291.50 +(z0, s(z1)) -> s(+(z0, z1)) 333.78/291.50 Tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 S tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 K tuples:none 333.78/291.50 Defined Rule Symbols: sum_1, +_2 333.78/291.50 333.78/291.50 Defined Pair Symbols: SUM_1, +'_2 333.78/291.50 333.78/291.50 Compound Symbols: c1_2, c3_1 333.78/291.50 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 333.78/291.50 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 We considered the (Usable) Rules:none 333.78/291.50 And the Tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 The order we found is given by the following interpretation: 333.78/291.50 333.78/291.50 Polynomial interpretation : 333.78/291.50 333.78/291.50 POL(+(x_1, x_2)) = [1] + x_2 333.78/291.50 POL(+'(x_1, x_2)) = 0 333.78/291.50 POL(0) = [1] 333.78/291.50 POL(SUM(x_1)) = x_1 333.78/291.50 POL(c1(x_1, x_2)) = x_1 + x_2 333.78/291.50 POL(c3(x_1)) = x_1 333.78/291.50 POL(s(x_1)) = [1] + x_1 333.78/291.50 POL(sum(x_1)) = [1] + x_1 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (8) 333.78/291.50 Obligation: 333.78/291.50 Complexity Dependency Tuples Problem 333.78/291.50 333.78/291.50 Rules: 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(z0)) -> +(sum(z0), s(z0)) 333.78/291.50 +(z0, 0) -> z0 333.78/291.50 +(z0, s(z1)) -> s(+(z0, z1)) 333.78/291.50 Tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 S tuples: 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 K tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 Defined Rule Symbols: sum_1, +_2 333.78/291.50 333.78/291.50 Defined Pair Symbols: SUM_1, +'_2 333.78/291.50 333.78/291.50 Compound Symbols: c1_2, c3_1 333.78/291.50 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 333.78/291.50 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 We considered the (Usable) Rules:none 333.78/291.50 And the Tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 The order we found is given by the following interpretation: 333.78/291.50 333.78/291.50 Polynomial interpretation : 333.78/291.50 333.78/291.50 POL(+(x_1, x_2)) = [1] + x_2 + [2]x_2^2 333.78/291.50 POL(+'(x_1, x_2)) = x_2 333.78/291.50 POL(0) = 0 333.78/291.50 POL(SUM(x_1)) = x_1^2 333.78/291.50 POL(c1(x_1, x_2)) = x_1 + x_2 333.78/291.50 POL(c3(x_1)) = x_1 333.78/291.50 POL(s(x_1)) = [1] + x_1 333.78/291.50 POL(sum(x_1)) = [2] + [2]x_1 + [2]x_1^2 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (10) 333.78/291.50 Obligation: 333.78/291.50 Complexity Dependency Tuples Problem 333.78/291.50 333.78/291.50 Rules: 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(z0)) -> +(sum(z0), s(z0)) 333.78/291.50 +(z0, 0) -> z0 333.78/291.50 +(z0, s(z1)) -> s(+(z0, z1)) 333.78/291.50 Tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 S tuples:none 333.78/291.50 K tuples: 333.78/291.50 SUM(s(z0)) -> c1(+'(sum(z0), s(z0)), SUM(z0)) 333.78/291.50 +'(z0, s(z1)) -> c3(+'(z0, z1)) 333.78/291.50 Defined Rule Symbols: sum_1, +_2 333.78/291.50 333.78/291.50 Defined Pair Symbols: SUM_1, +'_2 333.78/291.50 333.78/291.50 Compound Symbols: c1_2, c3_1 333.78/291.50 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (11) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 333.78/291.50 The set S is empty 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (12) 333.78/291.50 BOUNDS(1, 1) 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 333.78/291.50 Transformed a relative TRS into a decreasing-loop problem. 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (14) 333.78/291.50 Obligation: 333.78/291.50 Analyzing the following TRS for decreasing loops: 333.78/291.50 333.78/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.78/291.50 333.78/291.50 333.78/291.50 The TRS R consists of the following rules: 333.78/291.50 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(x)) -> +(sum(x), s(x)) 333.78/291.50 +(x, 0) -> x 333.78/291.50 +(x, s(y)) -> s(+(x, y)) 333.78/291.50 333.78/291.50 S is empty. 333.78/291.50 Rewrite Strategy: FULL 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (15) DecreasingLoopProof (LOWER BOUND(ID)) 333.78/291.50 The following loop(s) give(s) rise to the lower bound Omega(n^1): 333.78/291.50 333.78/291.50 The rewrite sequence 333.78/291.50 333.78/291.50 +(x, s(y)) ->^+ s(+(x, y)) 333.78/291.50 333.78/291.50 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 333.78/291.50 333.78/291.50 The pumping substitution is [y / s(y)]. 333.78/291.50 333.78/291.50 The result substitution is [ ]. 333.78/291.50 333.78/291.50 333.78/291.50 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (16) 333.78/291.50 Complex Obligation (BEST) 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (17) 333.78/291.50 Obligation: 333.78/291.50 Proved the lower bound n^1 for the following obligation: 333.78/291.50 333.78/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.78/291.50 333.78/291.50 333.78/291.50 The TRS R consists of the following rules: 333.78/291.50 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(x)) -> +(sum(x), s(x)) 333.78/291.50 +(x, 0) -> x 333.78/291.50 +(x, s(y)) -> s(+(x, y)) 333.78/291.50 333.78/291.50 S is empty. 333.78/291.50 Rewrite Strategy: FULL 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (18) LowerBoundPropagationProof (FINISHED) 333.78/291.50 Propagated lower bound. 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (19) 333.78/291.50 BOUNDS(n^1, INF) 333.78/291.50 333.78/291.50 ---------------------------------------- 333.78/291.50 333.78/291.50 (20) 333.78/291.50 Obligation: 333.78/291.50 Analyzing the following TRS for decreasing loops: 333.78/291.50 333.78/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.78/291.50 333.78/291.50 333.78/291.50 The TRS R consists of the following rules: 333.78/291.50 333.78/291.50 sum(0) -> 0 333.78/291.50 sum(s(x)) -> +(sum(x), s(x)) 333.78/291.50 +(x, 0) -> x 333.78/291.50 +(x, s(y)) -> s(+(x, y)) 333.78/291.50 333.78/291.50 S is empty. 333.78/291.50 Rewrite Strategy: FULL 333.78/291.54 EOF