26.12/8.71 WORST_CASE(Omega(n^2), O(n^2)) 26.12/8.73 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 26.12/8.73 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 26.12/8.73 26.12/8.73 26.12/8.73 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 26.12/8.73 26.12/8.73 (0) CpxTRS 26.12/8.73 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (2) CpxTRS 26.12/8.73 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (4) CpxWeightedTrs 26.12/8.73 (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (6) CpxWeightedTrs 26.12/8.73 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (8) CpxTypedWeightedTrs 26.12/8.73 (9) CompletionProof [UPPER BOUND(ID), 0 ms] 26.12/8.73 (10) CpxTypedWeightedCompleteTrs 26.12/8.73 (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (12) CpxTypedWeightedCompleteTrs 26.12/8.73 (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 26.12/8.73 (14) CpxRNTS 26.12/8.73 (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (16) CpxRNTS 26.12/8.73 (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (18) CpxRNTS 26.12/8.73 (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 26.12/8.73 (20) CpxRNTS 26.12/8.73 (21) IntTrsBoundProof [UPPER BOUND(ID), 360 ms] 26.12/8.73 (22) CpxRNTS 26.12/8.73 (23) IntTrsBoundProof [UPPER BOUND(ID), 75 ms] 26.12/8.73 (24) CpxRNTS 26.12/8.73 (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 26.12/8.73 (26) CpxRNTS 26.12/8.73 (27) IntTrsBoundProof [UPPER BOUND(ID), 836 ms] 26.12/8.73 (28) CpxRNTS 26.12/8.73 (29) IntTrsBoundProof [UPPER BOUND(ID), 370 ms] 26.12/8.73 (30) CpxRNTS 26.12/8.73 (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 26.12/8.73 (32) CpxRNTS 26.12/8.73 (33) IntTrsBoundProof [UPPER BOUND(ID), 740 ms] 26.12/8.73 (34) CpxRNTS 26.12/8.73 (35) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 26.12/8.73 (36) CpxRNTS 26.12/8.73 (37) FinalProof [FINISHED, 0 ms] 26.12/8.73 (38) BOUNDS(1, n^2) 26.12/8.73 (39) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (40) CpxTRS 26.12/8.73 (41) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 26.12/8.73 (42) typed CpxTrs 26.12/8.73 (43) OrderProof [LOWER BOUND(ID), 0 ms] 26.12/8.73 (44) typed CpxTrs 26.12/8.73 (45) RewriteLemmaProof [LOWER BOUND(ID), 284 ms] 26.12/8.73 (46) BEST 26.12/8.73 (47) proven lower bound 26.12/8.73 (48) LowerBoundPropagationProof [FINISHED, 0 ms] 26.12/8.73 (49) BOUNDS(n^1, INF) 26.12/8.73 (50) typed CpxTrs 26.12/8.73 (51) RewriteLemmaProof [LOWER BOUND(ID), 777 ms] 26.12/8.73 (52) proven lower bound 26.12/8.73 (53) LowerBoundPropagationProof [FINISHED, 0 ms] 26.12/8.73 (54) BOUNDS(n^2, INF) 26.12/8.73 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (0) 26.12/8.73 Obligation: 26.12/8.73 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 26.12/8.73 26.12/8.73 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0) -> 1 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0, y) -> y 26.12/8.73 g(s(x), y) -> g(x, +(y, s(x))) 26.12/8.73 +(x, 0) -> x 26.12/8.73 +(x, s(y)) -> s(+(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+(y, x))) 26.12/8.73 26.12/8.73 S is empty. 26.12/8.73 Rewrite Strategy: FULL 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Converted rc-obligation to irc-obligation. 26.12/8.73 26.12/8.73 The duplicating contexts are: 26.12/8.73 f(s([])) 26.12/8.73 g(s([]), y) 26.12/8.73 26.12/8.73 26.12/8.73 The defined contexts are: 26.12/8.73 g(x0, []) 26.12/8.73 g(x0, s([])) 26.12/8.73 +([], s(x1)) 26.12/8.73 +([], x1) 26.12/8.73 26.12/8.73 26.12/8.73 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (2) 26.12/8.73 Obligation: 26.12/8.73 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 26.12/8.73 26.12/8.73 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0) -> 1 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0, y) -> y 26.12/8.73 g(s(x), y) -> g(x, +(y, s(x))) 26.12/8.73 +(x, 0) -> x 26.12/8.73 +(x, s(y)) -> s(+(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+(y, x))) 26.12/8.73 26.12/8.73 S is empty. 26.12/8.73 Rewrite Strategy: INNERMOST 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Transformed relative TRS to weighted TRS 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (4) 26.12/8.73 Obligation: 26.12/8.73 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 26.12/8.73 26.12/8.73 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0) -> 1 [1] 26.12/8.73 f(s(x)) -> g(x, s(x)) [1] 26.12/8.73 g(0, y) -> y [1] 26.12/8.73 g(s(x), y) -> g(x, +(y, s(x))) [1] 26.12/8.73 +(x, 0) -> x [1] 26.12/8.73 +(x, s(y)) -> s(+(x, y)) [1] 26.12/8.73 g(s(x), y) -> g(x, s(+(y, x))) [1] 26.12/8.73 26.12/8.73 Rewrite Strategy: INNERMOST 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Renamed defined symbols to avoid conflicts with arithmetic symbols: 26.12/8.73 26.12/8.73 + => plus 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (6) 26.12/8.73 Obligation: 26.12/8.73 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 26.12/8.73 26.12/8.73 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0) -> 1 [1] 26.12/8.73 f(s(x)) -> g(x, s(x)) [1] 26.12/8.73 g(0, y) -> y [1] 26.12/8.73 g(s(x), y) -> g(x, plus(y, s(x))) [1] 26.12/8.73 plus(x, 0) -> x [1] 26.12/8.73 plus(x, s(y)) -> s(plus(x, y)) [1] 26.12/8.73 g(s(x), y) -> g(x, s(plus(y, x))) [1] 26.12/8.73 26.12/8.73 Rewrite Strategy: INNERMOST 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Infered types. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (8) 26.12/8.73 Obligation: 26.12/8.73 Runtime Complexity Weighted TRS with Types. 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0) -> 1 [1] 26.12/8.73 f(s(x)) -> g(x, s(x)) [1] 26.12/8.73 g(0, y) -> y [1] 26.12/8.73 g(s(x), y) -> g(x, plus(y, s(x))) [1] 26.12/8.73 plus(x, 0) -> x [1] 26.12/8.73 plus(x, s(y)) -> s(plus(x, y)) [1] 26.12/8.73 g(s(x), y) -> g(x, s(plus(y, x))) [1] 26.12/8.73 26.12/8.73 The TRS has the following type information: 26.12/8.73 f :: 0:1:s -> 0:1:s 26.12/8.73 0 :: 0:1:s 26.12/8.73 1 :: 0:1:s 26.12/8.73 s :: 0:1:s -> 0:1:s 26.12/8.73 g :: 0:1:s -> 0:1:s -> 0:1:s 26.12/8.73 plus :: 0:1:s -> 0:1:s -> 0:1:s 26.12/8.73 26.12/8.73 Rewrite Strategy: INNERMOST 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (9) CompletionProof (UPPER BOUND(ID)) 26.12/8.73 The transformation into a RNTS is sound, since: 26.12/8.73 26.12/8.73 (a) The obligation is a constructor system where every type has a constant constructor, 26.12/8.73 26.12/8.73 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 26.12/8.73 26.12/8.73 f_1 26.12/8.73 g_2 26.12/8.73 26.12/8.73 (c) The following functions are completely defined: 26.12/8.73 26.12/8.73 plus_2 26.12/8.73 26.12/8.73 Due to the following rules being added: 26.12/8.73 26.12/8.73 plus(v0, v1) -> null_plus [0] 26.12/8.73 26.12/8.73 And the following fresh constants: null_plus 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (10) 26.12/8.73 Obligation: 26.12/8.73 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 26.12/8.73 26.12/8.73 Runtime Complexity Weighted TRS with Types. 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0) -> 1 [1] 26.12/8.73 f(s(x)) -> g(x, s(x)) [1] 26.12/8.73 g(0, y) -> y [1] 26.12/8.73 g(s(x), y) -> g(x, plus(y, s(x))) [1] 26.12/8.73 plus(x, 0) -> x [1] 26.12/8.73 plus(x, s(y)) -> s(plus(x, y)) [1] 26.12/8.73 g(s(x), y) -> g(x, s(plus(y, x))) [1] 26.12/8.73 plus(v0, v1) -> null_plus [0] 26.12/8.73 26.12/8.73 The TRS has the following type information: 26.12/8.73 f :: 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 0 :: 0:1:s:null_plus 26.12/8.73 1 :: 0:1:s:null_plus 26.12/8.73 s :: 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 g :: 0:1:s:null_plus -> 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 plus :: 0:1:s:null_plus -> 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 null_plus :: 0:1:s:null_plus 26.12/8.73 26.12/8.73 Rewrite Strategy: INNERMOST 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (11) NarrowingProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (12) 26.12/8.73 Obligation: 26.12/8.73 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 26.12/8.73 26.12/8.73 Runtime Complexity Weighted TRS with Types. 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0) -> 1 [1] 26.12/8.73 f(s(x)) -> g(x, s(x)) [1] 26.12/8.73 g(0, y) -> y [1] 26.12/8.73 g(s(x), y) -> g(x, s(plus(y, x))) [2] 26.12/8.73 g(s(x), y) -> g(x, null_plus) [1] 26.12/8.73 plus(x, 0) -> x [1] 26.12/8.73 plus(x, s(y)) -> s(plus(x, y)) [1] 26.12/8.73 g(s(0), y) -> g(0, s(y)) [2] 26.12/8.73 g(s(s(y')), y) -> g(s(y'), s(s(plus(y, y')))) [2] 26.12/8.73 g(s(x), y) -> g(x, s(null_plus)) [1] 26.12/8.73 plus(v0, v1) -> null_plus [0] 26.12/8.73 26.12/8.73 The TRS has the following type information: 26.12/8.73 f :: 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 0 :: 0:1:s:null_plus 26.12/8.73 1 :: 0:1:s:null_plus 26.12/8.73 s :: 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 g :: 0:1:s:null_plus -> 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 plus :: 0:1:s:null_plus -> 0:1:s:null_plus -> 0:1:s:null_plus 26.12/8.73 null_plus :: 0:1:s:null_plus 26.12/8.73 26.12/8.73 Rewrite Strategy: INNERMOST 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 26.12/8.73 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 26.12/8.73 The constant constructors are abstracted as follows: 26.12/8.73 26.12/8.73 0 => 0 26.12/8.73 1 => 1 26.12/8.73 null_plus => 0 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (14) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(x, 1 + x) :|: x >= 0, z = 1 + x 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y 26.12/8.73 g(z, z') -{ 1 }-> g(x, 0) :|: x >= 0, y >= 0, z = 1 + x, z' = y 26.12/8.73 g(z, z') -{ 2 }-> g(x, 1 + plus(y, x)) :|: x >= 0, y >= 0, z = 1 + x, z' = y 26.12/8.73 g(z, z') -{ 1 }-> g(x, 1 + 0) :|: x >= 0, y >= 0, z = 1 + x, z' = y 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + y) :|: z = 1 + 0, y >= 0, z' = y 26.12/8.73 g(z, z') -{ 2 }-> g(1 + y', 1 + (1 + plus(y, y'))) :|: y >= 0, z = 1 + (1 + y'), y' >= 0, z' = y 26.12/8.73 plus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 26.12/8.73 plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = x 26.12/8.73 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (15) SimplificationProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (16) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(z - 1, 1 + plus(z', z - 1)) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(1 + (z - 2), 1 + (1 + plus(z', z - 2))) :|: z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Found the following analysis order by SCC decomposition: 26.12/8.73 26.12/8.73 { plus } 26.12/8.73 { g } 26.12/8.73 { f } 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (18) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(z - 1, 1 + plus(z', z - 1)) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(1 + (z - 2), 1 + (1 + plus(z', z - 2))) :|: z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {plus}, {g}, {f} 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (19) ResultPropagationProof (UPPER BOUND(ID)) 26.12/8.73 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (20) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(z - 1, 1 + plus(z', z - 1)) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(1 + (z - 2), 1 + (1 + plus(z', z - 2))) :|: z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {plus}, {g}, {f} 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (21) IntTrsBoundProof (UPPER BOUND(ID)) 26.12/8.73 26.12/8.73 Computed SIZE bound using CoFloCo for: plus 26.12/8.73 after applying outer abstraction to obtain an ITS, 26.12/8.73 resulting in: O(n^1) with polynomial bound: z + z' 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (22) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(z - 1, 1 + plus(z', z - 1)) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(1 + (z - 2), 1 + (1 + plus(z', z - 2))) :|: z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {plus}, {g}, {f} 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: ?, size: O(n^1) [z + z'] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (23) IntTrsBoundProof (UPPER BOUND(ID)) 26.12/8.73 26.12/8.73 Computed RUNTIME bound using CoFloCo for: plus 26.12/8.73 after applying outer abstraction to obtain an ITS, 26.12/8.73 resulting in: O(n^1) with polynomial bound: 1 + z' 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (24) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(z - 1, 1 + plus(z', z - 1)) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 }-> g(1 + (z - 2), 1 + (1 + plus(z', z - 2))) :|: z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {g}, {f} 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z'] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (25) ResultPropagationProof (UPPER BOUND(ID)) 26.12/8.73 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (26) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 + z }-> g(z - 1, 1 + s) :|: s >= 0, s <= z' + (z - 1), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 + z }-> g(1 + (z - 2), 1 + (1 + s'')) :|: s'' >= 0, s'' <= z' + (z - 2), z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 + z' }-> 1 + s' :|: s' >= 0, s' <= z + (z' - 1), z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {g}, {f} 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z'] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (27) IntTrsBoundProof (UPPER BOUND(ID)) 26.12/8.73 26.12/8.73 Computed SIZE bound using CoFloCo for: g 26.12/8.73 after applying outer abstraction to obtain an ITS, 26.12/8.73 resulting in: O(n^2) with polynomial bound: z^2 + z' 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (28) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 + z }-> g(z - 1, 1 + s) :|: s >= 0, s <= z' + (z - 1), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 + z }-> g(1 + (z - 2), 1 + (1 + s'')) :|: s'' >= 0, s'' <= z' + (z - 2), z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 + z' }-> 1 + s' :|: s' >= 0, s' <= z + (z' - 1), z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {g}, {f} 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z'] 26.12/8.73 g: runtime: ?, size: O(n^2) [z^2 + z'] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (29) IntTrsBoundProof (UPPER BOUND(ID)) 26.12/8.73 26.12/8.73 Computed RUNTIME bound using CoFloCo for: g 26.12/8.73 after applying outer abstraction to obtain an ITS, 26.12/8.73 resulting in: O(n^2) with polynomial bound: 5 + 3*z + z^2 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (30) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 1 }-> g(z - 1, 1 + (z - 1)) :|: z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 g(z, z') -{ 2 }-> g(0, 1 + z') :|: z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 2 + z }-> g(z - 1, 1 + s) :|: s >= 0, s <= z' + (z - 1), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> g(z - 1, 1 + 0) :|: z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 + z }-> g(1 + (z - 2), 1 + (1 + s'')) :|: s'' >= 0, s'' <= z' + (z - 2), z' >= 0, z - 2 >= 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 + z' }-> 1 + s' :|: s' >= 0, s' <= z + (z' - 1), z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {f} 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z'] 26.12/8.73 g: runtime: O(n^2) [5 + 3*z + z^2], size: O(n^2) [z^2 + z'] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (31) ResultPropagationProof (UPPER BOUND(ID)) 26.12/8.73 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (32) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 4 + z + z^2 }-> s1 :|: s1 >= 0, s1 <= (z - 1) * (z - 1) + (1 + (z - 1)), z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 5 + 2*z + z^2 }-> s2 :|: s2 >= 0, s2 <= (z - 1) * (z - 1) + (1 + s), s >= 0, s <= z' + (z - 1), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 4 + z + z^2 }-> s3 :|: s3 >= 0, s3 <= (z - 1) * (z - 1) + 0, z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 7 }-> s4 :|: s4 >= 0, s4 <= 0 * 0 + (1 + z'), z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 4 + 2*z + z^2 }-> s5 :|: s5 >= 0, s5 <= (1 + (z - 2)) * (1 + (z - 2)) + (1 + (1 + s'')), s'' >= 0, s'' <= z' + (z - 2), z' >= 0, z - 2 >= 0 26.12/8.73 g(z, z') -{ 4 + z + z^2 }-> s6 :|: s6 >= 0, s6 <= (z - 1) * (z - 1) + (1 + 0), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 + z' }-> 1 + s' :|: s' >= 0, s' <= z + (z' - 1), z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {f} 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z'] 26.12/8.73 g: runtime: O(n^2) [5 + 3*z + z^2], size: O(n^2) [z^2 + z'] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (33) IntTrsBoundProof (UPPER BOUND(ID)) 26.12/8.73 26.12/8.73 Computed SIZE bound using KoAT for: f 26.12/8.73 after applying outer abstraction to obtain an ITS, 26.12/8.73 resulting in: O(n^2) with polynomial bound: 2 + z + z^2 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (34) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 4 + z + z^2 }-> s1 :|: s1 >= 0, s1 <= (z - 1) * (z - 1) + (1 + (z - 1)), z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 5 + 2*z + z^2 }-> s2 :|: s2 >= 0, s2 <= (z - 1) * (z - 1) + (1 + s), s >= 0, s <= z' + (z - 1), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 4 + z + z^2 }-> s3 :|: s3 >= 0, s3 <= (z - 1) * (z - 1) + 0, z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 7 }-> s4 :|: s4 >= 0, s4 <= 0 * 0 + (1 + z'), z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 4 + 2*z + z^2 }-> s5 :|: s5 >= 0, s5 <= (1 + (z - 2)) * (1 + (z - 2)) + (1 + (1 + s'')), s'' >= 0, s'' <= z' + (z - 2), z' >= 0, z - 2 >= 0 26.12/8.73 g(z, z') -{ 4 + z + z^2 }-> s6 :|: s6 >= 0, s6 <= (z - 1) * (z - 1) + (1 + 0), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 + z' }-> 1 + s' :|: s' >= 0, s' <= z + (z' - 1), z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: {f} 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z'] 26.12/8.73 g: runtime: O(n^2) [5 + 3*z + z^2], size: O(n^2) [z^2 + z'] 26.12/8.73 f: runtime: ?, size: O(n^2) [2 + z + z^2] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (35) IntTrsBoundProof (UPPER BOUND(ID)) 26.12/8.73 26.12/8.73 Computed RUNTIME bound using KoAT for: f 26.12/8.73 after applying outer abstraction to obtain an ITS, 26.12/8.73 resulting in: O(n^2) with polynomial bound: 5 + z + z^2 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (36) 26.12/8.73 Obligation: 26.12/8.73 Complexity RNTS consisting of the following rules: 26.12/8.73 26.12/8.73 f(z) -{ 4 + z + z^2 }-> s1 :|: s1 >= 0, s1 <= (z - 1) * (z - 1) + (1 + (z - 1)), z - 1 >= 0 26.12/8.73 f(z) -{ 1 }-> 1 :|: z = 0 26.12/8.73 g(z, z') -{ 5 + 2*z + z^2 }-> s2 :|: s2 >= 0, s2 <= (z - 1) * (z - 1) + (1 + s), s >= 0, s <= z' + (z - 1), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 4 + z + z^2 }-> s3 :|: s3 >= 0, s3 <= (z - 1) * (z - 1) + 0, z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 7 }-> s4 :|: s4 >= 0, s4 <= 0 * 0 + (1 + z'), z = 1 + 0, z' >= 0 26.12/8.73 g(z, z') -{ 4 + 2*z + z^2 }-> s5 :|: s5 >= 0, s5 <= (1 + (z - 2)) * (1 + (z - 2)) + (1 + (1 + s'')), s'' >= 0, s'' <= z' + (z - 2), z' >= 0, z - 2 >= 0 26.12/8.73 g(z, z') -{ 4 + z + z^2 }-> s6 :|: s6 >= 0, s6 <= (z - 1) * (z - 1) + (1 + 0), z - 1 >= 0, z' >= 0 26.12/8.73 g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 26.12/8.73 plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 26.12/8.73 plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 26.12/8.73 plus(z, z') -{ 1 + z' }-> 1 + s' :|: s' >= 0, s' <= z + (z' - 1), z >= 0, z' - 1 >= 0 26.12/8.73 26.12/8.73 Function symbols to be analyzed: 26.12/8.73 Previous analysis results are: 26.12/8.73 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z'] 26.12/8.73 g: runtime: O(n^2) [5 + 3*z + z^2], size: O(n^2) [z^2 + z'] 26.12/8.73 f: runtime: O(n^2) [5 + z + z^2], size: O(n^2) [2 + z + z^2] 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (37) FinalProof (FINISHED) 26.12/8.73 Computed overall runtime complexity 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (38) 26.12/8.73 BOUNDS(1, n^2) 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (39) RenamingProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Renamed function symbols to avoid clashes with predefined symbol. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (40) 26.12/8.73 Obligation: 26.12/8.73 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 26.12/8.73 26.12/8.73 26.12/8.73 The TRS R consists of the following rules: 26.12/8.73 26.12/8.73 f(0') -> 1' 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0', y) -> y 26.12/8.73 g(s(x), y) -> g(x, +'(y, s(x))) 26.12/8.73 +'(x, 0') -> x 26.12/8.73 +'(x, s(y)) -> s(+'(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+'(y, x))) 26.12/8.73 26.12/8.73 S is empty. 26.12/8.73 Rewrite Strategy: FULL 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (41) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 26.12/8.73 Infered types. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (42) 26.12/8.73 Obligation: 26.12/8.73 TRS: 26.12/8.73 Rules: 26.12/8.73 f(0') -> 1' 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0', y) -> y 26.12/8.73 g(s(x), y) -> g(x, +'(y, s(x))) 26.12/8.73 +'(x, 0') -> x 26.12/8.73 +'(x, s(y)) -> s(+'(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+'(y, x))) 26.12/8.73 26.12/8.73 Types: 26.12/8.73 f :: 0':1':s -> 0':1':s 26.12/8.73 0' :: 0':1':s 26.12/8.73 1' :: 0':1':s 26.12/8.73 s :: 0':1':s -> 0':1':s 26.12/8.73 g :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 +' :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 hole_0':1':s1_0 :: 0':1':s 26.12/8.73 gen_0':1':s2_0 :: Nat -> 0':1':s 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (43) OrderProof (LOWER BOUND(ID)) 26.12/8.73 Heuristically decided to analyse the following defined symbols: 26.12/8.73 g, +' 26.12/8.73 26.12/8.73 They will be analysed ascendingly in the following order: 26.12/8.73 +' < g 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (44) 26.12/8.73 Obligation: 26.12/8.73 TRS: 26.12/8.73 Rules: 26.12/8.73 f(0') -> 1' 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0', y) -> y 26.12/8.73 g(s(x), y) -> g(x, +'(y, s(x))) 26.12/8.73 +'(x, 0') -> x 26.12/8.73 +'(x, s(y)) -> s(+'(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+'(y, x))) 26.12/8.73 26.12/8.73 Types: 26.12/8.73 f :: 0':1':s -> 0':1':s 26.12/8.73 0' :: 0':1':s 26.12/8.73 1' :: 0':1':s 26.12/8.73 s :: 0':1':s -> 0':1':s 26.12/8.73 g :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 +' :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 hole_0':1':s1_0 :: 0':1':s 26.12/8.73 gen_0':1':s2_0 :: Nat -> 0':1':s 26.12/8.73 26.12/8.73 26.12/8.73 Generator Equations: 26.12/8.73 gen_0':1':s2_0(0) <=> 0' 26.12/8.73 gen_0':1':s2_0(+(x, 1)) <=> s(gen_0':1':s2_0(x)) 26.12/8.73 26.12/8.73 26.12/8.73 The following defined symbols remain to be analysed: 26.12/8.73 +', g 26.12/8.73 26.12/8.73 They will be analysed ascendingly in the following order: 26.12/8.73 +' < g 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (45) RewriteLemmaProof (LOWER BOUND(ID)) 26.12/8.73 Proved the following rewrite lemma: 26.12/8.73 +'(gen_0':1':s2_0(a), gen_0':1':s2_0(n4_0)) -> gen_0':1':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 26.12/8.73 26.12/8.73 Induction Base: 26.12/8.73 +'(gen_0':1':s2_0(a), gen_0':1':s2_0(0)) ->_R^Omega(1) 26.12/8.73 gen_0':1':s2_0(a) 26.12/8.73 26.12/8.73 Induction Step: 26.12/8.73 +'(gen_0':1':s2_0(a), gen_0':1':s2_0(+(n4_0, 1))) ->_R^Omega(1) 26.12/8.73 s(+'(gen_0':1':s2_0(a), gen_0':1':s2_0(n4_0))) ->_IH 26.12/8.73 s(gen_0':1':s2_0(+(a, c5_0))) 26.12/8.73 26.12/8.73 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (46) 26.12/8.73 Complex Obligation (BEST) 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (47) 26.12/8.73 Obligation: 26.12/8.73 Proved the lower bound n^1 for the following obligation: 26.12/8.73 26.12/8.73 TRS: 26.12/8.73 Rules: 26.12/8.73 f(0') -> 1' 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0', y) -> y 26.12/8.73 g(s(x), y) -> g(x, +'(y, s(x))) 26.12/8.73 +'(x, 0') -> x 26.12/8.73 +'(x, s(y)) -> s(+'(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+'(y, x))) 26.12/8.73 26.12/8.73 Types: 26.12/8.73 f :: 0':1':s -> 0':1':s 26.12/8.73 0' :: 0':1':s 26.12/8.73 1' :: 0':1':s 26.12/8.73 s :: 0':1':s -> 0':1':s 26.12/8.73 g :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 +' :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 hole_0':1':s1_0 :: 0':1':s 26.12/8.73 gen_0':1':s2_0 :: Nat -> 0':1':s 26.12/8.73 26.12/8.73 26.12/8.73 Generator Equations: 26.12/8.73 gen_0':1':s2_0(0) <=> 0' 26.12/8.73 gen_0':1':s2_0(+(x, 1)) <=> s(gen_0':1':s2_0(x)) 26.12/8.73 26.12/8.73 26.12/8.73 The following defined symbols remain to be analysed: 26.12/8.73 +', g 26.12/8.73 26.12/8.73 They will be analysed ascendingly in the following order: 26.12/8.73 +' < g 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (48) LowerBoundPropagationProof (FINISHED) 26.12/8.73 Propagated lower bound. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (49) 26.12/8.73 BOUNDS(n^1, INF) 26.12/8.73 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (50) 26.12/8.73 Obligation: 26.12/8.73 TRS: 26.12/8.73 Rules: 26.12/8.73 f(0') -> 1' 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0', y) -> y 26.12/8.73 g(s(x), y) -> g(x, +'(y, s(x))) 26.12/8.73 +'(x, 0') -> x 26.12/8.73 +'(x, s(y)) -> s(+'(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+'(y, x))) 26.12/8.73 26.12/8.73 Types: 26.12/8.73 f :: 0':1':s -> 0':1':s 26.12/8.73 0' :: 0':1':s 26.12/8.73 1' :: 0':1':s 26.12/8.73 s :: 0':1':s -> 0':1':s 26.12/8.73 g :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 +' :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 hole_0':1':s1_0 :: 0':1':s 26.12/8.73 gen_0':1':s2_0 :: Nat -> 0':1':s 26.12/8.73 26.12/8.73 26.12/8.73 Lemmas: 26.12/8.73 +'(gen_0':1':s2_0(a), gen_0':1':s2_0(n4_0)) -> gen_0':1':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 26.12/8.73 26.12/8.73 26.12/8.73 Generator Equations: 26.12/8.73 gen_0':1':s2_0(0) <=> 0' 26.12/8.73 gen_0':1':s2_0(+(x, 1)) <=> s(gen_0':1':s2_0(x)) 26.12/8.73 26.12/8.73 26.12/8.73 The following defined symbols remain to be analysed: 26.12/8.73 g 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (51) RewriteLemmaProof (LOWER BOUND(ID)) 26.12/8.73 Proved the following rewrite lemma: 26.12/8.73 g(gen_0':1':s2_0(n457_0), gen_0':1':s2_0(b)) -> *3_0, rt in Omega(n457_0 + n457_0^2) 26.12/8.73 26.12/8.73 Induction Base: 26.12/8.73 g(gen_0':1':s2_0(0), gen_0':1':s2_0(b)) 26.12/8.73 26.12/8.73 Induction Step: 26.12/8.73 g(gen_0':1':s2_0(+(n457_0, 1)), gen_0':1':s2_0(b)) ->_R^Omega(1) 26.12/8.73 g(gen_0':1':s2_0(n457_0), +'(gen_0':1':s2_0(b), s(gen_0':1':s2_0(n457_0)))) ->_L^Omega(2 + n457_0) 26.12/8.73 g(gen_0':1':s2_0(n457_0), gen_0':1':s2_0(+(+(n457_0, 1), b))) ->_IH 26.12/8.73 *3_0 26.12/8.73 26.12/8.73 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (52) 26.12/8.73 Obligation: 26.12/8.73 Proved the lower bound n^2 for the following obligation: 26.12/8.73 26.12/8.73 TRS: 26.12/8.73 Rules: 26.12/8.73 f(0') -> 1' 26.12/8.73 f(s(x)) -> g(x, s(x)) 26.12/8.73 g(0', y) -> y 26.12/8.73 g(s(x), y) -> g(x, +'(y, s(x))) 26.12/8.73 +'(x, 0') -> x 26.12/8.73 +'(x, s(y)) -> s(+'(x, y)) 26.12/8.73 g(s(x), y) -> g(x, s(+'(y, x))) 26.12/8.73 26.12/8.73 Types: 26.12/8.73 f :: 0':1':s -> 0':1':s 26.12/8.73 0' :: 0':1':s 26.12/8.73 1' :: 0':1':s 26.12/8.73 s :: 0':1':s -> 0':1':s 26.12/8.73 g :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 +' :: 0':1':s -> 0':1':s -> 0':1':s 26.12/8.73 hole_0':1':s1_0 :: 0':1':s 26.12/8.73 gen_0':1':s2_0 :: Nat -> 0':1':s 26.12/8.73 26.12/8.73 26.12/8.73 Lemmas: 26.12/8.73 +'(gen_0':1':s2_0(a), gen_0':1':s2_0(n4_0)) -> gen_0':1':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 26.12/8.73 26.12/8.73 26.12/8.73 Generator Equations: 26.12/8.73 gen_0':1':s2_0(0) <=> 0' 26.12/8.73 gen_0':1':s2_0(+(x, 1)) <=> s(gen_0':1':s2_0(x)) 26.12/8.73 26.12/8.73 26.12/8.73 The following defined symbols remain to be analysed: 26.12/8.73 g 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (53) LowerBoundPropagationProof (FINISHED) 26.12/8.73 Propagated lower bound. 26.12/8.73 ---------------------------------------- 26.12/8.73 26.12/8.73 (54) 26.12/8.73 BOUNDS(n^2, INF) 26.34/8.77 EOF