315.27/291.55 WORST_CASE(Omega(n^1), O(n^2)) 315.27/291.56 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 315.27/291.56 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 315.27/291.56 315.27/291.56 315.27/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 315.27/291.56 315.27/291.56 (0) CpxTRS 315.27/291.56 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 315.27/291.56 (2) CpxTRS 315.27/291.56 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 315.27/291.56 (4) CdtProblem 315.27/291.56 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 315.27/291.56 (6) CdtProblem 315.27/291.56 (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 315.27/291.56 (8) CdtProblem 315.27/291.56 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 315.27/291.56 (10) CdtProblem 315.27/291.56 (11) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 315.27/291.56 (12) CdtProblem 315.27/291.56 (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 315.27/291.56 (14) CdtProblem 315.27/291.56 (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 8 ms] 315.27/291.56 (16) CdtProblem 315.27/291.56 (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 9 ms] 315.27/291.56 (18) CdtProblem 315.27/291.56 (19) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 315.27/291.56 (20) BOUNDS(1, 1) 315.27/291.56 (21) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 315.27/291.56 (22) TRS for Loop Detection 315.27/291.56 (23) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 315.27/291.56 (24) BEST 315.27/291.56 (25) proven lower bound 315.27/291.56 (26) LowerBoundPropagationProof [FINISHED, 0 ms] 315.27/291.56 (27) BOUNDS(n^1, INF) 315.27/291.56 (28) TRS for Loop Detection 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (0) 315.27/291.56 Obligation: 315.27/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 315.27/291.56 315.27/291.56 315.27/291.56 The TRS R consists of the following rules: 315.27/291.56 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(x)) -> x 315.27/291.56 le(0, y) -> true 315.27/291.56 le(s(x), 0) -> false 315.27/291.56 le(s(x), s(y)) -> le(x, y) 315.27/291.56 minus(x, 0) -> x 315.27/291.56 minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y))))) 315.27/291.56 if(true, x, y) -> x 315.27/291.56 if(false, x, y) -> y 315.27/291.56 315.27/291.56 S is empty. 315.27/291.56 Rewrite Strategy: FULL 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 315.27/291.56 Converted rc-obligation to irc-obligation. 315.27/291.56 315.27/291.56 The duplicating contexts are: 315.27/291.56 minus([], s(y)) 315.27/291.56 minus(x, s([])) 315.27/291.56 315.27/291.56 315.27/291.56 The defined contexts are: 315.27/291.56 if([], 0, x1) 315.27/291.56 if(x0, 0, []) 315.27/291.56 p([]) 315.27/291.56 minus(x0, []) 315.27/291.56 le(x0, s([])) 315.27/291.56 p(s([])) 315.27/291.56 le(x0, []) 315.27/291.56 315.27/291.56 315.27/291.56 [] just represents basic- or constructor-terms in the following defined contexts: 315.27/291.56 if([], 0, x1) 315.27/291.56 minus(x0, []) 315.27/291.56 315.27/291.56 315.27/291.56 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (2) 315.27/291.56 Obligation: 315.27/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 315.27/291.56 315.27/291.56 315.27/291.56 The TRS R consists of the following rules: 315.27/291.56 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(x)) -> x 315.27/291.56 le(0, y) -> true 315.27/291.56 le(s(x), 0) -> false 315.27/291.56 le(s(x), s(y)) -> le(x, y) 315.27/291.56 minus(x, 0) -> x 315.27/291.56 minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y))))) 315.27/291.56 if(true, x, y) -> x 315.27/291.56 if(false, x, y) -> y 315.27/291.56 315.27/291.56 S is empty. 315.27/291.56 Rewrite Strategy: INNERMOST 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 315.27/291.56 Converted Cpx (relative) TRS to CDT 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (4) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules: 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(z0)) -> z0 315.27/291.56 le(0, z0) -> true 315.27/291.56 le(s(z0), 0) -> false 315.27/291.56 le(s(z0), s(z1)) -> le(z0, z1) 315.27/291.56 minus(z0, 0) -> z0 315.27/291.56 minus(z0, s(z1)) -> if(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))) 315.27/291.56 if(true, z0, z1) -> z0 315.27/291.56 if(false, z0, z1) -> z1 315.27/291.56 Tuples: 315.27/291.56 P(0) -> c 315.27/291.56 P(s(z0)) -> c1 315.27/291.56 LE(0, z0) -> c2 315.27/291.56 LE(s(z0), 0) -> c3 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, 0) -> c5 315.27/291.56 MINUS(z0, s(z1)) -> c6(IF(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))), LE(z0, s(z1)), P(minus(z0, p(s(z1)))), MINUS(z0, p(s(z1))), P(s(z1))) 315.27/291.56 IF(true, z0, z1) -> c7 315.27/291.56 IF(false, z0, z1) -> c8 315.27/291.56 S tuples: 315.27/291.56 P(0) -> c 315.27/291.56 P(s(z0)) -> c1 315.27/291.56 LE(0, z0) -> c2 315.27/291.56 LE(s(z0), 0) -> c3 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, 0) -> c5 315.27/291.56 MINUS(z0, s(z1)) -> c6(IF(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))), LE(z0, s(z1)), P(minus(z0, p(s(z1)))), MINUS(z0, p(s(z1))), P(s(z1))) 315.27/291.56 IF(true, z0, z1) -> c7 315.27/291.56 IF(false, z0, z1) -> c8 315.27/291.56 K tuples:none 315.27/291.56 Defined Rule Symbols: p_1, le_2, minus_2, if_3 315.27/291.56 315.27/291.56 Defined Pair Symbols: P_1, LE_2, MINUS_2, IF_3 315.27/291.56 315.27/291.56 Compound Symbols: c, c1, c2, c3, c4_1, c5, c6_5, c7, c8 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 315.27/291.56 Removed 7 trailing nodes: 315.27/291.56 IF(true, z0, z1) -> c7 315.27/291.56 LE(s(z0), 0) -> c3 315.27/291.56 MINUS(z0, 0) -> c5 315.27/291.56 P(s(z0)) -> c1 315.27/291.56 LE(0, z0) -> c2 315.27/291.56 P(0) -> c 315.27/291.56 IF(false, z0, z1) -> c8 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (6) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules: 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(z0)) -> z0 315.27/291.56 le(0, z0) -> true 315.27/291.56 le(s(z0), 0) -> false 315.27/291.56 le(s(z0), s(z1)) -> le(z0, z1) 315.27/291.56 minus(z0, 0) -> z0 315.27/291.56 minus(z0, s(z1)) -> if(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))) 315.27/291.56 if(true, z0, z1) -> z0 315.27/291.56 if(false, z0, z1) -> z1 315.27/291.56 Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, s(z1)) -> c6(IF(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))), LE(z0, s(z1)), P(minus(z0, p(s(z1)))), MINUS(z0, p(s(z1))), P(s(z1))) 315.27/291.56 S tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, s(z1)) -> c6(IF(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))), LE(z0, s(z1)), P(minus(z0, p(s(z1)))), MINUS(z0, p(s(z1))), P(s(z1))) 315.27/291.56 K tuples:none 315.27/291.56 Defined Rule Symbols: p_1, le_2, minus_2, if_3 315.27/291.56 315.27/291.56 Defined Pair Symbols: LE_2, MINUS_2 315.27/291.56 315.27/291.56 Compound Symbols: c4_1, c6_5 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 315.27/291.56 Removed 3 trailing tuple parts 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (8) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules: 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(z0)) -> z0 315.27/291.56 le(0, z0) -> true 315.27/291.56 le(s(z0), 0) -> false 315.27/291.56 le(s(z0), s(z1)) -> le(z0, z1) 315.27/291.56 minus(z0, 0) -> z0 315.27/291.56 minus(z0, s(z1)) -> if(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))) 315.27/291.56 if(true, z0, z1) -> z0 315.27/291.56 if(false, z0, z1) -> z1 315.27/291.56 Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, s(z1)) -> c6(LE(z0, s(z1)), MINUS(z0, p(s(z1)))) 315.27/291.56 S tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, s(z1)) -> c6(LE(z0, s(z1)), MINUS(z0, p(s(z1)))) 315.27/291.56 K tuples:none 315.27/291.56 Defined Rule Symbols: p_1, le_2, minus_2, if_3 315.27/291.56 315.27/291.56 Defined Pair Symbols: LE_2, MINUS_2 315.27/291.56 315.27/291.56 Compound Symbols: c4_1, c6_2 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 315.27/291.56 The following rules are not usable and were removed: 315.27/291.56 p(0) -> 0 315.27/291.56 le(0, z0) -> true 315.27/291.56 le(s(z0), 0) -> false 315.27/291.56 le(s(z0), s(z1)) -> le(z0, z1) 315.27/291.56 minus(z0, 0) -> z0 315.27/291.56 minus(z0, s(z1)) -> if(le(z0, s(z1)), 0, p(minus(z0, p(s(z1))))) 315.27/291.56 if(true, z0, z1) -> z0 315.27/291.56 if(false, z0, z1) -> z1 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (10) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules: 315.27/291.56 p(s(z0)) -> z0 315.27/291.56 Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, s(z1)) -> c6(LE(z0, s(z1)), MINUS(z0, p(s(z1)))) 315.27/291.56 S tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(z0, s(z1)) -> c6(LE(z0, s(z1)), MINUS(z0, p(s(z1)))) 315.27/291.56 K tuples:none 315.27/291.56 Defined Rule Symbols: p_1 315.27/291.56 315.27/291.56 Defined Pair Symbols: LE_2, MINUS_2 315.27/291.56 315.27/291.56 Compound Symbols: c4_1, c6_2 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (11) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) 315.27/291.56 Use narrowing to replace MINUS(z0, s(z1)) -> c6(LE(z0, s(z1)), MINUS(z0, p(s(z1)))) by 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (12) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules: 315.27/291.56 p(s(z0)) -> z0 315.27/291.56 Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 S tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 K tuples:none 315.27/291.56 Defined Rule Symbols: p_1 315.27/291.56 315.27/291.56 Defined Pair Symbols: LE_2, MINUS_2 315.27/291.56 315.27/291.56 Compound Symbols: c4_1, c6_2 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 315.27/291.56 The following rules are not usable and were removed: 315.27/291.56 p(s(z0)) -> z0 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (14) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules:none 315.27/291.56 Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 S tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 K tuples:none 315.27/291.56 Defined Rule Symbols:none 315.27/291.56 315.27/291.56 Defined Pair Symbols: LE_2, MINUS_2 315.27/291.56 315.27/291.56 Compound Symbols: c4_1, c6_2 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 315.27/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 We considered the (Usable) Rules:none 315.27/291.56 And the Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 The order we found is given by the following interpretation: 315.27/291.56 315.27/291.56 Polynomial interpretation : 315.27/291.56 315.27/291.56 POL(LE(x_1, x_2)) = [3] 315.27/291.56 POL(MINUS(x_1, x_2)) = [2]x_2 315.27/291.56 POL(c4(x_1)) = x_1 315.27/291.56 POL(c6(x_1, x_2)) = x_1 + x_2 315.27/291.56 POL(s(x_1)) = [3] + x_1 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (16) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules:none 315.27/291.56 Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 S tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 K tuples: 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 Defined Rule Symbols:none 315.27/291.56 315.27/291.56 Defined Pair Symbols: LE_2, MINUS_2 315.27/291.56 315.27/291.56 Compound Symbols: c4_1, c6_2 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 315.27/291.56 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 We considered the (Usable) Rules:none 315.27/291.56 And the Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 The order we found is given by the following interpretation: 315.27/291.56 315.27/291.56 Polynomial interpretation : 315.27/291.56 315.27/291.56 POL(LE(x_1, x_2)) = [2] + x_2 315.27/291.56 POL(MINUS(x_1, x_2)) = [2]x_2^2 + x_1*x_2 315.27/291.56 POL(c4(x_1)) = x_1 315.27/291.56 POL(c6(x_1, x_2)) = x_1 + x_2 315.27/291.56 POL(s(x_1)) = [2] + x_1 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (18) 315.27/291.56 Obligation: 315.27/291.56 Complexity Dependency Tuples Problem 315.27/291.56 315.27/291.56 Rules:none 315.27/291.56 Tuples: 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 S tuples:none 315.27/291.56 K tuples: 315.27/291.56 MINUS(x0, s(z0)) -> c6(LE(x0, s(z0)), MINUS(x0, z0)) 315.27/291.56 LE(s(z0), s(z1)) -> c4(LE(z0, z1)) 315.27/291.56 Defined Rule Symbols:none 315.27/291.56 315.27/291.56 Defined Pair Symbols: LE_2, MINUS_2 315.27/291.56 315.27/291.56 Compound Symbols: c4_1, c6_2 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (19) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 315.27/291.56 The set S is empty 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (20) 315.27/291.56 BOUNDS(1, 1) 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (21) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 315.27/291.56 Transformed a relative TRS into a decreasing-loop problem. 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (22) 315.27/291.56 Obligation: 315.27/291.56 Analyzing the following TRS for decreasing loops: 315.27/291.56 315.27/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 315.27/291.56 315.27/291.56 315.27/291.56 The TRS R consists of the following rules: 315.27/291.56 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(x)) -> x 315.27/291.56 le(0, y) -> true 315.27/291.56 le(s(x), 0) -> false 315.27/291.56 le(s(x), s(y)) -> le(x, y) 315.27/291.56 minus(x, 0) -> x 315.27/291.56 minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y))))) 315.27/291.56 if(true, x, y) -> x 315.27/291.56 if(false, x, y) -> y 315.27/291.56 315.27/291.56 S is empty. 315.27/291.56 Rewrite Strategy: FULL 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (23) DecreasingLoopProof (LOWER BOUND(ID)) 315.27/291.56 The following loop(s) give(s) rise to the lower bound Omega(n^1): 315.27/291.56 315.27/291.56 The rewrite sequence 315.27/291.56 315.27/291.56 le(s(x), s(y)) ->^+ le(x, y) 315.27/291.56 315.27/291.56 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 315.27/291.56 315.27/291.56 The pumping substitution is [x / s(x), y / s(y)]. 315.27/291.56 315.27/291.56 The result substitution is [ ]. 315.27/291.56 315.27/291.56 315.27/291.56 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (24) 315.27/291.56 Complex Obligation (BEST) 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (25) 315.27/291.56 Obligation: 315.27/291.56 Proved the lower bound n^1 for the following obligation: 315.27/291.56 315.27/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 315.27/291.56 315.27/291.56 315.27/291.56 The TRS R consists of the following rules: 315.27/291.56 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(x)) -> x 315.27/291.56 le(0, y) -> true 315.27/291.56 le(s(x), 0) -> false 315.27/291.56 le(s(x), s(y)) -> le(x, y) 315.27/291.56 minus(x, 0) -> x 315.27/291.56 minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y))))) 315.27/291.56 if(true, x, y) -> x 315.27/291.56 if(false, x, y) -> y 315.27/291.56 315.27/291.56 S is empty. 315.27/291.56 Rewrite Strategy: FULL 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (26) LowerBoundPropagationProof (FINISHED) 315.27/291.56 Propagated lower bound. 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (27) 315.27/291.56 BOUNDS(n^1, INF) 315.27/291.56 315.27/291.56 ---------------------------------------- 315.27/291.56 315.27/291.56 (28) 315.27/291.56 Obligation: 315.27/291.56 Analyzing the following TRS for decreasing loops: 315.27/291.56 315.27/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 315.27/291.56 315.27/291.56 315.27/291.56 The TRS R consists of the following rules: 315.27/291.56 315.27/291.56 p(0) -> 0 315.27/291.56 p(s(x)) -> x 315.27/291.56 le(0, y) -> true 315.27/291.56 le(s(x), 0) -> false 315.27/291.56 le(s(x), s(y)) -> le(x, y) 315.27/291.56 minus(x, 0) -> x 315.27/291.56 minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y))))) 315.27/291.56 if(true, x, y) -> x 315.27/291.56 if(false, x, y) -> y 315.27/291.56 315.27/291.56 S is empty. 315.27/291.56 Rewrite Strategy: FULL 315.36/291.59 EOF