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