60.50/16.34 WORST_CASE(Omega(n^3), O(n^3)) 60.50/16.37 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 60.50/16.37 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 60.50/16.37 60.50/16.37 60.50/16.37 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 60.50/16.37 60.50/16.37 (0) CpxTRS 60.50/16.37 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 60.50/16.37 (2) CpxWeightedTrs 60.50/16.37 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 60.50/16.37 (4) CpxTypedWeightedTrs 60.50/16.37 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (6) CpxTypedWeightedCompleteTrs 60.50/16.37 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 60.50/16.37 (8) CpxTypedWeightedCompleteTrs 60.50/16.37 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (10) CpxRNTS 60.50/16.37 (11) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 60.50/16.37 (12) CpxRNTS 60.50/16.37 (13) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 60.50/16.37 (14) CpxRNTS 60.50/16.37 (15) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (16) CpxRNTS 60.50/16.37 (17) IntTrsBoundProof [UPPER BOUND(ID), 193 ms] 60.50/16.37 (18) CpxRNTS 60.50/16.37 (19) IntTrsBoundProof [UPPER BOUND(ID), 8 ms] 60.50/16.37 (20) CpxRNTS 60.50/16.37 (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (22) CpxRNTS 60.50/16.37 (23) IntTrsBoundProof [UPPER BOUND(ID), 442 ms] 60.50/16.37 (24) CpxRNTS 60.50/16.37 (25) IntTrsBoundProof [UPPER BOUND(ID), 96 ms] 60.50/16.37 (26) CpxRNTS 60.50/16.37 (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (28) CpxRNTS 60.50/16.37 (29) IntTrsBoundProof [UPPER BOUND(ID), 155 ms] 60.50/16.37 (30) CpxRNTS 60.50/16.37 (31) IntTrsBoundProof [UPPER BOUND(ID), 62 ms] 60.50/16.37 (32) CpxRNTS 60.50/16.37 (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (34) CpxRNTS 60.50/16.37 (35) IntTrsBoundProof [UPPER BOUND(ID), 170 ms] 60.50/16.37 (36) CpxRNTS 60.50/16.37 (37) IntTrsBoundProof [UPPER BOUND(ID), 42 ms] 60.50/16.37 (38) CpxRNTS 60.50/16.37 (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (40) CpxRNTS 60.50/16.37 (41) IntTrsBoundProof [UPPER BOUND(ID), 353 ms] 60.50/16.37 (42) CpxRNTS 60.50/16.37 (43) IntTrsBoundProof [UPPER BOUND(ID), 116 ms] 60.50/16.37 (44) CpxRNTS 60.50/16.37 (45) ResultPropagationProof [UPPER BOUND(ID), 1 ms] 60.50/16.37 (46) CpxRNTS 60.50/16.37 (47) IntTrsBoundProof [UPPER BOUND(ID), 1871 ms] 60.50/16.37 (48) CpxRNTS 60.50/16.37 (49) IntTrsBoundProof [UPPER BOUND(ID), 272 ms] 60.50/16.37 (50) CpxRNTS 60.50/16.37 (51) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (52) CpxRNTS 60.50/16.37 (53) IntTrsBoundProof [UPPER BOUND(ID), 639 ms] 60.50/16.37 (54) CpxRNTS 60.50/16.37 (55) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 60.50/16.37 (56) CpxRNTS 60.50/16.37 (57) FinalProof [FINISHED, 0 ms] 60.50/16.37 (58) BOUNDS(1, n^3) 60.50/16.37 (59) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 60.50/16.37 (60) CpxTRS 60.50/16.37 (61) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 60.50/16.37 (62) typed CpxTrs 60.50/16.37 (63) OrderProof [LOWER BOUND(ID), 0 ms] 60.50/16.37 (64) typed CpxTrs 60.50/16.37 (65) RewriteLemmaProof [LOWER BOUND(ID), 306 ms] 60.50/16.37 (66) BEST 60.50/16.37 (67) proven lower bound 60.50/16.37 (68) LowerBoundPropagationProof [FINISHED, 0 ms] 60.50/16.37 (69) BOUNDS(n^1, INF) 60.50/16.37 (70) typed CpxTrs 60.50/16.37 (71) RewriteLemmaProof [LOWER BOUND(ID), 14 ms] 60.50/16.37 (72) BEST 60.50/16.37 (73) proven lower bound 60.50/16.37 (74) LowerBoundPropagationProof [FINISHED, 0 ms] 60.50/16.37 (75) BOUNDS(n^2, INF) 60.50/16.37 (76) typed CpxTrs 60.50/16.37 (77) RewriteLemmaProof [LOWER BOUND(ID), 797 ms] 60.50/16.37 (78) proven lower bound 60.50/16.37 (79) LowerBoundPropagationProof [FINISHED, 0 ms] 60.50/16.37 (80) BOUNDS(n^3, INF) 60.50/16.37 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (0) 60.50/16.37 Obligation: 60.50/16.37 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 60.50/16.37 60.50/16.37 60.50/16.37 The TRS R consists of the following rules: 60.50/16.37 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 S is empty. 60.50/16.37 Rewrite Strategy: INNERMOST 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 60.50/16.37 Transformed relative TRS to weighted TRS 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (2) 60.50/16.37 Obligation: 60.50/16.37 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 60.50/16.37 60.50/16.37 60.50/16.37 The TRS R consists of the following rules: 60.50/16.37 60.50/16.37 null(nil) -> true [1] 60.50/16.37 null(add(n, x)) -> false [1] 60.50/16.37 tail(add(n, x)) -> x [1] 60.50/16.37 tail(nil) -> nil [1] 60.50/16.37 head(add(n, x)) -> n [1] 60.50/16.37 app(nil, y) -> y [1] 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) [1] 60.50/16.37 reverse(nil) -> nil [1] 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) [1] 60.50/16.37 shuffle(x) -> shuff(x, nil) [1] 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) [1] 60.50/16.37 if(true, x, y, z) -> y [1] 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) [1] 60.50/16.37 60.50/16.37 Rewrite Strategy: INNERMOST 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 60.50/16.37 Infered types. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (4) 60.50/16.37 Obligation: 60.50/16.37 Runtime Complexity Weighted TRS with Types. 60.50/16.37 The TRS R consists of the following rules: 60.50/16.37 60.50/16.37 null(nil) -> true [1] 60.50/16.37 null(add(n, x)) -> false [1] 60.50/16.37 tail(add(n, x)) -> x [1] 60.50/16.37 tail(nil) -> nil [1] 60.50/16.37 head(add(n, x)) -> n [1] 60.50/16.37 app(nil, y) -> y [1] 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) [1] 60.50/16.37 reverse(nil) -> nil [1] 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) [1] 60.50/16.37 shuffle(x) -> shuff(x, nil) [1] 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) [1] 60.50/16.37 if(true, x, y, z) -> y [1] 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) [1] 60.50/16.37 60.50/16.37 The TRS has the following type information: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 60.50/16.37 Rewrite Strategy: INNERMOST 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (5) CompletionProof (UPPER BOUND(ID)) 60.50/16.37 The transformation into a RNTS is sound, since: 60.50/16.37 60.50/16.37 (a) The obligation is a constructor system where every type has a constant constructor, 60.50/16.37 60.50/16.37 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 60.50/16.37 60.50/16.37 shuffle_1 60.50/16.37 shuff_2 60.50/16.37 if_4 60.50/16.37 60.50/16.37 (c) The following functions are completely defined: 60.50/16.37 60.50/16.37 null_1 60.50/16.37 app_2 60.50/16.37 head_1 60.50/16.37 reverse_1 60.50/16.37 tail_1 60.50/16.37 60.50/16.37 Due to the following rules being added: 60.50/16.37 60.50/16.37 head(v0) -> const [0] 60.50/16.37 60.50/16.37 And the following fresh constants: const 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (6) 60.50/16.37 Obligation: 60.50/16.37 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 60.50/16.37 60.50/16.37 Runtime Complexity Weighted TRS with Types. 60.50/16.37 The TRS R consists of the following rules: 60.50/16.37 60.50/16.37 null(nil) -> true [1] 60.50/16.37 null(add(n, x)) -> false [1] 60.50/16.37 tail(add(n, x)) -> x [1] 60.50/16.37 tail(nil) -> nil [1] 60.50/16.37 head(add(n, x)) -> n [1] 60.50/16.37 app(nil, y) -> y [1] 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) [1] 60.50/16.37 reverse(nil) -> nil [1] 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) [1] 60.50/16.37 shuffle(x) -> shuff(x, nil) [1] 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) [1] 60.50/16.37 if(true, x, y, z) -> y [1] 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) [1] 60.50/16.37 head(v0) -> const [0] 60.50/16.37 60.50/16.37 The TRS has the following type information: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: const -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> const 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 const :: const 60.50/16.37 60.50/16.37 Rewrite Strategy: INNERMOST 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 60.50/16.37 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (8) 60.50/16.37 Obligation: 60.50/16.37 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 60.50/16.37 60.50/16.37 Runtime Complexity Weighted TRS with Types. 60.50/16.37 The TRS R consists of the following rules: 60.50/16.37 60.50/16.37 null(nil) -> true [1] 60.50/16.37 null(add(n, x)) -> false [1] 60.50/16.37 tail(add(n, x)) -> x [1] 60.50/16.37 tail(nil) -> nil [1] 60.50/16.37 head(add(n, x)) -> n [1] 60.50/16.37 app(nil, y) -> y [1] 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) [1] 60.50/16.37 reverse(nil) -> nil [1] 60.50/16.37 reverse(add(n, nil)) -> app(nil, add(n, nil)) [2] 60.50/16.37 reverse(add(n, add(n', x'))) -> app(app(reverse(x'), add(n', nil)), add(n, nil)) [2] 60.50/16.37 shuffle(x) -> shuff(x, nil) [1] 60.50/16.37 shuff(nil, y) -> if(true, nil, y, app(y, add(const, nil))) [2] 60.50/16.37 shuff(add(n'', x''), y) -> if(false, add(n'', x''), y, app(y, add(n'', nil))) [3] 60.50/16.37 shuff(add(n'', x''), y) -> if(false, add(n'', x''), y, app(y, add(const, nil))) [2] 60.50/16.37 if(true, x, y, z) -> y [1] 60.50/16.37 if(false, add(n1, x1), y, z) -> shuff(reverse(x1), z) [2] 60.50/16.37 if(false, nil, y, z) -> shuff(reverse(nil), z) [2] 60.50/16.37 head(v0) -> const [0] 60.50/16.37 60.50/16.37 The TRS has the following type information: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: const -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> const 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 const :: const 60.50/16.37 60.50/16.37 Rewrite Strategy: INNERMOST 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 60.50/16.37 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 60.50/16.37 The constant constructors are abstracted as follows: 60.50/16.37 60.50/16.37 nil => 0 60.50/16.37 true => 1 60.50/16.37 false => 0 60.50/16.37 const => 0 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (10) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, y) :|: n >= 0, z'' = y, z' = 1 + n + x, x >= 0, y >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> y :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z) :|: z1 = y, x1 >= 0, z >= 0, z2 = z, y >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z) :|: z'' = 0, z1 = y, z >= 0, z2 = z, y >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + n + 0) :|: n >= 0, z' = 1 + n + 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, y, app(y, 1 + 0 + 0)) :|: z'' = y, y >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', y, app(y, 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' = y, y >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', y, app(y, 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' = y, y >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(x, 0) :|: z' = x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (11) SimplificationProof (BOTH BOUNDS(ID, ID)) 60.50/16.37 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (12) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (13) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 60.50/16.37 Found the following analysis order by SCC decomposition: 60.50/16.37 60.50/16.37 { head } 60.50/16.37 { app } 60.50/16.37 { null } 60.50/16.37 { tail } 60.50/16.37 { reverse } 60.50/16.37 { shuff, if } 60.50/16.37 { shuffle } 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (14) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {head}, {app}, {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (15) ResultPropagationProof (UPPER BOUND(ID)) 60.50/16.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (16) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {head}, {app}, {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (17) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed SIZE bound using KoAT for: head 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^1) with polynomial bound: z' 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (18) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {head}, {app}, {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: ?, size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (19) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed RUNTIME bound using CoFloCo for: head 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(1) with polynomial bound: 1 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (20) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {app}, {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (21) ResultPropagationProof (UPPER BOUND(ID)) 60.50/16.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (22) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {app}, {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (23) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed SIZE bound using CoFloCo for: app 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^1) with polynomial bound: z' + z'' 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (24) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {app}, {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: ?, size: O(n^1) [z' + z''] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (25) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed RUNTIME bound using CoFloCo for: app 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^1) with polynomial bound: 1 + z' 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (26) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(1, 0, z'', app(z'', 1 + 0 + 0)) :|: z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 3 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + n'' + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 2 }-> if(0, 1 + n'' + x'', z'', app(z'', 1 + 0 + 0)) :|: z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (27) ResultPropagationProof (UPPER BOUND(ID)) 60.50/16.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (28) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (29) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed SIZE bound using CoFloCo for: null 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(1) with polynomial bound: 1 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (30) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {null}, {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: ?, size: O(1) [1] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (31) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed RUNTIME bound using CoFloCo for: null 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(1) with polynomial bound: 1 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (32) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (33) ResultPropagationProof (UPPER BOUND(ID)) 60.50/16.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (34) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (35) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed SIZE bound using KoAT for: tail 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^1) with polynomial bound: z' 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (36) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {tail}, {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: ?, size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (37) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed RUNTIME bound using CoFloCo for: tail 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(1) with polynomial bound: 1 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (38) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (39) ResultPropagationProof (UPPER BOUND(ID)) 60.50/16.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (40) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (41) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed SIZE bound using CoFloCo for: reverse 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^1) with polynomial bound: z' 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (42) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {reverse}, {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: ?, size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (43) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed RUNTIME bound using CoFloCo for: reverse 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^2) with polynomial bound: 4 + 3*z' + 2*z'^2 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (44) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(x1), z2) :|: x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 2 }-> shuff(reverse(0), z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 2 }-> app(app(reverse(x'), 1 + n' + 0), 1 + n + 0) :|: n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (45) ResultPropagationProof (UPPER BOUND(ID)) 60.50/16.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (46) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 6 + 3*x1 + 2*x1^2 }-> shuff(s6, z2) :|: s6 >= 0, s6 <= x1, x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 6 }-> shuff(s7, z2) :|: s7 >= 0, s7 <= 0, z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 8 + s3 + s4 + 3*x' + 2*x'^2 }-> s5 :|: s3 >= 0, s3 <= x', s4 >= 0, s4 <= s3 + (1 + n' + 0), s5 >= 0, s5 <= s4 + (1 + n + 0), n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (47) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed SIZE bound using CoFloCo for: shuff 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^2) with polynomial bound: z'^2 + z'' 60.50/16.37 60.50/16.37 Computed SIZE bound using KoAT for: if 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^2) with polynomial bound: z''^2 + z1 + 2*z2 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (48) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 6 + 3*x1 + 2*x1^2 }-> shuff(s6, z2) :|: s6 >= 0, s6 <= x1, x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 6 }-> shuff(s7, z2) :|: s7 >= 0, s7 <= 0, z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 8 + s3 + s4 + 3*x' + 2*x'^2 }-> s5 :|: s3 >= 0, s3 <= x', s4 >= 0, s4 <= s3 + (1 + n' + 0), s5 >= 0, s5 <= s4 + (1 + n + 0), n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {shuff,if}, {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 60.50/16.37 shuff: runtime: ?, size: O(n^2) [z'^2 + z''] 60.50/16.37 if: runtime: ?, size: O(n^2) [z''^2 + z1 + 2*z2] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (49) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed RUNTIME bound using KoAT for: shuff 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^3) with polynomial bound: 20 + 47*z' + 6*z'*z'' + 26*z'^2 + 16*z'^3 + 3*z'' 60.50/16.37 60.50/16.37 Computed RUNTIME bound using KoAT for: if 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^3) with polynomial bound: 53 + 50*z'' + 6*z''*z2 + 28*z''^2 + 16*z''^3 + 6*z2 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (50) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 if(z', z'', z1, z2) -{ 6 + 3*x1 + 2*x1^2 }-> shuff(s6, z2) :|: s6 >= 0, s6 <= x1, x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 6 }-> shuff(s7, z2) :|: s7 >= 0, s7 <= 0, z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 8 + s3 + s4 + 3*x' + 2*x'^2 }-> s5 :|: s3 >= 0, s3 <= x', s4 >= 0, s4 <= s3 + (1 + n' + 0), s5 >= 0, s5 <= s4 + (1 + n + 0), n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(1, 0, z'', s'') :|: s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuff(z', z'') -{ 4 + z'' }-> if(0, 1 + n'' + x'', z'', s1) :|: s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 3 + z'' }-> if(0, 1 + n'' + x'', z'', s2) :|: s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuffle(z') -{ 1 }-> shuff(z', 0) :|: z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 60.50/16.37 shuff: runtime: O(n^3) [20 + 47*z' + 6*z'*z'' + 26*z'^2 + 16*z'^3 + 3*z''], size: O(n^2) [z'^2 + z''] 60.50/16.37 if: runtime: O(n^3) [53 + 50*z'' + 6*z''*z2 + 28*z''^2 + 16*z''^3 + 6*z2], size: O(n^2) [z''^2 + z1 + 2*z2] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (51) ResultPropagationProof (UPPER BOUND(ID)) 60.50/16.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (52) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 26 + 47*s6 + 6*s6*z2 + 26*s6^2 + 16*s6^3 + 3*x1 + 2*x1^2 + 3*z2 }-> s12 :|: s12 >= 0, s12 <= s6 * s6 + z2, s6 >= 0, s6 <= x1, x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 26 + 47*s7 + 6*s7*z2 + 26*s7^2 + 16*s7^3 + 3*z2 }-> s13 :|: s13 >= 0, s13 <= s7 * s7 + z2, s7 >= 0, s7 <= 0, z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 8 + s3 + s4 + 3*x' + 2*x'^2 }-> s5 :|: s3 >= 0, s3 <= x', s4 >= 0, s4 <= s3 + (1 + n' + 0), s5 >= 0, s5 <= s4 + (1 + n + 0), n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 151 + 154*n'' + 6*n''*s1 + 152*n''*x'' + 48*n''*x''^2 + 76*n''^2 + 48*n''^2*x'' + 16*n''^3 + 12*s1 + 6*s1*x'' + 154*x'' + 76*x''^2 + 16*x''^3 + z'' }-> s10 :|: s10 >= 0, s10 <= 2 * s1 + (1 + n'' + x'') * (1 + n'' + x'') + z'', s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 150 + 154*n'' + 6*n''*s2 + 152*n''*x'' + 48*n''*x''^2 + 76*n''^2 + 48*n''^2*x'' + 16*n''^3 + 12*s2 + 6*s2*x'' + 154*x'' + 76*x''^2 + 16*x''^3 + z'' }-> s11 :|: s11 >= 0, s11 <= 2 * s2 + (1 + n'' + x'') * (1 + n'' + x'') + z'', s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 56 + 6*s'' + z'' }-> s9 :|: s9 >= 0, s9 <= 2 * s'' + 0 * 0 + z'', s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuffle(z') -{ 21 + 47*z' + 26*z'^2 + 16*z'^3 }-> s8 :|: s8 >= 0, s8 <= z' * z' + 0, z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 60.50/16.37 shuff: runtime: O(n^3) [20 + 47*z' + 6*z'*z'' + 26*z'^2 + 16*z'^3 + 3*z''], size: O(n^2) [z'^2 + z''] 60.50/16.37 if: runtime: O(n^3) [53 + 50*z'' + 6*z''*z2 + 28*z''^2 + 16*z''^3 + 6*z2], size: O(n^2) [z''^2 + z1 + 2*z2] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (53) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed SIZE bound using KoAT for: shuffle 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^2) with polynomial bound: z'^2 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (54) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 26 + 47*s6 + 6*s6*z2 + 26*s6^2 + 16*s6^3 + 3*x1 + 2*x1^2 + 3*z2 }-> s12 :|: s12 >= 0, s12 <= s6 * s6 + z2, s6 >= 0, s6 <= x1, x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 26 + 47*s7 + 6*s7*z2 + 26*s7^2 + 16*s7^3 + 3*z2 }-> s13 :|: s13 >= 0, s13 <= s7 * s7 + z2, s7 >= 0, s7 <= 0, z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 8 + s3 + s4 + 3*x' + 2*x'^2 }-> s5 :|: s3 >= 0, s3 <= x', s4 >= 0, s4 <= s3 + (1 + n' + 0), s5 >= 0, s5 <= s4 + (1 + n + 0), n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 151 + 154*n'' + 6*n''*s1 + 152*n''*x'' + 48*n''*x''^2 + 76*n''^2 + 48*n''^2*x'' + 16*n''^3 + 12*s1 + 6*s1*x'' + 154*x'' + 76*x''^2 + 16*x''^3 + z'' }-> s10 :|: s10 >= 0, s10 <= 2 * s1 + (1 + n'' + x'') * (1 + n'' + x'') + z'', s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 150 + 154*n'' + 6*n''*s2 + 152*n''*x'' + 48*n''*x''^2 + 76*n''^2 + 48*n''^2*x'' + 16*n''^3 + 12*s2 + 6*s2*x'' + 154*x'' + 76*x''^2 + 16*x''^3 + z'' }-> s11 :|: s11 >= 0, s11 <= 2 * s2 + (1 + n'' + x'') * (1 + n'' + x'') + z'', s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 56 + 6*s'' + z'' }-> s9 :|: s9 >= 0, s9 <= 2 * s'' + 0 * 0 + z'', s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuffle(z') -{ 21 + 47*z' + 26*z'^2 + 16*z'^3 }-> s8 :|: s8 >= 0, s8 <= z' * z' + 0, z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: {shuffle} 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 60.50/16.37 shuff: runtime: O(n^3) [20 + 47*z' + 6*z'*z'' + 26*z'^2 + 16*z'^3 + 3*z''], size: O(n^2) [z'^2 + z''] 60.50/16.37 if: runtime: O(n^3) [53 + 50*z'' + 6*z''*z2 + 28*z''^2 + 16*z''^3 + 6*z2], size: O(n^2) [z''^2 + z1 + 2*z2] 60.50/16.37 shuffle: runtime: ?, size: O(n^2) [z'^2] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (55) IntTrsBoundProof (UPPER BOUND(ID)) 60.50/16.37 60.50/16.37 Computed RUNTIME bound using KoAT for: shuffle 60.50/16.37 after applying outer abstraction to obtain an ITS, 60.50/16.37 resulting in: O(n^3) with polynomial bound: 21 + 47*z' + 26*z'^2 + 16*z'^3 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (56) 60.50/16.37 Obligation: 60.50/16.37 Complexity RNTS consisting of the following rules: 60.50/16.37 60.50/16.37 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 60.50/16.37 app(z', z'') -{ 2 + x }-> 1 + n + s :|: s >= 0, s <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 60.50/16.37 head(z') -{ 1 }-> n :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 head(z') -{ 0 }-> 0 :|: z' >= 0 60.50/16.37 if(z', z'', z1, z2) -{ 26 + 47*s6 + 6*s6*z2 + 26*s6^2 + 16*s6^3 + 3*x1 + 2*x1^2 + 3*z2 }-> s12 :|: s12 >= 0, s12 <= s6 * s6 + z2, s6 >= 0, s6 <= x1, x1 >= 0, z2 >= 0, z1 >= 0, z'' = 1 + n1 + x1, n1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 26 + 47*s7 + 6*s7*z2 + 26*s7^2 + 16*s7^3 + 3*z2 }-> s13 :|: s13 >= 0, s13 <= s7 * s7 + z2, s7 >= 0, s7 <= 0, z'' = 0, z2 >= 0, z1 >= 0, z' = 0 60.50/16.37 if(z', z'', z1, z2) -{ 1 }-> z1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1 60.50/16.37 null(z') -{ 1 }-> 1 :|: z' = 0 60.50/16.37 null(z') -{ 1 }-> 0 :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 reverse(z') -{ 3 }-> s' :|: s' >= 0, s' <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 60.50/16.37 reverse(z') -{ 8 + s3 + s4 + 3*x' + 2*x'^2 }-> s5 :|: s3 >= 0, s3 <= x', s4 >= 0, s4 <= s3 + (1 + n' + 0), s5 >= 0, s5 <= s4 + (1 + n + 0), n >= 0, x' >= 0, n' >= 0, z' = 1 + n + (1 + n' + x') 60.50/16.37 reverse(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 shuff(z', z'') -{ 151 + 154*n'' + 6*n''*s1 + 152*n''*x'' + 48*n''*x''^2 + 76*n''^2 + 48*n''^2*x'' + 16*n''^3 + 12*s1 + 6*s1*x'' + 154*x'' + 76*x''^2 + 16*x''^3 + z'' }-> s10 :|: s10 >= 0, s10 <= 2 * s1 + (1 + n'' + x'') * (1 + n'' + x'') + z'', s1 >= 0, s1 <= z'' + (1 + n'' + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 150 + 154*n'' + 6*n''*s2 + 152*n''*x'' + 48*n''*x''^2 + 76*n''^2 + 48*n''^2*x'' + 16*n''^3 + 12*s2 + 6*s2*x'' + 154*x'' + 76*x''^2 + 16*x''^3 + z'' }-> s11 :|: s11 >= 0, s11 <= 2 * s2 + (1 + n'' + x'') * (1 + n'' + x'') + z'', s2 >= 0, s2 <= z'' + (1 + 0 + 0), z' = 1 + n'' + x'', z'' >= 0, n'' >= 0, x'' >= 0 60.50/16.37 shuff(z', z'') -{ 56 + 6*s'' + z'' }-> s9 :|: s9 >= 0, s9 <= 2 * s'' + 0 * 0 + z'', s'' >= 0, s'' <= z'' + (1 + 0 + 0), z'' >= 0, z' = 0 60.50/16.37 shuffle(z') -{ 21 + 47*z' + 26*z'^2 + 16*z'^3 }-> s8 :|: s8 >= 0, s8 <= z' * z' + 0, z' >= 0 60.50/16.37 tail(z') -{ 1 }-> x :|: n >= 0, z' = 1 + n + x, x >= 0 60.50/16.37 tail(z') -{ 1 }-> 0 :|: z' = 0 60.50/16.37 60.50/16.37 Function symbols to be analyzed: 60.50/16.37 Previous analysis results are: 60.50/16.37 head: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 60.50/16.37 null: runtime: O(1) [1], size: O(1) [1] 60.50/16.37 tail: runtime: O(1) [1], size: O(n^1) [z'] 60.50/16.37 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 60.50/16.37 shuff: runtime: O(n^3) [20 + 47*z' + 6*z'*z'' + 26*z'^2 + 16*z'^3 + 3*z''], size: O(n^2) [z'^2 + z''] 60.50/16.37 if: runtime: O(n^3) [53 + 50*z'' + 6*z''*z2 + 28*z''^2 + 16*z''^3 + 6*z2], size: O(n^2) [z''^2 + z1 + 2*z2] 60.50/16.37 shuffle: runtime: O(n^3) [21 + 47*z' + 26*z'^2 + 16*z'^3], size: O(n^2) [z'^2] 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (57) FinalProof (FINISHED) 60.50/16.37 Computed overall runtime complexity 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (58) 60.50/16.37 BOUNDS(1, n^3) 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (59) RenamingProof (BOTH BOUNDS(ID, ID)) 60.50/16.37 Renamed function symbols to avoid clashes with predefined symbol. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (60) 60.50/16.37 Obligation: 60.50/16.37 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 60.50/16.37 60.50/16.37 60.50/16.37 The TRS R consists of the following rules: 60.50/16.37 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 S is empty. 60.50/16.37 Rewrite Strategy: INNERMOST 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (61) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 60.50/16.37 Infered types. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (62) 60.50/16.37 Obligation: 60.50/16.37 Innermost TRS: 60.50/16.37 Rules: 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 Types: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 hole_true:false1_0 :: true:false 60.50/16.37 hole_nil:add2_0 :: nil:add 60.50/16.37 hole_head3_0 :: head 60.50/16.37 gen_nil:add4_0 :: Nat -> nil:add 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (63) OrderProof (LOWER BOUND(ID)) 60.50/16.37 Heuristically decided to analyse the following defined symbols: 60.50/16.37 app, reverse, shuff 60.50/16.37 60.50/16.37 They will be analysed ascendingly in the following order: 60.50/16.37 app < reverse 60.50/16.37 app < shuff 60.50/16.37 reverse < shuff 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (64) 60.50/16.37 Obligation: 60.50/16.37 Innermost TRS: 60.50/16.37 Rules: 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 Types: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 hole_true:false1_0 :: true:false 60.50/16.37 hole_nil:add2_0 :: nil:add 60.50/16.37 hole_head3_0 :: head 60.50/16.37 gen_nil:add4_0 :: Nat -> nil:add 60.50/16.37 60.50/16.37 60.50/16.37 Generator Equations: 60.50/16.37 gen_nil:add4_0(0) <=> nil 60.50/16.37 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 60.50/16.37 60.50/16.37 60.50/16.37 The following defined symbols remain to be analysed: 60.50/16.37 app, reverse, shuff 60.50/16.37 60.50/16.37 They will be analysed ascendingly in the following order: 60.50/16.37 app < reverse 60.50/16.37 app < shuff 60.50/16.37 reverse < shuff 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (65) RewriteLemmaProof (LOWER BOUND(ID)) 60.50/16.37 Proved the following rewrite lemma: 60.50/16.37 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 60.50/16.37 60.50/16.37 Induction Base: 60.50/16.37 app(gen_nil:add4_0(0), gen_nil:add4_0(b)) ->_R^Omega(1) 60.50/16.37 gen_nil:add4_0(b) 60.50/16.37 60.50/16.37 Induction Step: 60.50/16.37 app(gen_nil:add4_0(+(n6_0, 1)), gen_nil:add4_0(b)) ->_R^Omega(1) 60.50/16.37 add(hole_head3_0, app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b))) ->_IH 60.50/16.37 add(hole_head3_0, gen_nil:add4_0(+(b, c7_0))) 60.50/16.37 60.50/16.37 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (66) 60.50/16.37 Complex Obligation (BEST) 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (67) 60.50/16.37 Obligation: 60.50/16.37 Proved the lower bound n^1 for the following obligation: 60.50/16.37 60.50/16.37 Innermost TRS: 60.50/16.37 Rules: 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 Types: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 hole_true:false1_0 :: true:false 60.50/16.37 hole_nil:add2_0 :: nil:add 60.50/16.37 hole_head3_0 :: head 60.50/16.37 gen_nil:add4_0 :: Nat -> nil:add 60.50/16.37 60.50/16.37 60.50/16.37 Generator Equations: 60.50/16.37 gen_nil:add4_0(0) <=> nil 60.50/16.37 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 60.50/16.37 60.50/16.37 60.50/16.37 The following defined symbols remain to be analysed: 60.50/16.37 app, reverse, shuff 60.50/16.37 60.50/16.37 They will be analysed ascendingly in the following order: 60.50/16.37 app < reverse 60.50/16.37 app < shuff 60.50/16.37 reverse < shuff 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (68) LowerBoundPropagationProof (FINISHED) 60.50/16.37 Propagated lower bound. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (69) 60.50/16.37 BOUNDS(n^1, INF) 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (70) 60.50/16.37 Obligation: 60.50/16.37 Innermost TRS: 60.50/16.37 Rules: 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 Types: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 hole_true:false1_0 :: true:false 60.50/16.37 hole_nil:add2_0 :: nil:add 60.50/16.37 hole_head3_0 :: head 60.50/16.37 gen_nil:add4_0 :: Nat -> nil:add 60.50/16.37 60.50/16.37 60.50/16.37 Lemmas: 60.50/16.37 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 60.50/16.37 60.50/16.37 60.50/16.37 Generator Equations: 60.50/16.37 gen_nil:add4_0(0) <=> nil 60.50/16.37 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 60.50/16.37 60.50/16.37 60.50/16.37 The following defined symbols remain to be analysed: 60.50/16.37 reverse, shuff 60.50/16.37 60.50/16.37 They will be analysed ascendingly in the following order: 60.50/16.37 reverse < shuff 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (71) RewriteLemmaProof (LOWER BOUND(ID)) 60.50/16.37 Proved the following rewrite lemma: 60.50/16.37 reverse(gen_nil:add4_0(n665_0)) -> gen_nil:add4_0(n665_0), rt in Omega(1 + n665_0 + n665_0^2) 60.50/16.37 60.50/16.37 Induction Base: 60.50/16.37 reverse(gen_nil:add4_0(0)) ->_R^Omega(1) 60.50/16.37 nil 60.50/16.37 60.50/16.37 Induction Step: 60.50/16.37 reverse(gen_nil:add4_0(+(n665_0, 1))) ->_R^Omega(1) 60.50/16.37 app(reverse(gen_nil:add4_0(n665_0)), add(hole_head3_0, nil)) ->_IH 60.50/16.37 app(gen_nil:add4_0(c666_0), add(hole_head3_0, nil)) ->_L^Omega(1 + n665_0) 60.50/16.37 gen_nil:add4_0(+(n665_0, +(0, 1))) 60.50/16.37 60.50/16.37 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (72) 60.50/16.37 Complex Obligation (BEST) 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (73) 60.50/16.37 Obligation: 60.50/16.37 Proved the lower bound n^2 for the following obligation: 60.50/16.37 60.50/16.37 Innermost TRS: 60.50/16.37 Rules: 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 Types: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 hole_true:false1_0 :: true:false 60.50/16.37 hole_nil:add2_0 :: nil:add 60.50/16.37 hole_head3_0 :: head 60.50/16.37 gen_nil:add4_0 :: Nat -> nil:add 60.50/16.37 60.50/16.37 60.50/16.37 Lemmas: 60.50/16.37 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 60.50/16.37 60.50/16.37 60.50/16.37 Generator Equations: 60.50/16.37 gen_nil:add4_0(0) <=> nil 60.50/16.37 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 60.50/16.37 60.50/16.37 60.50/16.37 The following defined symbols remain to be analysed: 60.50/16.37 reverse, shuff 60.50/16.37 60.50/16.37 They will be analysed ascendingly in the following order: 60.50/16.37 reverse < shuff 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (74) LowerBoundPropagationProof (FINISHED) 60.50/16.37 Propagated lower bound. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (75) 60.50/16.37 BOUNDS(n^2, INF) 60.50/16.37 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (76) 60.50/16.37 Obligation: 60.50/16.37 Innermost TRS: 60.50/16.37 Rules: 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 Types: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 hole_true:false1_0 :: true:false 60.50/16.37 hole_nil:add2_0 :: nil:add 60.50/16.37 hole_head3_0 :: head 60.50/16.37 gen_nil:add4_0 :: Nat -> nil:add 60.50/16.37 60.50/16.37 60.50/16.37 Lemmas: 60.50/16.37 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 60.50/16.37 reverse(gen_nil:add4_0(n665_0)) -> gen_nil:add4_0(n665_0), rt in Omega(1 + n665_0 + n665_0^2) 60.50/16.37 60.50/16.37 60.50/16.37 Generator Equations: 60.50/16.37 gen_nil:add4_0(0) <=> nil 60.50/16.37 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 60.50/16.37 60.50/16.37 60.50/16.37 The following defined symbols remain to be analysed: 60.50/16.37 shuff 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (77) RewriteLemmaProof (LOWER BOUND(ID)) 60.50/16.37 Proved the following rewrite lemma: 60.50/16.37 shuff(gen_nil:add4_0(n952_0), gen_nil:add4_0(b)) -> *5_0, rt in Omega(b*n952_0 + n952_0 + n952_0^2 + n952_0^3) 60.50/16.37 60.50/16.37 Induction Base: 60.50/16.37 shuff(gen_nil:add4_0(0), gen_nil:add4_0(b)) 60.50/16.37 60.50/16.37 Induction Step: 60.50/16.37 shuff(gen_nil:add4_0(+(n952_0, 1)), gen_nil:add4_0(b)) ->_R^Omega(1) 60.50/16.37 if(null(gen_nil:add4_0(+(n952_0, 1))), gen_nil:add4_0(+(n952_0, 1)), gen_nil:add4_0(b), app(gen_nil:add4_0(b), add(head(gen_nil:add4_0(+(n952_0, 1))), nil))) ->_R^Omega(1) 60.50/16.37 if(false, gen_nil:add4_0(+(1, n952_0)), gen_nil:add4_0(b), app(gen_nil:add4_0(b), add(head(gen_nil:add4_0(+(1, n952_0))), nil))) ->_R^Omega(1) 60.50/16.37 if(false, gen_nil:add4_0(+(1, n952_0)), gen_nil:add4_0(b), app(gen_nil:add4_0(b), add(hole_head3_0, nil))) ->_L^Omega(1 + b) 60.50/16.37 if(false, gen_nil:add4_0(+(1, n952_0)), gen_nil:add4_0(+(0, 1)), gen_nil:add4_0(+(b, +(0, 1)))) ->_R^Omega(1) 60.50/16.37 shuff(reverse(tail(gen_nil:add4_0(+(1, n952_0)))), gen_nil:add4_0(+(1, b))) ->_R^Omega(1) 60.50/16.37 shuff(reverse(gen_nil:add4_0(n952_0)), gen_nil:add4_0(+(1, b))) ->_L^Omega(1 + n952_0 + n952_0^2) 60.50/16.37 shuff(gen_nil:add4_0(n952_0), gen_nil:add4_0(+(1, b))) ->_IH 60.50/16.37 *5_0 60.50/16.37 60.50/16.37 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (78) 60.50/16.37 Obligation: 60.50/16.37 Proved the lower bound n^3 for the following obligation: 60.50/16.37 60.50/16.37 Innermost TRS: 60.50/16.37 Rules: 60.50/16.37 null(nil) -> true 60.50/16.37 null(add(n, x)) -> false 60.50/16.37 tail(add(n, x)) -> x 60.50/16.37 tail(nil) -> nil 60.50/16.37 head(add(n, x)) -> n 60.50/16.37 app(nil, y) -> y 60.50/16.37 app(add(n, x), y) -> add(n, app(x, y)) 60.50/16.37 reverse(nil) -> nil 60.50/16.37 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 60.50/16.37 shuffle(x) -> shuff(x, nil) 60.50/16.37 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 60.50/16.37 if(true, x, y, z) -> y 60.50/16.37 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 60.50/16.37 60.50/16.37 Types: 60.50/16.37 null :: nil:add -> true:false 60.50/16.37 nil :: nil:add 60.50/16.37 true :: true:false 60.50/16.37 add :: head -> nil:add -> nil:add 60.50/16.37 false :: true:false 60.50/16.37 tail :: nil:add -> nil:add 60.50/16.37 head :: nil:add -> head 60.50/16.37 app :: nil:add -> nil:add -> nil:add 60.50/16.37 reverse :: nil:add -> nil:add 60.50/16.37 shuffle :: nil:add -> nil:add 60.50/16.37 shuff :: nil:add -> nil:add -> nil:add 60.50/16.37 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 60.50/16.37 hole_true:false1_0 :: true:false 60.50/16.37 hole_nil:add2_0 :: nil:add 60.50/16.37 hole_head3_0 :: head 60.50/16.37 gen_nil:add4_0 :: Nat -> nil:add 60.50/16.37 60.50/16.37 60.50/16.37 Lemmas: 60.50/16.37 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 60.50/16.37 reverse(gen_nil:add4_0(n665_0)) -> gen_nil:add4_0(n665_0), rt in Omega(1 + n665_0 + n665_0^2) 60.50/16.37 60.50/16.37 60.50/16.37 Generator Equations: 60.50/16.37 gen_nil:add4_0(0) <=> nil 60.50/16.37 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 60.50/16.37 60.50/16.37 60.50/16.37 The following defined symbols remain to be analysed: 60.50/16.37 shuff 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (79) LowerBoundPropagationProof (FINISHED) 60.50/16.37 Propagated lower bound. 60.50/16.37 ---------------------------------------- 60.50/16.37 60.50/16.37 (80) 60.50/16.37 BOUNDS(n^3, INF) 60.71/16.41 EOF