25.69/7.46 WORST_CASE(Omega(n^1), O(n^1)) 25.88/7.49 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 25.88/7.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.88/7.49 25.88/7.49 25.88/7.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.88/7.49 25.88/7.49 (0) CpxTRS 25.88/7.49 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 25.88/7.49 (2) CdtProblem 25.88/7.49 (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 25.88/7.49 (4) CdtProblem 25.88/7.49 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 25.88/7.49 (6) CdtProblem 25.88/7.49 (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 25.88/7.49 (8) CdtProblem 25.88/7.49 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 24 ms] 25.88/7.49 (10) CdtProblem 25.88/7.49 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 8 ms] 25.88/7.49 (12) CdtProblem 25.88/7.49 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 25.88/7.49 (14) BOUNDS(1, 1) 25.88/7.49 (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 25.88/7.49 (16) TRS for Loop Detection 25.88/7.49 (17) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 25.88/7.49 (18) BEST 25.88/7.49 (19) proven lower bound 25.88/7.49 (20) LowerBoundPropagationProof [FINISHED, 1 ms] 25.88/7.49 (21) BOUNDS(n^1, INF) 25.88/7.49 (22) TRS for Loop Detection 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (0) 25.88/7.49 Obligation: 25.88/7.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.88/7.49 25.88/7.49 25.88/7.49 The TRS R consists of the following rules: 25.88/7.49 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(x)) -> f(x, s(0), s(x), s(x)) 25.88/7.49 f(0, y, 0, u) -> true 25.88/7.49 f(0, y, s(z), u) -> false 25.88/7.49 f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u) 25.88/7.49 f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u)) 25.88/7.49 25.88/7.49 S is empty. 25.88/7.49 Rewrite Strategy: INNERMOST 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 25.88/7.49 Converted Cpx (relative) TRS to CDT 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (2) 25.88/7.49 Obligation: 25.88/7.49 Complexity Dependency Tuples Problem 25.88/7.49 25.88/7.49 Rules: 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0)) 25.88/7.49 f(0, z0, 0, z1) -> true 25.88/7.49 f(0, z0, s(z1), z2) -> false 25.88/7.49 f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2) 25.88/7.49 f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3)) 25.88/7.49 Tuples: 25.88/7.49 PERFECTP(0) -> c 25.88/7.49 PERFECTP(s(z0)) -> c1(F(z0, s(0), s(z0), s(z0))) 25.88/7.49 F(0, z0, 0, z1) -> c2 25.88/7.49 F(0, z0, s(z1), z2) -> c3 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3)) 25.88/7.49 S tuples: 25.88/7.49 PERFECTP(0) -> c 25.88/7.49 PERFECTP(s(z0)) -> c1(F(z0, s(0), s(z0), s(z0))) 25.88/7.49 F(0, z0, 0, z1) -> c2 25.88/7.49 F(0, z0, s(z1), z2) -> c3 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3)) 25.88/7.49 K tuples:none 25.88/7.49 Defined Rule Symbols: perfectp_1, f_4 25.88/7.49 25.88/7.49 Defined Pair Symbols: PERFECTP_1, F_4 25.88/7.49 25.88/7.49 Compound Symbols: c, c1_1, c2, c3, c4_1, c5_2 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (3) CdtLeafRemovalProof (ComplexityIfPolyImplication) 25.88/7.49 Removed 1 leading nodes: 25.88/7.49 PERFECTP(s(z0)) -> c1(F(z0, s(0), s(z0), s(z0))) 25.88/7.49 Removed 3 trailing nodes: 25.88/7.49 F(0, z0, 0, z1) -> c2 25.88/7.49 F(0, z0, s(z1), z2) -> c3 25.88/7.49 PERFECTP(0) -> c 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (4) 25.88/7.49 Obligation: 25.88/7.49 Complexity Dependency Tuples Problem 25.88/7.49 25.88/7.49 Rules: 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0)) 25.88/7.49 f(0, z0, 0, z1) -> true 25.88/7.49 f(0, z0, s(z1), z2) -> false 25.88/7.49 f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2) 25.88/7.49 f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3)) 25.88/7.49 Tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3)) 25.88/7.49 S tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3)) 25.88/7.49 K tuples:none 25.88/7.49 Defined Rule Symbols: perfectp_1, f_4 25.88/7.49 25.88/7.49 Defined Pair Symbols: F_4 25.88/7.49 25.88/7.49 Compound Symbols: c4_1, c5_2 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 25.88/7.49 Removed 1 trailing tuple parts 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (6) 25.88/7.49 Obligation: 25.88/7.49 Complexity Dependency Tuples Problem 25.88/7.49 25.88/7.49 Rules: 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0)) 25.88/7.49 f(0, z0, 0, z1) -> true 25.88/7.49 f(0, z0, s(z1), z2) -> false 25.88/7.49 f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2) 25.88/7.49 f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3)) 25.88/7.49 Tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 S tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 K tuples:none 25.88/7.49 Defined Rule Symbols: perfectp_1, f_4 25.88/7.49 25.88/7.49 Defined Pair Symbols: F_4 25.88/7.49 25.88/7.49 Compound Symbols: c4_1, c5_1 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 25.88/7.49 The following rules are not usable and were removed: 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0)) 25.88/7.49 f(0, z0, 0, z1) -> true 25.88/7.49 f(0, z0, s(z1), z2) -> false 25.88/7.49 f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2) 25.88/7.49 f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3)) 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (8) 25.88/7.49 Obligation: 25.88/7.49 Complexity Dependency Tuples Problem 25.88/7.49 25.88/7.49 Rules:none 25.88/7.49 Tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 S tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 K tuples:none 25.88/7.49 Defined Rule Symbols:none 25.88/7.49 25.88/7.49 Defined Pair Symbols: F_4 25.88/7.49 25.88/7.49 Compound Symbols: c4_1, c5_1 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.88/7.49 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 We considered the (Usable) Rules:none 25.88/7.49 And the Tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 The order we found is given by the following interpretation: 25.88/7.49 25.88/7.49 Polynomial interpretation : 25.88/7.49 25.88/7.49 POL(0) = 0 25.88/7.49 POL(F(x_1, x_2, x_3, x_4)) = x_1 + x_3 25.88/7.49 POL(c4(x_1)) = x_1 25.88/7.49 POL(c5(x_1)) = x_1 25.88/7.49 POL(minus(x_1, x_2)) = [1] 25.88/7.49 POL(s(x_1)) = [1] + x_1 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (10) 25.88/7.49 Obligation: 25.88/7.49 Complexity Dependency Tuples Problem 25.88/7.49 25.88/7.49 Rules:none 25.88/7.49 Tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 S tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 K tuples: 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 Defined Rule Symbols:none 25.88/7.49 25.88/7.49 Defined Pair Symbols: F_4 25.88/7.49 25.88/7.49 Compound Symbols: c4_1, c5_1 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.88/7.49 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 We considered the (Usable) Rules:none 25.88/7.49 And the Tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 The order we found is given by the following interpretation: 25.88/7.49 25.88/7.49 Polynomial interpretation : 25.88/7.49 25.88/7.49 POL(0) = 0 25.88/7.49 POL(F(x_1, x_2, x_3, x_4)) = x_1 + x_3 25.88/7.49 POL(c4(x_1)) = x_1 25.88/7.49 POL(c5(x_1)) = x_1 25.88/7.49 POL(minus(x_1, x_2)) = x_1 25.88/7.49 POL(s(x_1)) = [1] + x_1 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (12) 25.88/7.49 Obligation: 25.88/7.49 Complexity Dependency Tuples Problem 25.88/7.49 25.88/7.49 Rules:none 25.88/7.49 Tuples: 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 S tuples:none 25.88/7.49 K tuples: 25.88/7.49 F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3)) 25.88/7.49 F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2)) 25.88/7.49 Defined Rule Symbols:none 25.88/7.49 25.88/7.49 Defined Pair Symbols: F_4 25.88/7.49 25.88/7.49 Compound Symbols: c4_1, c5_1 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 25.88/7.49 The set S is empty 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (14) 25.88/7.49 BOUNDS(1, 1) 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 25.88/7.49 Transformed a relative TRS into a decreasing-loop problem. 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (16) 25.88/7.49 Obligation: 25.88/7.49 Analyzing the following TRS for decreasing loops: 25.88/7.49 25.88/7.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.88/7.49 25.88/7.49 25.88/7.49 The TRS R consists of the following rules: 25.88/7.49 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(x)) -> f(x, s(0), s(x), s(x)) 25.88/7.49 f(0, y, 0, u) -> true 25.88/7.49 f(0, y, s(z), u) -> false 25.88/7.49 f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u) 25.88/7.49 f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u)) 25.88/7.49 25.88/7.49 S is empty. 25.88/7.49 Rewrite Strategy: INNERMOST 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (17) DecreasingLoopProof (LOWER BOUND(ID)) 25.88/7.49 The following loop(s) give(s) rise to the lower bound Omega(n^1): 25.88/7.49 25.88/7.49 The rewrite sequence 25.88/7.49 25.88/7.49 f(s(s(x1_0)), s(y), z, s(y2_0)) ->^+ if(le(s(x1_0), y), f(s(s(x1_0)), minus(y, s(x1_0)), z, s(y2_0)), if(le(x1_0, y2_0), f(s(x1_0), minus(y2_0, x1_0), z, s(y2_0)), f(x1_0, s(y2_0), z, s(y2_0)))) 25.88/7.49 25.88/7.49 gives rise to a decreasing loop by considering the right hand sides subterm at position [2,2]. 25.88/7.49 25.88/7.49 The pumping substitution is [x1_0 / s(s(x1_0))]. 25.88/7.49 25.88/7.49 The result substitution is [y / y2_0]. 25.88/7.49 25.88/7.49 25.88/7.49 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (18) 25.88/7.49 Complex Obligation (BEST) 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (19) 25.88/7.49 Obligation: 25.88/7.49 Proved the lower bound n^1 for the following obligation: 25.88/7.49 25.88/7.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.88/7.49 25.88/7.49 25.88/7.49 The TRS R consists of the following rules: 25.88/7.49 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(x)) -> f(x, s(0), s(x), s(x)) 25.88/7.49 f(0, y, 0, u) -> true 25.88/7.49 f(0, y, s(z), u) -> false 25.88/7.49 f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u) 25.88/7.49 f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u)) 25.88/7.49 25.88/7.49 S is empty. 25.88/7.49 Rewrite Strategy: INNERMOST 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (20) LowerBoundPropagationProof (FINISHED) 25.88/7.49 Propagated lower bound. 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (21) 25.88/7.49 BOUNDS(n^1, INF) 25.88/7.49 25.88/7.49 ---------------------------------------- 25.88/7.49 25.88/7.49 (22) 25.88/7.49 Obligation: 25.88/7.49 Analyzing the following TRS for decreasing loops: 25.88/7.49 25.88/7.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.88/7.49 25.88/7.49 25.88/7.49 The TRS R consists of the following rules: 25.88/7.49 25.88/7.49 perfectp(0) -> false 25.88/7.49 perfectp(s(x)) -> f(x, s(0), s(x), s(x)) 25.88/7.49 f(0, y, 0, u) -> true 25.88/7.49 f(0, y, s(z), u) -> false 25.88/7.49 f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u) 25.88/7.49 f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u)) 25.88/7.49 25.88/7.49 S is empty. 25.88/7.49 Rewrite Strategy: INNERMOST 25.88/7.55 EOF