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