39.22/13.77 WORST_CASE(Omega(n^3), O(n^3)) 39.22/13.78 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 39.22/13.78 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 39.22/13.78 39.22/13.78 39.22/13.78 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 39.22/13.78 39.22/13.78 (0) CpxTRS 39.22/13.78 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 13 ms] 39.22/13.78 (2) CpxTRS 39.22/13.78 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 39.22/13.78 (4) CpxWeightedTrs 39.22/13.78 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 39.22/13.78 (6) CpxTypedWeightedTrs 39.22/13.78 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (8) CpxTypedWeightedCompleteTrs 39.22/13.78 (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 39.22/13.78 (10) CpxTypedWeightedCompleteTrs 39.22/13.78 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (12) CpxRNTS 39.22/13.78 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 39.22/13.78 (14) CpxRNTS 39.22/13.78 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 39.22/13.78 (16) CpxRNTS 39.22/13.78 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (18) CpxRNTS 39.22/13.78 (19) IntTrsBoundProof [UPPER BOUND(ID), 382 ms] 39.22/13.78 (20) CpxRNTS 39.22/13.78 (21) IntTrsBoundProof [UPPER BOUND(ID), 97 ms] 39.22/13.78 (22) CpxRNTS 39.22/13.78 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (24) CpxRNTS 39.22/13.78 (25) IntTrsBoundProof [UPPER BOUND(ID), 401 ms] 39.22/13.78 (26) CpxRNTS 39.22/13.78 (27) IntTrsBoundProof [UPPER BOUND(ID), 93 ms] 39.22/13.78 (28) CpxRNTS 39.22/13.78 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (30) CpxRNTS 39.22/13.78 (31) IntTrsBoundProof [UPPER BOUND(ID), 380 ms] 39.22/13.78 (32) CpxRNTS 39.22/13.78 (33) IntTrsBoundProof [UPPER BOUND(ID), 124 ms] 39.22/13.78 (34) CpxRNTS 39.22/13.78 (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (36) CpxRNTS 39.22/13.78 (37) IntTrsBoundProof [UPPER BOUND(ID), 623 ms] 39.22/13.78 (38) CpxRNTS 39.22/13.78 (39) IntTrsBoundProof [UPPER BOUND(ID), 236 ms] 39.22/13.78 (40) CpxRNTS 39.22/13.78 (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (42) CpxRNTS 39.22/13.78 (43) IntTrsBoundProof [UPPER BOUND(ID), 805 ms] 39.22/13.78 (44) CpxRNTS 39.22/13.78 (45) IntTrsBoundProof [UPPER BOUND(ID), 509 ms] 39.22/13.78 (46) CpxRNTS 39.22/13.78 (47) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (48) CpxRNTS 39.22/13.78 (49) IntTrsBoundProof [UPPER BOUND(ID), 310 ms] 39.22/13.78 (50) CpxRNTS 39.22/13.78 (51) IntTrsBoundProof [UPPER BOUND(ID), 96 ms] 39.22/13.78 (52) CpxRNTS 39.22/13.78 (53) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 39.22/13.78 (54) CpxRNTS 39.22/13.78 (55) IntTrsBoundProof [UPPER BOUND(ID), 381 ms] 39.22/13.78 (56) CpxRNTS 39.22/13.78 (57) IntTrsBoundProof [UPPER BOUND(ID), 32 ms] 39.22/13.78 (58) CpxRNTS 39.22/13.78 (59) FinalProof [FINISHED, 0 ms] 39.22/13.78 (60) BOUNDS(1, n^3) 39.22/13.78 (61) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 39.22/13.78 (62) CpxTRS 39.22/13.78 (63) SlicingProof [LOWER BOUND(ID), 0 ms] 39.22/13.78 (64) CpxTRS 39.22/13.78 (65) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 39.22/13.78 (66) typed CpxTrs 39.22/13.78 (67) OrderProof [LOWER BOUND(ID), 0 ms] 39.22/13.78 (68) typed CpxTrs 39.22/13.78 (69) RewriteLemmaProof [LOWER BOUND(ID), 283 ms] 39.22/13.78 (70) BEST 39.22/13.78 (71) proven lower bound 39.22/13.78 (72) LowerBoundPropagationProof [FINISHED, 0 ms] 39.22/13.78 (73) BOUNDS(n^1, INF) 39.22/13.78 (74) typed CpxTrs 39.22/13.78 (75) RewriteLemmaProof [LOWER BOUND(ID), 59 ms] 39.22/13.78 (76) typed CpxTrs 39.22/13.78 (77) RewriteLemmaProof [LOWER BOUND(ID), 5 ms] 39.22/13.78 (78) BEST 39.22/13.78 (79) proven lower bound 39.22/13.78 (80) LowerBoundPropagationProof [FINISHED, 0 ms] 39.22/13.78 (81) BOUNDS(n^2, INF) 39.22/13.78 (82) typed CpxTrs 39.22/13.78 (83) RewriteLemmaProof [LOWER BOUND(ID), 21 ms] 39.22/13.78 (84) BEST 39.22/13.78 (85) proven lower bound 39.22/13.78 (86) LowerBoundPropagationProof [FINISHED, 0 ms] 39.22/13.78 (87) BOUNDS(n^3, INF) 39.22/13.78 (88) typed CpxTrs 39.22/13.78 (89) RewriteLemmaProof [LOWER BOUND(ID), 80 ms] 39.22/13.78 (90) typed CpxTrs 39.22/13.78 (91) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 39.22/13.78 (92) BOUNDS(1, INF) 39.22/13.78 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (0) 39.22/13.78 Obligation: 39.22/13.78 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 39.22/13.78 39.22/13.78 39.22/13.78 The TRS R consists of the following rules: 39.22/13.78 39.22/13.78 minus(x, 0) -> x 39.22/13.78 minus(s(x), s(y)) -> minus(x, y) 39.22/13.78 quot(0, s(y)) -> 0 39.22/13.78 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.78 app(nil, y) -> y 39.22/13.78 app(add(n, x), y) -> add(n, app(x, y)) 39.22/13.78 reverse(nil) -> nil 39.22/13.78 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 39.22/13.78 shuffle(nil) -> nil 39.22/13.78 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) 39.22/13.78 concat(leaf, y) -> y 39.22/13.78 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.78 less_leaves(x, leaf) -> false 39.22/13.78 less_leaves(leaf, cons(w, z)) -> true 39.22/13.78 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.78 39.22/13.78 S is empty. 39.22/13.78 Rewrite Strategy: FULL 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 39.22/13.78 Converted rc-obligation to irc-obligation. 39.22/13.78 39.22/13.78 The duplicating contexts are: 39.22/13.78 quot(s(x), s([])) 39.22/13.78 39.22/13.78 39.22/13.78 The defined contexts are: 39.22/13.78 quot([], s(x1)) 39.22/13.78 shuffle([]) 39.22/13.78 less_leaves([], x1) 39.22/13.78 less_leaves(x0, []) 39.22/13.78 app([], add(x1, nil)) 39.22/13.78 minus([], x1) 39.22/13.78 app([], x1) 39.22/13.78 reverse([]) 39.22/13.78 concat([], x1) 39.22/13.78 concat(x0, []) 39.22/13.78 app(x0, add([], nil)) 39.22/13.78 app(x0, []) 39.22/13.78 39.22/13.78 39.22/13.78 [] just represents basic- or constructor-terms in the following defined contexts: 39.22/13.78 quot([], s(x1)) 39.22/13.78 39.22/13.78 39.22/13.78 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (2) 39.22/13.78 Obligation: 39.22/13.78 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 39.22/13.78 39.22/13.78 39.22/13.78 The TRS R consists of the following rules: 39.22/13.78 39.22/13.78 minus(x, 0) -> x 39.22/13.78 minus(s(x), s(y)) -> minus(x, y) 39.22/13.78 quot(0, s(y)) -> 0 39.22/13.78 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.78 app(nil, y) -> y 39.22/13.78 app(add(n, x), y) -> add(n, app(x, y)) 39.22/13.78 reverse(nil) -> nil 39.22/13.78 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 39.22/13.78 shuffle(nil) -> nil 39.22/13.78 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) 39.22/13.78 concat(leaf, y) -> y 39.22/13.78 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.78 less_leaves(x, leaf) -> false 39.22/13.78 less_leaves(leaf, cons(w, z)) -> true 39.22/13.78 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.78 39.22/13.78 S is empty. 39.22/13.78 Rewrite Strategy: INNERMOST 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 39.22/13.78 Transformed relative TRS to weighted TRS 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (4) 39.22/13.78 Obligation: 39.22/13.78 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 39.22/13.78 39.22/13.78 39.22/13.78 The TRS R consists of the following rules: 39.22/13.78 39.22/13.78 minus(x, 0) -> x [1] 39.22/13.78 minus(s(x), s(y)) -> minus(x, y) [1] 39.22/13.78 quot(0, s(y)) -> 0 [1] 39.22/13.78 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1] 39.22/13.78 app(nil, y) -> y [1] 39.22/13.78 app(add(n, x), y) -> add(n, app(x, y)) [1] 39.22/13.78 reverse(nil) -> nil [1] 39.22/13.78 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) [1] 39.22/13.78 shuffle(nil) -> nil [1] 39.22/13.78 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) [1] 39.22/13.78 concat(leaf, y) -> y [1] 39.22/13.78 concat(cons(u, v), y) -> cons(u, concat(v, y)) [1] 39.22/13.78 less_leaves(x, leaf) -> false [1] 39.22/13.78 less_leaves(leaf, cons(w, z)) -> true [1] 39.22/13.78 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) [1] 39.22/13.78 39.22/13.78 Rewrite Strategy: INNERMOST 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 39.22/13.78 Infered types. 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (6) 39.22/13.78 Obligation: 39.22/13.78 Runtime Complexity Weighted TRS with Types. 39.22/13.78 The TRS R consists of the following rules: 39.22/13.78 39.22/13.78 minus(x, 0) -> x [1] 39.22/13.78 minus(s(x), s(y)) -> minus(x, y) [1] 39.22/13.78 quot(0, s(y)) -> 0 [1] 39.22/13.78 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1] 39.22/13.78 app(nil, y) -> y [1] 39.22/13.78 app(add(n, x), y) -> add(n, app(x, y)) [1] 39.22/13.78 reverse(nil) -> nil [1] 39.22/13.78 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) [1] 39.22/13.78 shuffle(nil) -> nil [1] 39.22/13.78 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) [1] 39.22/13.78 concat(leaf, y) -> y [1] 39.22/13.78 concat(cons(u, v), y) -> cons(u, concat(v, y)) [1] 39.22/13.78 less_leaves(x, leaf) -> false [1] 39.22/13.78 less_leaves(leaf, cons(w, z)) -> true [1] 39.22/13.78 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) [1] 39.22/13.78 39.22/13.78 The TRS has the following type information: 39.22/13.78 minus :: 0:s -> 0:s -> 0:s 39.22/13.78 0 :: 0:s 39.22/13.78 s :: 0:s -> 0:s 39.22/13.78 quot :: 0:s -> 0:s -> 0:s 39.22/13.78 app :: nil:add -> nil:add -> nil:add 39.22/13.78 nil :: nil:add 39.22/13.78 add :: a -> nil:add -> nil:add 39.22/13.78 reverse :: nil:add -> nil:add 39.22/13.78 shuffle :: nil:add -> nil:add 39.22/13.78 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.78 leaf :: leaf:cons 39.22/13.78 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.78 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.78 false :: false:true 39.22/13.78 true :: false:true 39.22/13.78 39.22/13.78 Rewrite Strategy: INNERMOST 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (7) CompletionProof (UPPER BOUND(ID)) 39.22/13.78 The transformation into a RNTS is sound, since: 39.22/13.78 39.22/13.78 (a) The obligation is a constructor system where every type has a constant constructor, 39.22/13.78 39.22/13.78 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 39.22/13.78 39.22/13.78 quot_2 39.22/13.78 shuffle_1 39.22/13.78 less_leaves_2 39.22/13.78 39.22/13.78 (c) The following functions are completely defined: 39.22/13.78 39.22/13.78 minus_2 39.22/13.78 reverse_1 39.22/13.78 concat_2 39.22/13.78 app_2 39.22/13.78 39.22/13.78 Due to the following rules being added: 39.22/13.78 39.22/13.78 minus(v0, v1) -> 0 [0] 39.22/13.78 39.22/13.78 And the following fresh constants: const 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (8) 39.22/13.78 Obligation: 39.22/13.78 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 39.22/13.78 39.22/13.78 Runtime Complexity Weighted TRS with Types. 39.22/13.78 The TRS R consists of the following rules: 39.22/13.78 39.22/13.78 minus(x, 0) -> x [1] 39.22/13.78 minus(s(x), s(y)) -> minus(x, y) [1] 39.22/13.78 quot(0, s(y)) -> 0 [1] 39.22/13.78 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1] 39.22/13.78 app(nil, y) -> y [1] 39.22/13.78 app(add(n, x), y) -> add(n, app(x, y)) [1] 39.22/13.78 reverse(nil) -> nil [1] 39.22/13.78 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) [1] 39.22/13.78 shuffle(nil) -> nil [1] 39.22/13.78 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) [1] 39.22/13.78 concat(leaf, y) -> y [1] 39.22/13.78 concat(cons(u, v), y) -> cons(u, concat(v, y)) [1] 39.22/13.78 less_leaves(x, leaf) -> false [1] 39.22/13.78 less_leaves(leaf, cons(w, z)) -> true [1] 39.22/13.78 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) [1] 39.22/13.78 minus(v0, v1) -> 0 [0] 39.22/13.78 39.22/13.78 The TRS has the following type information: 39.22/13.78 minus :: 0:s -> 0:s -> 0:s 39.22/13.78 0 :: 0:s 39.22/13.78 s :: 0:s -> 0:s 39.22/13.78 quot :: 0:s -> 0:s -> 0:s 39.22/13.78 app :: nil:add -> nil:add -> nil:add 39.22/13.78 nil :: nil:add 39.22/13.78 add :: a -> nil:add -> nil:add 39.22/13.78 reverse :: nil:add -> nil:add 39.22/13.78 shuffle :: nil:add -> nil:add 39.22/13.78 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.78 leaf :: leaf:cons 39.22/13.78 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.78 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.78 false :: false:true 39.22/13.78 true :: false:true 39.22/13.78 const :: a 39.22/13.78 39.22/13.78 Rewrite Strategy: INNERMOST 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (9) NarrowingProof (BOTH BOUNDS(ID, ID)) 39.22/13.78 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (10) 39.22/13.78 Obligation: 39.22/13.78 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 39.22/13.78 39.22/13.78 Runtime Complexity Weighted TRS with Types. 39.22/13.78 The TRS R consists of the following rules: 39.22/13.78 39.22/13.78 minus(x, 0) -> x [1] 39.22/13.78 minus(s(x), s(y)) -> minus(x, y) [1] 39.22/13.78 quot(0, s(y)) -> 0 [1] 39.22/13.78 quot(s(x), s(0)) -> s(quot(x, s(0))) [2] 39.22/13.78 quot(s(s(x')), s(s(y'))) -> s(quot(minus(x', y'), s(s(y')))) [2] 39.22/13.78 quot(s(x), s(y)) -> s(quot(0, s(y))) [1] 39.22/13.78 app(nil, y) -> y [1] 39.22/13.78 app(add(n, x), y) -> add(n, app(x, y)) [1] 39.22/13.78 reverse(nil) -> nil [1] 39.22/13.78 reverse(add(n, nil)) -> app(nil, add(n, nil)) [2] 39.22/13.78 reverse(add(n, add(n', x''))) -> app(app(reverse(x''), add(n', nil)), add(n, nil)) [2] 39.22/13.78 shuffle(nil) -> nil [1] 39.22/13.78 shuffle(add(n, nil)) -> add(n, shuffle(nil)) [2] 39.22/13.78 shuffle(add(n, add(n'', x1))) -> add(n, shuffle(app(reverse(x1), add(n'', nil)))) [2] 39.22/13.78 concat(leaf, y) -> y [1] 39.22/13.78 concat(cons(u, v), y) -> cons(u, concat(v, y)) [1] 39.22/13.78 less_leaves(x, leaf) -> false [1] 39.22/13.78 less_leaves(leaf, cons(w, z)) -> true [1] 39.22/13.78 less_leaves(cons(leaf, v), cons(leaf, z)) -> less_leaves(v, z) [3] 39.22/13.78 less_leaves(cons(leaf, v), cons(cons(u'', v''), z)) -> less_leaves(v, cons(u'', concat(v'', z))) [3] 39.22/13.78 less_leaves(cons(cons(u', v'), v), cons(leaf, z)) -> less_leaves(cons(u', concat(v', v)), z) [3] 39.22/13.78 less_leaves(cons(cons(u', v'), v), cons(cons(u1, v2), z)) -> less_leaves(cons(u', concat(v', v)), cons(u1, concat(v2, z))) [3] 39.22/13.78 minus(v0, v1) -> 0 [0] 39.22/13.78 39.22/13.78 The TRS has the following type information: 39.22/13.78 minus :: 0:s -> 0:s -> 0:s 39.22/13.78 0 :: 0:s 39.22/13.78 s :: 0:s -> 0:s 39.22/13.78 quot :: 0:s -> 0:s -> 0:s 39.22/13.78 app :: nil:add -> nil:add -> nil:add 39.22/13.78 nil :: nil:add 39.22/13.78 add :: a -> nil:add -> nil:add 39.22/13.78 reverse :: nil:add -> nil:add 39.22/13.78 shuffle :: nil:add -> nil:add 39.22/13.78 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.78 leaf :: leaf:cons 39.22/13.78 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.78 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.78 false :: false:true 39.22/13.78 true :: false:true 39.22/13.78 const :: a 39.22/13.78 39.22/13.78 Rewrite Strategy: INNERMOST 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 39.22/13.78 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 39.22/13.78 The constant constructors are abstracted as follows: 39.22/13.78 39.22/13.78 0 => 0 39.22/13.78 nil => 0 39.22/13.78 leaf => 0 39.22/13.78 false => 0 39.22/13.78 true => 1 39.22/13.78 const => 0 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (12) 39.22/13.78 Obligation: 39.22/13.78 Complexity RNTS consisting of the following rules: 39.22/13.78 39.22/13.78 app(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0 39.22/13.78 app(z', z'') -{ 1 }-> 1 + n + app(x, y) :|: n >= 0, z'' = y, z' = 1 + n + x, x >= 0, y >= 0 39.22/13.78 concat(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0 39.22/13.78 concat(z', z'') -{ 1 }-> 1 + u + concat(v, y) :|: v >= 0, z' = 1 + u + v, z'' = y, y >= 0, u >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(v, z) :|: v >= 0, z >= 0, z' = 1 + 0 + v, z'' = 1 + 0 + z 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(v, 1 + u'' + concat(v'', z)) :|: v >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, z' = 1 + 0 + v, v'' >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + 0 + z 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = x, x >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> x :|: z'' = 0, z' = x, x >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> minus(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 39.22/13.78 minus(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 39.22/13.78 quot(z', z'') -{ 1 }-> 0 :|: y >= 0, z'' = 1 + y, z' = 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(x, 1 + 0) :|: z' = 1 + x, x >= 0, z'' = 1 + 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(minus(x', y'), 1 + (1 + y')) :|: z' = 1 + (1 + x'), x' >= 0, z'' = 1 + (1 + y'), y' >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 39.22/13.78 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.78 reverse(z') -{ 2 }-> app(0, 1 + n + 0) :|: n >= 0, z' = 1 + n + 0 39.22/13.78 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.78 shuffle(z') -{ 2 }-> 1 + n + shuffle(0) :|: n >= 0, z' = 1 + n + 0 39.22/13.78 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 39.22/13.78 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (14) 39.22/13.78 Obligation: 39.22/13.78 Complexity RNTS consisting of the following rules: 39.22/13.78 39.22/13.78 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.78 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(minus(z' - 2, z'' - 2), 1 + (1 + (z'' - 2))) :|: z' - 2 >= 0, z'' - 2 >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.78 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.78 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.78 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.78 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.78 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 39.22/13.78 Found the following analysis order by SCC decomposition: 39.22/13.78 39.22/13.78 { minus } 39.22/13.78 { concat } 39.22/13.78 { app } 39.22/13.78 { quot } 39.22/13.78 { less_leaves } 39.22/13.78 { reverse } 39.22/13.78 { shuffle } 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (16) 39.22/13.78 Obligation: 39.22/13.78 Complexity RNTS consisting of the following rules: 39.22/13.78 39.22/13.78 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.78 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(minus(z' - 2, z'' - 2), 1 + (1 + (z'' - 2))) :|: z' - 2 >= 0, z'' - 2 >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.78 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.78 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.78 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.78 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.78 39.22/13.78 Function symbols to be analyzed: {minus}, {concat}, {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (17) ResultPropagationProof (UPPER BOUND(ID)) 39.22/13.78 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (18) 39.22/13.78 Obligation: 39.22/13.78 Complexity RNTS consisting of the following rules: 39.22/13.78 39.22/13.78 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.78 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(minus(z' - 2, z'' - 2), 1 + (1 + (z'' - 2))) :|: z' - 2 >= 0, z'' - 2 >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.78 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.78 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.78 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.78 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.78 39.22/13.78 Function symbols to be analyzed: {minus}, {concat}, {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (19) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.78 39.22/13.78 Computed SIZE bound using KoAT for: minus 39.22/13.78 after applying outer abstraction to obtain an ITS, 39.22/13.78 resulting in: O(n^1) with polynomial bound: z' 39.22/13.78 39.22/13.78 ---------------------------------------- 39.22/13.78 39.22/13.78 (20) 39.22/13.78 Obligation: 39.22/13.78 Complexity RNTS consisting of the following rules: 39.22/13.78 39.22/13.78 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.78 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.78 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.78 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.78 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.78 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(minus(z' - 2, z'' - 2), 1 + (1 + (z'' - 2))) :|: z' - 2 >= 0, z'' - 2 >= 0 39.22/13.78 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.78 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.78 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.78 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.78 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.78 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.78 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.79 39.22/13.79 Function symbols to be analyzed: {minus}, {concat}, {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.79 Previous analysis results are: 39.22/13.79 minus: runtime: ?, size: O(n^1) [z'] 39.22/13.79 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (21) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.79 39.22/13.79 Computed RUNTIME bound using CoFloCo for: minus 39.22/13.79 after applying outer abstraction to obtain an ITS, 39.22/13.79 resulting in: O(n^1) with polynomial bound: 1 + z'' 39.22/13.79 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (22) 39.22/13.79 Obligation: 39.22/13.79 Complexity RNTS consisting of the following rules: 39.22/13.79 39.22/13.79 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.79 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.79 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.79 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.79 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.79 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.79 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.79 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.79 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.79 quot(z', z'') -{ 2 }-> 1 + quot(minus(z' - 2, z'' - 2), 1 + (1 + (z'' - 2))) :|: z' - 2 >= 0, z'' - 2 >= 0 39.22/13.79 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.79 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.79 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.79 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.79 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.79 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.79 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.79 39.22/13.79 Function symbols to be analyzed: {concat}, {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.79 Previous analysis results are: 39.22/13.79 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.79 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (23) ResultPropagationProof (UPPER BOUND(ID)) 39.22/13.79 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (24) 39.22/13.79 Obligation: 39.22/13.79 Complexity RNTS consisting of the following rules: 39.22/13.79 39.22/13.79 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.79 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.79 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.79 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.79 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.79 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.79 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.79 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.79 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.79 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.79 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.79 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.79 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.79 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.79 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.79 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.79 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.79 39.22/13.79 Function symbols to be analyzed: {concat}, {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.79 Previous analysis results are: 39.22/13.79 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.79 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (25) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.79 39.22/13.79 Computed SIZE bound using CoFloCo for: concat 39.22/13.79 after applying outer abstraction to obtain an ITS, 39.22/13.79 resulting in: O(n^1) with polynomial bound: z' + z'' 39.22/13.79 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (26) 39.22/13.79 Obligation: 39.22/13.79 Complexity RNTS consisting of the following rules: 39.22/13.79 39.22/13.79 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.79 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.79 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.79 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.79 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.79 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.79 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.79 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.79 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.79 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.79 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.79 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.79 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.79 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.79 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.79 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.79 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.79 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.79 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.79 39.22/13.79 Function symbols to be analyzed: {concat}, {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.79 Previous analysis results are: 39.22/13.79 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.79 concat: runtime: ?, size: O(n^1) [z' + z''] 39.22/13.79 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (27) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.79 39.22/13.79 Computed RUNTIME bound using CoFloCo for: concat 39.22/13.79 after applying outer abstraction to obtain an ITS, 39.22/13.79 resulting in: O(n^1) with polynomial bound: 1 + z' 39.22/13.79 39.22/13.79 ---------------------------------------- 39.22/13.79 39.22/13.79 (28) 39.22/13.79 Obligation: 39.22/13.79 Complexity RNTS consisting of the following rules: 39.22/13.79 39.22/13.79 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 1 }-> 1 + u + concat(v, z'') :|: v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, 1 + u'' + concat(v'', z)) :|: z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), z'' - 1) :|: v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(1 + u' + concat(v', v), 1 + u1 + concat(v2, z)) :|: v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (29) ResultPropagationProof (UPPER BOUND(ID)) 39.22/13.80 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (30) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (31) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed SIZE bound using CoFloCo for: app 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^1) with polynomial bound: z' + z'' 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (32) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {app}, {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: ?, size: O(n^1) [z' + z''] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (33) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed RUNTIME bound using CoFloCo for: app 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^1) with polynomial bound: 1 + z' 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (34) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 1 }-> 1 + n + app(x, z'') :|: n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(0, 1 + (z' - 1) + 0) :|: z' - 1 >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (35) ResultPropagationProof (UPPER BOUND(ID)) 39.22/13.80 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (36) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (37) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed SIZE bound using KoAT for: quot 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^1) with polynomial bound: z' 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (38) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {quot}, {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: ?, size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (39) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed RUNTIME bound using CoFloCo for: quot 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^2) with polynomial bound: 4 + 2*z' + z'*z'' + z'' 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (40) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 1 + z'' }-> 1 + quot(s', 1 + (1 + (z'' - 2))) :|: s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 1 + quot(0, 1 + (z'' - 1)) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 quot(z', z'') -{ 2 }-> 1 + quot(z' - 1, 1 + 0) :|: z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (41) ResultPropagationProof (UPPER BOUND(ID)) 39.22/13.80 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (42) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (43) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed SIZE bound using CoFloCo for: less_leaves 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(1) with polynomial bound: 1 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (44) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {less_leaves}, {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: ?, size: O(1) [1] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (45) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed RUNTIME bound using CoFloCo for: less_leaves 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^2) with polynomial bound: 1 + 3*z' + z'*z'' + z'^2 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (46) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 }-> less_leaves(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v'' }-> less_leaves(z' - 1, 1 + u'' + s1) :|: s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 4 + v' }-> less_leaves(1 + u' + s2, z'' - 1) :|: s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 5 + v' + v2 }-> less_leaves(1 + u' + s3, 1 + u1 + s4) :|: s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: O(n^2) [1 + 3*z' + z'*z'' + z'^2], size: O(1) [1] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (47) ResultPropagationProof (UPPER BOUND(ID)) 39.22/13.80 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (48) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 + z'*z'' + z'^2 + -1*z'' }-> s10 :|: s10 >= 0, s10 <= 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 2 + -1*s1 + s1*z' + -1*u'' + u''*z' + v'' + 2*z' + z'^2 }-> s11 :|: s11 >= 0, s11 <= 1, s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 8 + 4*s2 + 2*s2*u' + s2*z'' + s2^2 + 4*u' + u'*z'' + u'^2 + v' + z'' }-> s12 :|: s12 >= 0, s12 <= 1, s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 11 + 6*s3 + s3*s4 + 2*s3*u' + s3*u1 + s3^2 + s4 + s4*u' + 6*u' + u'*u1 + u'^2 + u1 + v' + v2 }-> s13 :|: s13 >= 0, s13 <= 1, s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: O(n^2) [1 + 3*z' + z'*z'' + z'^2], size: O(1) [1] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (49) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed SIZE bound using CoFloCo for: reverse 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^1) with polynomial bound: z' 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (50) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 + z'*z'' + z'^2 + -1*z'' }-> s10 :|: s10 >= 0, s10 <= 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 2 + -1*s1 + s1*z' + -1*u'' + u''*z' + v'' + 2*z' + z'^2 }-> s11 :|: s11 >= 0, s11 <= 1, s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 8 + 4*s2 + 2*s2*u' + s2*z'' + s2^2 + 4*u' + u'*z'' + u'^2 + v' + z'' }-> s12 :|: s12 >= 0, s12 <= 1, s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 11 + 6*s3 + s3*s4 + 2*s3*u' + s3*u1 + s3^2 + s4 + s4*u' + 6*u' + u'*u1 + u'^2 + u1 + v' + v2 }-> s13 :|: s13 >= 0, s13 <= 1, s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {reverse}, {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: O(n^2) [1 + 3*z' + z'*z'' + z'^2], size: O(1) [1] 39.22/13.80 reverse: runtime: ?, size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (51) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed RUNTIME bound using CoFloCo for: reverse 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^2) with polynomial bound: 4 + 3*z' + 2*z'^2 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (52) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 + z'*z'' + z'^2 + -1*z'' }-> s10 :|: s10 >= 0, s10 <= 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 2 + -1*s1 + s1*z' + -1*u'' + u''*z' + v'' + 2*z' + z'^2 }-> s11 :|: s11 >= 0, s11 <= 1, s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 8 + 4*s2 + 2*s2*u' + s2*z'' + s2^2 + 4*u' + u'*z'' + u'^2 + v' + z'' }-> s12 :|: s12 >= 0, s12 <= 1, s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 11 + 6*s3 + s3*s4 + 2*s3*u' + s3*u1 + s3^2 + s4 + s4*u' + 6*u' + u'*u1 + u'^2 + u1 + v' + v2 }-> s13 :|: s13 >= 0, s13 <= 1, s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 2 }-> app(app(reverse(x''), 1 + n' + 0), 1 + n + 0) :|: n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 2 }-> 1 + n + shuffle(app(reverse(x1), 1 + n'' + 0)) :|: n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: O(n^2) [1 + 3*z' + z'*z'' + z'^2], size: O(1) [1] 39.22/13.80 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (53) ResultPropagationProof (UPPER BOUND(ID)) 39.22/13.80 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (54) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 + z'*z'' + z'^2 + -1*z'' }-> s10 :|: s10 >= 0, s10 <= 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 2 + -1*s1 + s1*z' + -1*u'' + u''*z' + v'' + 2*z' + z'^2 }-> s11 :|: s11 >= 0, s11 <= 1, s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 8 + 4*s2 + 2*s2*u' + s2*z'' + s2^2 + 4*u' + u'*z'' + u'^2 + v' + z'' }-> s12 :|: s12 >= 0, s12 <= 1, s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 11 + 6*s3 + s3*s4 + 2*s3*u' + s3*u1 + s3^2 + s4 + s4*u' + 6*u' + u'*u1 + u'^2 + u1 + v' + v2 }-> s13 :|: s13 >= 0, s13 <= 1, s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 8 + s14 + s15 + 3*x'' + 2*x''^2 }-> s16 :|: s14 >= 0, s14 <= x'', s15 >= 0, s15 <= s14 + (1 + n' + 0), s16 >= 0, s16 <= s15 + (1 + n + 0), n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 7 + s17 + 3*x1 + 2*x1^2 }-> 1 + n + shuffle(s18) :|: s17 >= 0, s17 <= x1, s18 >= 0, s18 <= s17 + (1 + n'' + 0), n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: O(n^2) [1 + 3*z' + z'*z'' + z'^2], size: O(1) [1] 39.22/13.80 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (55) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed SIZE bound using KoAT for: shuffle 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^1) with polynomial bound: z' 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (56) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 + z'*z'' + z'^2 + -1*z'' }-> s10 :|: s10 >= 0, s10 <= 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 2 + -1*s1 + s1*z' + -1*u'' + u''*z' + v'' + 2*z' + z'^2 }-> s11 :|: s11 >= 0, s11 <= 1, s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 8 + 4*s2 + 2*s2*u' + s2*z'' + s2^2 + 4*u' + u'*z'' + u'^2 + v' + z'' }-> s12 :|: s12 >= 0, s12 <= 1, s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 11 + 6*s3 + s3*s4 + 2*s3*u' + s3*u1 + s3^2 + s4 + s4*u' + 6*u' + u'*u1 + u'^2 + u1 + v' + v2 }-> s13 :|: s13 >= 0, s13 <= 1, s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 8 + s14 + s15 + 3*x'' + 2*x''^2 }-> s16 :|: s14 >= 0, s14 <= x'', s15 >= 0, s15 <= s14 + (1 + n' + 0), s16 >= 0, s16 <= s15 + (1 + n + 0), n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 7 + s17 + 3*x1 + 2*x1^2 }-> 1 + n + shuffle(s18) :|: s17 >= 0, s17 <= x1, s18 >= 0, s18 <= s17 + (1 + n'' + 0), n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: {shuffle} 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: O(n^2) [1 + 3*z' + z'*z'' + z'^2], size: O(1) [1] 39.22/13.80 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 39.22/13.80 shuffle: runtime: ?, size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (57) IntTrsBoundProof (UPPER BOUND(ID)) 39.22/13.80 39.22/13.80 Computed RUNTIME bound using KoAT for: shuffle 39.22/13.80 after applying outer abstraction to obtain an ITS, 39.22/13.80 resulting in: O(n^3) with polynomial bound: 1 + 9*z' + 4*z'^2 + 2*z'^3 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (58) 39.22/13.80 Obligation: 39.22/13.80 Complexity RNTS consisting of the following rules: 39.22/13.80 39.22/13.80 app(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 app(z', z'') -{ 2 + x }-> 1 + n + s5 :|: s5 >= 0, s5 <= x + z'', n >= 0, z' = 1 + n + x, x >= 0, z'' >= 0 39.22/13.80 concat(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 39.22/13.80 concat(z', z'') -{ 2 + v }-> 1 + u + s'' :|: s'' >= 0, s'' <= v + z'', v >= 0, z' = 1 + u + v, z'' >= 0, u >= 0 39.22/13.80 less_leaves(z', z'') -{ 3 + z'*z'' + z'^2 + -1*z'' }-> s10 :|: s10 >= 0, s10 <= 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 less_leaves(z', z'') -{ 2 + -1*s1 + s1*z' + -1*u'' + u''*z' + v'' + 2*z' + z'^2 }-> s11 :|: s11 >= 0, s11 <= 1, s1 >= 0, s1 <= v'' + z, z' - 1 >= 0, z >= 0, z'' = 1 + (1 + u'' + v'') + z, u'' >= 0, v'' >= 0 39.22/13.80 less_leaves(z', z'') -{ 8 + 4*s2 + 2*s2*u' + s2*z'' + s2^2 + 4*u' + u'*z'' + u'^2 + v' + z'' }-> s12 :|: s12 >= 0, s12 <= 1, s2 >= 0, s2 <= v' + v, v >= 0, z'' - 1 >= 0, u' >= 0, v' >= 0, z' = 1 + (1 + u' + v') + v 39.22/13.80 less_leaves(z', z'') -{ 11 + 6*s3 + s3*s4 + 2*s3*u' + s3*u1 + s3^2 + s4 + s4*u' + 6*u' + u'*u1 + u'^2 + u1 + v' + v2 }-> s13 :|: s13 >= 0, s13 <= 1, s3 >= 0, s3 <= v' + v, s4 >= 0, s4 <= v2 + z, v >= 0, z >= 0, u' >= 0, v' >= 0, u1 >= 0, z' = 1 + (1 + u' + v') + v, z'' = 1 + (1 + u1 + v2) + z, v2 >= 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 1 :|: z >= 0, z'' = 1 + w + z, w >= 0, z' = 0 39.22/13.80 less_leaves(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 1 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 39.22/13.80 minus(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 39.22/13.80 quot(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 39.22/13.80 quot(z', z'') -{ 4 + 3*z' }-> 1 + s7 :|: s7 >= 0, s7 <= z' - 1, z' - 1 >= 0, z'' = 1 + 0 39.22/13.80 quot(z', z'') -{ 5 + 2*s' + s'*z'' + 2*z'' }-> 1 + s8 :|: s8 >= 0, s8 <= s', s' >= 0, s' <= z' - 2, z' - 2 >= 0, z'' - 2 >= 0 39.22/13.80 quot(z', z'') -{ 5 + z'' }-> 1 + s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z'' - 1 >= 0 39.22/13.80 reverse(z') -{ 8 + s14 + s15 + 3*x'' + 2*x''^2 }-> s16 :|: s14 >= 0, s14 <= x'', s15 >= 0, s15 <= s14 + (1 + n' + 0), s16 >= 0, s16 <= s15 + (1 + n + 0), n >= 0, n' >= 0, z' = 1 + n + (1 + n' + x''), x'' >= 0 39.22/13.80 reverse(z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + (1 + (z' - 1) + 0), z' - 1 >= 0 39.22/13.80 reverse(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 1 }-> 0 :|: z' = 0 39.22/13.80 shuffle(z') -{ 7 + s17 + 3*x1 + 2*x1^2 }-> 1 + n + shuffle(s18) :|: s17 >= 0, s17 <= x1, s18 >= 0, s18 <= s17 + (1 + n'' + 0), n >= 0, x1 >= 0, n'' >= 0, z' = 1 + n + (1 + n'' + x1) 39.22/13.80 shuffle(z') -{ 2 }-> 1 + (z' - 1) + shuffle(0) :|: z' - 1 >= 0 39.22/13.80 39.22/13.80 Function symbols to be analyzed: 39.22/13.80 Previous analysis results are: 39.22/13.80 minus: runtime: O(n^1) [1 + z''], size: O(n^1) [z'] 39.22/13.80 concat: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 app: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 39.22/13.80 quot: runtime: O(n^2) [4 + 2*z' + z'*z'' + z''], size: O(n^1) [z'] 39.22/13.80 less_leaves: runtime: O(n^2) [1 + 3*z' + z'*z'' + z'^2], size: O(1) [1] 39.22/13.80 reverse: runtime: O(n^2) [4 + 3*z' + 2*z'^2], size: O(n^1) [z'] 39.22/13.80 shuffle: runtime: O(n^3) [1 + 9*z' + 4*z'^2 + 2*z'^3], size: O(n^1) [z'] 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (59) FinalProof (FINISHED) 39.22/13.80 Computed overall runtime complexity 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (60) 39.22/13.80 BOUNDS(1, n^3) 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (61) RenamingProof (BOTH BOUNDS(ID, ID)) 39.22/13.80 Renamed function symbols to avoid clashes with predefined symbol. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (62) 39.22/13.80 Obligation: 39.22/13.80 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 39.22/13.80 39.22/13.80 39.22/13.80 The TRS R consists of the following rules: 39.22/13.80 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(n, x), y) -> add(n, app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(n, x)) -> add(n, shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 S is empty. 39.22/13.80 Rewrite Strategy: FULL 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (63) SlicingProof (LOWER BOUND(ID)) 39.22/13.80 Sliced the following arguments: 39.22/13.80 add/0 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (64) 39.22/13.80 Obligation: 39.22/13.80 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 39.22/13.80 39.22/13.80 39.22/13.80 The TRS R consists of the following rules: 39.22/13.80 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 S is empty. 39.22/13.80 Rewrite Strategy: FULL 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (65) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 39.22/13.80 Infered types. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (66) 39.22/13.80 Obligation: 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (67) OrderProof (LOWER BOUND(ID)) 39.22/13.80 Heuristically decided to analyse the following defined symbols: 39.22/13.80 minus, quot, app, reverse, shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 minus < quot 39.22/13.80 app < reverse 39.22/13.80 reverse < shuffle 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (68) 39.22/13.80 Obligation: 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 minus, quot, app, reverse, shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 minus < quot 39.22/13.80 app < reverse 39.22/13.80 reverse < shuffle 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (69) RewriteLemmaProof (LOWER BOUND(ID)) 39.22/13.80 Proved the following rewrite lemma: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 39.22/13.80 Induction Base: 39.22/13.80 minus(gen_0':s5_0(0), gen_0':s5_0(0)) ->_R^Omega(1) 39.22/13.80 gen_0':s5_0(0) 39.22/13.80 39.22/13.80 Induction Step: 39.22/13.80 minus(gen_0':s5_0(+(n9_0, 1)), gen_0':s5_0(+(n9_0, 1))) ->_R^Omega(1) 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) ->_IH 39.22/13.80 gen_0':s5_0(0) 39.22/13.80 39.22/13.80 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (70) 39.22/13.80 Complex Obligation (BEST) 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (71) 39.22/13.80 Obligation: 39.22/13.80 Proved the lower bound n^1 for the following obligation: 39.22/13.80 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 minus, quot, app, reverse, shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 minus < quot 39.22/13.80 app < reverse 39.22/13.80 reverse < shuffle 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (72) LowerBoundPropagationProof (FINISHED) 39.22/13.80 Propagated lower bound. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (73) 39.22/13.80 BOUNDS(n^1, INF) 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (74) 39.22/13.80 Obligation: 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Lemmas: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 quot, app, reverse, shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 app < reverse 39.22/13.80 reverse < shuffle 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (75) RewriteLemmaProof (LOWER BOUND(ID)) 39.22/13.80 Proved the following rewrite lemma: 39.22/13.80 app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b)) -> gen_nil:add6_0(+(n589_0, b)), rt in Omega(1 + n589_0) 39.22/13.80 39.22/13.80 Induction Base: 39.22/13.80 app(gen_nil:add6_0(0), gen_nil:add6_0(b)) ->_R^Omega(1) 39.22/13.80 gen_nil:add6_0(b) 39.22/13.80 39.22/13.80 Induction Step: 39.22/13.80 app(gen_nil:add6_0(+(n589_0, 1)), gen_nil:add6_0(b)) ->_R^Omega(1) 39.22/13.80 add(app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b))) ->_IH 39.22/13.80 add(gen_nil:add6_0(+(b, c590_0))) 39.22/13.80 39.22/13.80 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (76) 39.22/13.80 Obligation: 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Lemmas: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b)) -> gen_nil:add6_0(+(n589_0, b)), rt in Omega(1 + n589_0) 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 reverse, shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 reverse < shuffle 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (77) RewriteLemmaProof (LOWER BOUND(ID)) 39.22/13.80 Proved the following rewrite lemma: 39.22/13.80 reverse(gen_nil:add6_0(n1508_0)) -> gen_nil:add6_0(n1508_0), rt in Omega(1 + n1508_0 + n1508_0^2) 39.22/13.80 39.22/13.80 Induction Base: 39.22/13.80 reverse(gen_nil:add6_0(0)) ->_R^Omega(1) 39.22/13.80 nil 39.22/13.80 39.22/13.80 Induction Step: 39.22/13.80 reverse(gen_nil:add6_0(+(n1508_0, 1))) ->_R^Omega(1) 39.22/13.80 app(reverse(gen_nil:add6_0(n1508_0)), add(nil)) ->_IH 39.22/13.80 app(gen_nil:add6_0(c1509_0), add(nil)) ->_L^Omega(1 + n1508_0) 39.22/13.80 gen_nil:add6_0(+(n1508_0, +(0, 1))) 39.22/13.80 39.22/13.80 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (78) 39.22/13.80 Complex Obligation (BEST) 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (79) 39.22/13.80 Obligation: 39.22/13.80 Proved the lower bound n^2 for the following obligation: 39.22/13.80 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Lemmas: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b)) -> gen_nil:add6_0(+(n589_0, b)), rt in Omega(1 + n589_0) 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 reverse, shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 reverse < shuffle 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (80) LowerBoundPropagationProof (FINISHED) 39.22/13.80 Propagated lower bound. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (81) 39.22/13.80 BOUNDS(n^2, INF) 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (82) 39.22/13.80 Obligation: 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Lemmas: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b)) -> gen_nil:add6_0(+(n589_0, b)), rt in Omega(1 + n589_0) 39.22/13.80 reverse(gen_nil:add6_0(n1508_0)) -> gen_nil:add6_0(n1508_0), rt in Omega(1 + n1508_0 + n1508_0^2) 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (83) RewriteLemmaProof (LOWER BOUND(ID)) 39.22/13.80 Proved the following rewrite lemma: 39.22/13.80 shuffle(gen_nil:add6_0(n1776_0)) -> gen_nil:add6_0(n1776_0), rt in Omega(1 + n1776_0 + n1776_0^2 + n1776_0^3) 39.22/13.80 39.22/13.80 Induction Base: 39.22/13.80 shuffle(gen_nil:add6_0(0)) ->_R^Omega(1) 39.22/13.80 nil 39.22/13.80 39.22/13.80 Induction Step: 39.22/13.80 shuffle(gen_nil:add6_0(+(n1776_0, 1))) ->_R^Omega(1) 39.22/13.80 add(shuffle(reverse(gen_nil:add6_0(n1776_0)))) ->_L^Omega(1 + n1776_0 + n1776_0^2) 39.22/13.80 add(shuffle(gen_nil:add6_0(n1776_0))) ->_IH 39.22/13.80 add(gen_nil:add6_0(c1777_0)) 39.22/13.80 39.22/13.80 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (84) 39.22/13.80 Complex Obligation (BEST) 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (85) 39.22/13.80 Obligation: 39.22/13.80 Proved the lower bound n^3 for the following obligation: 39.22/13.80 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Lemmas: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b)) -> gen_nil:add6_0(+(n589_0, b)), rt in Omega(1 + n589_0) 39.22/13.80 reverse(gen_nil:add6_0(n1508_0)) -> gen_nil:add6_0(n1508_0), rt in Omega(1 + n1508_0 + n1508_0^2) 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 shuffle, concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (86) LowerBoundPropagationProof (FINISHED) 39.22/13.80 Propagated lower bound. 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (87) 39.22/13.80 BOUNDS(n^3, INF) 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (88) 39.22/13.80 Obligation: 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Lemmas: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b)) -> gen_nil:add6_0(+(n589_0, b)), rt in Omega(1 + n589_0) 39.22/13.80 reverse(gen_nil:add6_0(n1508_0)) -> gen_nil:add6_0(n1508_0), rt in Omega(1 + n1508_0 + n1508_0^2) 39.22/13.80 shuffle(gen_nil:add6_0(n1776_0)) -> gen_nil:add6_0(n1776_0), rt in Omega(1 + n1776_0 + n1776_0^2 + n1776_0^3) 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 concat, less_leaves 39.22/13.80 39.22/13.80 They will be analysed ascendingly in the following order: 39.22/13.80 concat < less_leaves 39.22/13.80 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (89) RewriteLemmaProof (LOWER BOUND(ID)) 39.22/13.80 Proved the following rewrite lemma: 39.22/13.80 concat(gen_leaf:cons7_0(n1977_0), gen_leaf:cons7_0(b)) -> gen_leaf:cons7_0(+(n1977_0, b)), rt in Omega(1 + n1977_0) 39.22/13.80 39.22/13.80 Induction Base: 39.22/13.80 concat(gen_leaf:cons7_0(0), gen_leaf:cons7_0(b)) ->_R^Omega(1) 39.22/13.80 gen_leaf:cons7_0(b) 39.22/13.80 39.22/13.80 Induction Step: 39.22/13.80 concat(gen_leaf:cons7_0(+(n1977_0, 1)), gen_leaf:cons7_0(b)) ->_R^Omega(1) 39.22/13.80 cons(leaf, concat(gen_leaf:cons7_0(n1977_0), gen_leaf:cons7_0(b))) ->_IH 39.22/13.80 cons(leaf, gen_leaf:cons7_0(+(b, c1978_0))) 39.22/13.80 39.22/13.80 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (90) 39.22/13.80 Obligation: 39.22/13.80 TRS: 39.22/13.80 Rules: 39.22/13.80 minus(x, 0') -> x 39.22/13.80 minus(s(x), s(y)) -> minus(x, y) 39.22/13.80 quot(0', s(y)) -> 0' 39.22/13.80 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 39.22/13.80 app(nil, y) -> y 39.22/13.80 app(add(x), y) -> add(app(x, y)) 39.22/13.80 reverse(nil) -> nil 39.22/13.80 reverse(add(x)) -> app(reverse(x), add(nil)) 39.22/13.80 shuffle(nil) -> nil 39.22/13.80 shuffle(add(x)) -> add(shuffle(reverse(x))) 39.22/13.80 concat(leaf, y) -> y 39.22/13.80 concat(cons(u, v), y) -> cons(u, concat(v, y)) 39.22/13.80 less_leaves(x, leaf) -> false 39.22/13.80 less_leaves(leaf, cons(w, z)) -> true 39.22/13.80 less_leaves(cons(u, v), cons(w, z)) -> less_leaves(concat(u, v), concat(w, z)) 39.22/13.80 39.22/13.80 Types: 39.22/13.80 minus :: 0':s -> 0':s -> 0':s 39.22/13.80 0' :: 0':s 39.22/13.80 s :: 0':s -> 0':s 39.22/13.80 quot :: 0':s -> 0':s -> 0':s 39.22/13.80 app :: nil:add -> nil:add -> nil:add 39.22/13.80 nil :: nil:add 39.22/13.80 add :: nil:add -> nil:add 39.22/13.80 reverse :: nil:add -> nil:add 39.22/13.80 shuffle :: nil:add -> nil:add 39.22/13.80 concat :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 leaf :: leaf:cons 39.22/13.80 cons :: leaf:cons -> leaf:cons -> leaf:cons 39.22/13.80 less_leaves :: leaf:cons -> leaf:cons -> false:true 39.22/13.80 false :: false:true 39.22/13.80 true :: false:true 39.22/13.80 hole_0':s1_0 :: 0':s 39.22/13.80 hole_nil:add2_0 :: nil:add 39.22/13.80 hole_leaf:cons3_0 :: leaf:cons 39.22/13.80 hole_false:true4_0 :: false:true 39.22/13.80 gen_0':s5_0 :: Nat -> 0':s 39.22/13.80 gen_nil:add6_0 :: Nat -> nil:add 39.22/13.80 gen_leaf:cons7_0 :: Nat -> leaf:cons 39.22/13.80 39.22/13.80 39.22/13.80 Lemmas: 39.22/13.80 minus(gen_0':s5_0(n9_0), gen_0':s5_0(n9_0)) -> gen_0':s5_0(0), rt in Omega(1 + n9_0) 39.22/13.80 app(gen_nil:add6_0(n589_0), gen_nil:add6_0(b)) -> gen_nil:add6_0(+(n589_0, b)), rt in Omega(1 + n589_0) 39.22/13.80 reverse(gen_nil:add6_0(n1508_0)) -> gen_nil:add6_0(n1508_0), rt in Omega(1 + n1508_0 + n1508_0^2) 39.22/13.80 shuffle(gen_nil:add6_0(n1776_0)) -> gen_nil:add6_0(n1776_0), rt in Omega(1 + n1776_0 + n1776_0^2 + n1776_0^3) 39.22/13.80 concat(gen_leaf:cons7_0(n1977_0), gen_leaf:cons7_0(b)) -> gen_leaf:cons7_0(+(n1977_0, b)), rt in Omega(1 + n1977_0) 39.22/13.80 39.22/13.80 39.22/13.80 Generator Equations: 39.22/13.80 gen_0':s5_0(0) <=> 0' 39.22/13.80 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 39.22/13.80 gen_nil:add6_0(0) <=> nil 39.22/13.80 gen_nil:add6_0(+(x, 1)) <=> add(gen_nil:add6_0(x)) 39.22/13.80 gen_leaf:cons7_0(0) <=> leaf 39.22/13.80 gen_leaf:cons7_0(+(x, 1)) <=> cons(leaf, gen_leaf:cons7_0(x)) 39.22/13.80 39.22/13.80 39.22/13.80 The following defined symbols remain to be analysed: 39.22/13.80 less_leaves 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (91) RewriteLemmaProof (LOWER BOUND(ID)) 39.22/13.80 Proved the following rewrite lemma: 39.22/13.80 less_leaves(gen_leaf:cons7_0(n3068_0), gen_leaf:cons7_0(n3068_0)) -> false, rt in Omega(1 + n3068_0) 39.22/13.80 39.22/13.80 Induction Base: 39.22/13.80 less_leaves(gen_leaf:cons7_0(0), gen_leaf:cons7_0(0)) ->_R^Omega(1) 39.22/13.80 false 39.22/13.80 39.22/13.80 Induction Step: 39.22/13.80 less_leaves(gen_leaf:cons7_0(+(n3068_0, 1)), gen_leaf:cons7_0(+(n3068_0, 1))) ->_R^Omega(1) 39.22/13.80 less_leaves(concat(leaf, gen_leaf:cons7_0(n3068_0)), concat(leaf, gen_leaf:cons7_0(n3068_0))) ->_L^Omega(1) 39.22/13.80 less_leaves(gen_leaf:cons7_0(+(0, n3068_0)), concat(leaf, gen_leaf:cons7_0(n3068_0))) ->_L^Omega(1) 39.22/13.80 less_leaves(gen_leaf:cons7_0(n3068_0), gen_leaf:cons7_0(+(0, n3068_0))) ->_IH 39.22/13.80 false 39.22/13.80 39.22/13.80 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 39.22/13.80 ---------------------------------------- 39.22/13.80 39.22/13.80 (92) 39.22/13.80 BOUNDS(1, INF) 39.44/13.84 EOF