1116.06/291.73 WORST_CASE(Omega(n^2), O(n^3)) 1118.42/292.35 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1118.42/292.35 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1118.42/292.35 1118.42/292.35 1118.42/292.35 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3). 1118.42/292.35 1118.42/292.35 (0) CpxTRS 1118.42/292.35 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.42/292.35 (2) CpxWeightedTrs 1118.42/292.35 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.42/292.35 (4) CpxTypedWeightedTrs 1118.42/292.35 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1118.42/292.35 (6) CpxTypedWeightedCompleteTrs 1118.42/292.35 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.42/292.35 (8) CpxTypedWeightedCompleteTrs 1118.42/292.35 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1118.42/292.35 (10) CpxRNTS 1118.42/292.35 (11) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.42/292.35 (12) CpxRNTS 1118.42/292.35 (13) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.42/292.35 (14) CpxRNTS 1118.42/292.35 (15) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1118.42/292.35 (16) CpxRNTS 1118.42/292.35 (17) IntTrsBoundProof [UPPER BOUND(ID), 295 ms] 1118.42/292.35 (18) CpxRNTS 1118.42/292.35 (19) IntTrsBoundProof [UPPER BOUND(ID), 189 ms] 1118.42/292.35 (20) CpxRNTS 1118.42/292.35 (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1118.42/292.35 (22) CpxRNTS 1118.42/292.35 (23) IntTrsBoundProof [UPPER BOUND(ID), 473 ms] 1118.42/292.35 (24) CpxRNTS 1118.42/292.35 (25) IntTrsBoundProof [UPPER BOUND(ID), 156 ms] 1118.42/292.35 (26) CpxRNTS 1118.42/292.35 (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1118.42/292.35 (28) CpxRNTS 1118.42/292.35 (29) IntTrsBoundProof [UPPER BOUND(ID), 766 ms] 1118.42/292.35 (30) CpxRNTS 1118.42/292.35 (31) IntTrsBoundProof [UPPER BOUND(ID), 263 ms] 1118.42/292.35 (32) CpxRNTS 1118.42/292.35 (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1118.42/292.35 (34) CpxRNTS 1118.42/292.35 (35) IntTrsBoundProof [UPPER BOUND(ID), 861 ms] 1118.42/292.35 (36) CpxRNTS 1118.42/292.35 (37) IntTrsBoundProof [UPPER BOUND(ID), 211 ms] 1118.42/292.35 (38) CpxRNTS 1118.42/292.35 (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1118.42/292.35 (40) CpxRNTS 1118.42/292.35 (41) IntTrsBoundProof [UPPER BOUND(ID), 1318 ms] 1118.42/292.35 (42) CpxRNTS 1118.42/292.35 (43) IntTrsBoundProof [UPPER BOUND(ID), 565 ms] 1118.42/292.35 (44) CpxRNTS 1118.42/292.35 (45) FinalProof [FINISHED, 0 ms] 1118.42/292.35 (46) BOUNDS(1, n^3) 1118.42/292.35 (47) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.42/292.35 (48) CpxTRS 1118.42/292.35 (49) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.42/292.35 (50) typed CpxTrs 1118.42/292.35 (51) OrderProof [LOWER BOUND(ID), 5 ms] 1118.42/292.35 (52) typed CpxTrs 1118.42/292.35 (53) RewriteLemmaProof [LOWER BOUND(ID), 261 ms] 1118.42/292.35 (54) BEST 1118.42/292.35 (55) proven lower bound 1118.42/292.35 (56) LowerBoundPropagationProof [FINISHED, 0 ms] 1118.42/292.35 (57) BOUNDS(n^1, INF) 1118.42/292.35 (58) typed CpxTrs 1118.42/292.35 (59) RewriteLemmaProof [LOWER BOUND(ID), 47 ms] 1118.42/292.35 (60) typed CpxTrs 1118.42/292.35 (61) RewriteLemmaProof [LOWER BOUND(ID), 5 ms] 1118.42/292.35 (62) typed CpxTrs 1118.42/292.35 (63) RewriteLemmaProof [LOWER BOUND(ID), 66 ms] 1118.42/292.35 (64) proven lower bound 1118.42/292.35 (65) LowerBoundPropagationProof [FINISHED, 0 ms] 1118.42/292.35 (66) BOUNDS(n^2, INF) 1118.42/292.35 1118.42/292.35 1118.42/292.35 ---------------------------------------- 1118.42/292.35 1118.42/292.35 (0) 1118.42/292.35 Obligation: 1118.42/292.35 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3). 1118.42/292.35 1118.42/292.35 1118.42/292.35 The TRS R consists of the following rules: 1118.42/292.35 1118.42/292.35 eq(0, 0) -> true 1118.42/292.35 eq(0, s(Y)) -> false 1118.42/292.35 eq(s(X), 0) -> false 1118.42/292.35 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.35 le(0, Y) -> true 1118.42/292.35 le(s(X), 0) -> false 1118.42/292.35 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.35 min(cons(0, nil)) -> 0 1118.42/292.35 min(cons(s(N), nil)) -> s(N) 1118.42/292.35 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.35 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.35 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.35 replace(N, M, nil) -> nil 1118.42/292.35 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.35 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.35 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.35 selsort(nil) -> nil 1118.42/292.35 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.35 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.35 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.35 1118.42/292.35 S is empty. 1118.42/292.35 Rewrite Strategy: INNERMOST 1118.42/292.35 ---------------------------------------- 1118.42/292.35 1118.42/292.35 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1118.42/292.35 Transformed relative TRS to weighted TRS 1118.42/292.35 ---------------------------------------- 1118.42/292.35 1118.42/292.35 (2) 1118.42/292.35 Obligation: 1118.42/292.35 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 1118.42/292.35 1118.42/292.35 1118.42/292.35 The TRS R consists of the following rules: 1118.42/292.35 1118.42/292.35 eq(0, 0) -> true [1] 1118.42/292.35 eq(0, s(Y)) -> false [1] 1118.42/292.35 eq(s(X), 0) -> false [1] 1118.42/292.35 eq(s(X), s(Y)) -> eq(X, Y) [1] 1118.42/292.35 le(0, Y) -> true [1] 1118.42/292.35 le(s(X), 0) -> false [1] 1118.42/292.35 le(s(X), s(Y)) -> le(X, Y) [1] 1118.42/292.35 min(cons(0, nil)) -> 0 [1] 1118.42/292.35 min(cons(s(N), nil)) -> s(N) [1] 1118.42/292.35 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) [1] 1118.42/292.35 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) [1] 1118.42/292.35 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) [1] 1118.42/292.35 replace(N, M, nil) -> nil [1] 1118.42/292.35 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) [1] 1118.42/292.35 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) [1] 1118.42/292.35 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) [1] 1118.42/292.35 selsort(nil) -> nil [1] 1118.42/292.35 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) [1] 1118.42/292.35 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) [1] 1118.42/292.35 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) [1] 1118.42/292.35 1118.42/292.35 Rewrite Strategy: INNERMOST 1118.42/292.35 ---------------------------------------- 1118.42/292.35 1118.42/292.35 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1118.42/292.35 Infered types. 1118.42/292.35 ---------------------------------------- 1118.42/292.35 1118.42/292.35 (4) 1118.42/292.35 Obligation: 1118.42/292.35 Runtime Complexity Weighted TRS with Types. 1118.42/292.35 The TRS R consists of the following rules: 1118.42/292.35 1118.42/292.35 eq(0, 0) -> true [1] 1118.42/292.35 eq(0, s(Y)) -> false [1] 1118.42/292.35 eq(s(X), 0) -> false [1] 1118.42/292.35 eq(s(X), s(Y)) -> eq(X, Y) [1] 1118.42/292.35 le(0, Y) -> true [1] 1118.42/292.35 le(s(X), 0) -> false [1] 1118.42/292.35 le(s(X), s(Y)) -> le(X, Y) [1] 1118.42/292.35 min(cons(0, nil)) -> 0 [1] 1118.42/292.35 min(cons(s(N), nil)) -> s(N) [1] 1118.42/292.35 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) [1] 1118.42/292.35 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) [1] 1118.42/292.35 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) [1] 1118.42/292.35 replace(N, M, nil) -> nil [1] 1118.42/292.35 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) [1] 1118.42/292.35 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) [1] 1118.42/292.35 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) [1] 1118.42/292.35 selsort(nil) -> nil [1] 1118.42/292.35 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) [1] 1118.42/292.35 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) [1] 1118.42/292.35 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) [1] 1118.42/292.35 1118.42/292.35 The TRS has the following type information: 1118.42/292.35 eq :: 0:s -> 0:s -> true:false 1118.42/292.35 0 :: 0:s 1118.42/292.35 true :: true:false 1118.42/292.35 s :: 0:s -> 0:s 1118.42/292.35 false :: true:false 1118.42/292.35 le :: 0:s -> 0:s -> true:false 1118.42/292.35 min :: nil:cons -> 0:s 1118.42/292.35 cons :: 0:s -> nil:cons -> nil:cons 1118.42/292.35 nil :: nil:cons 1118.42/292.35 ifmin :: true:false -> nil:cons -> 0:s 1118.42/292.35 replace :: 0:s -> 0:s -> nil:cons -> nil:cons 1118.42/292.35 ifrepl :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons 1118.42/292.35 selsort :: nil:cons -> nil:cons 1118.42/292.35 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.35 1118.42/292.35 Rewrite Strategy: INNERMOST 1118.42/292.35 ---------------------------------------- 1118.42/292.35 1118.42/292.35 (5) CompletionProof (UPPER BOUND(ID)) 1118.42/292.35 The transformation into a RNTS is sound, since: 1118.42/292.35 1118.42/292.35 (a) The obligation is a constructor system where every type has a constant constructor, 1118.42/292.35 1118.42/292.35 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 1118.42/292.35 1118.42/292.35 selsort_1 1118.42/292.35 ifselsort_2 1118.42/292.35 1118.42/292.35 (c) The following functions are completely defined: 1118.42/292.35 1118.42/292.35 le_2 1118.42/292.35 eq_2 1118.42/292.35 min_1 1118.42/292.35 replace_3 1118.42/292.35 ifmin_2 1118.42/292.35 ifrepl_4 1118.42/292.35 1118.42/292.35 Due to the following rules being added: 1118.42/292.35 1118.42/292.35 min(v0) -> 0 [0] 1118.42/292.35 ifmin(v0, v1) -> 0 [0] 1118.42/292.35 ifrepl(v0, v1, v2, v3) -> nil [0] 1118.42/292.35 1118.42/292.35 And the following fresh constants: none 1118.42/292.35 1118.42/292.35 ---------------------------------------- 1118.42/292.35 1118.42/292.35 (6) 1118.42/292.35 Obligation: 1118.42/292.35 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1118.42/292.35 1118.42/292.35 Runtime Complexity Weighted TRS with Types. 1118.42/292.35 The TRS R consists of the following rules: 1118.42/292.35 1118.42/292.35 eq(0, 0) -> true [1] 1118.42/292.35 eq(0, s(Y)) -> false [1] 1118.42/292.35 eq(s(X), 0) -> false [1] 1118.42/292.35 eq(s(X), s(Y)) -> eq(X, Y) [1] 1118.42/292.35 le(0, Y) -> true [1] 1118.42/292.35 le(s(X), 0) -> false [1] 1118.42/292.35 le(s(X), s(Y)) -> le(X, Y) [1] 1118.42/292.35 min(cons(0, nil)) -> 0 [1] 1118.42/292.35 min(cons(s(N), nil)) -> s(N) [1] 1118.42/292.35 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) [1] 1118.42/292.35 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) [1] 1118.42/292.35 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) [1] 1118.42/292.36 replace(N, M, nil) -> nil [1] 1118.42/292.36 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) [1] 1118.42/292.36 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) [1] 1118.42/292.36 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) [1] 1118.42/292.36 selsort(nil) -> nil [1] 1118.42/292.36 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) [1] 1118.42/292.36 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) [1] 1118.42/292.36 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) [1] 1118.42/292.36 min(v0) -> 0 [0] 1118.42/292.36 ifmin(v0, v1) -> 0 [0] 1118.42/292.36 ifrepl(v0, v1, v2, v3) -> nil [0] 1118.42/292.36 1118.42/292.36 The TRS has the following type information: 1118.42/292.36 eq :: 0:s -> 0:s -> true:false 1118.42/292.36 0 :: 0:s 1118.42/292.36 true :: true:false 1118.42/292.36 s :: 0:s -> 0:s 1118.42/292.36 false :: true:false 1118.42/292.36 le :: 0:s -> 0:s -> true:false 1118.42/292.36 min :: nil:cons -> 0:s 1118.42/292.36 cons :: 0:s -> nil:cons -> nil:cons 1118.42/292.36 nil :: nil:cons 1118.42/292.36 ifmin :: true:false -> nil:cons -> 0:s 1118.42/292.36 replace :: 0:s -> 0:s -> nil:cons -> nil:cons 1118.42/292.36 ifrepl :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons 1118.42/292.36 selsort :: nil:cons -> nil:cons 1118.42/292.36 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.36 1118.42/292.36 Rewrite Strategy: INNERMOST 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 1118.42/292.36 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (8) 1118.42/292.36 Obligation: 1118.42/292.36 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1118.42/292.36 1118.42/292.36 Runtime Complexity Weighted TRS with Types. 1118.42/292.36 The TRS R consists of the following rules: 1118.42/292.36 1118.42/292.36 eq(0, 0) -> true [1] 1118.42/292.36 eq(0, s(Y)) -> false [1] 1118.42/292.36 eq(s(X), 0) -> false [1] 1118.42/292.36 eq(s(X), s(Y)) -> eq(X, Y) [1] 1118.42/292.36 le(0, Y) -> true [1] 1118.42/292.36 le(s(X), 0) -> false [1] 1118.42/292.36 le(s(X), s(Y)) -> le(X, Y) [1] 1118.42/292.36 min(cons(0, nil)) -> 0 [1] 1118.42/292.36 min(cons(s(N), nil)) -> s(N) [1] 1118.42/292.36 min(cons(0, cons(M, L))) -> ifmin(true, cons(0, cons(M, L))) [2] 1118.42/292.36 min(cons(s(X'), cons(0, L))) -> ifmin(false, cons(s(X'), cons(0, L))) [2] 1118.42/292.36 min(cons(s(X''), cons(s(Y'), L))) -> ifmin(le(X'', Y'), cons(s(X''), cons(s(Y'), L))) [2] 1118.42/292.36 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) [1] 1118.42/292.36 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) [1] 1118.42/292.36 replace(N, M, nil) -> nil [1] 1118.42/292.36 replace(0, M, cons(0, L)) -> ifrepl(true, 0, M, cons(0, L)) [2] 1118.42/292.36 replace(0, M, cons(s(Y''), L)) -> ifrepl(false, 0, M, cons(s(Y''), L)) [2] 1118.42/292.36 replace(s(X1), M, cons(0, L)) -> ifrepl(false, s(X1), M, cons(0, L)) [2] 1118.42/292.36 replace(s(X2), M, cons(s(Y1), L)) -> ifrepl(eq(X2, Y1), s(X2), M, cons(s(Y1), L)) [2] 1118.42/292.36 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) [1] 1118.42/292.36 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) [1] 1118.42/292.36 selsort(nil) -> nil [1] 1118.42/292.36 selsort(cons(0, nil)) -> ifselsort(eq(0, 0), cons(0, nil)) [2] 1118.42/292.36 selsort(cons(s(N'), nil)) -> ifselsort(eq(s(N'), s(N')), cons(s(N'), nil)) [2] 1118.42/292.36 selsort(cons(N, cons(M', L'))) -> ifselsort(eq(N, ifmin(le(N, M'), cons(N, cons(M', L')))), cons(N, cons(M', L'))) [2] 1118.42/292.36 selsort(cons(N, L)) -> ifselsort(eq(N, 0), cons(N, L)) [1] 1118.42/292.36 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) [1] 1118.42/292.36 ifselsort(false, cons(0, nil)) -> cons(min(cons(0, nil)), selsort(replace(0, 0, nil))) [2] 1118.42/292.36 ifselsort(false, cons(s(N''), nil)) -> cons(min(cons(s(N''), nil)), selsort(replace(s(N''), s(N''), nil))) [2] 1118.42/292.36 ifselsort(false, cons(N, cons(M'', L''))) -> cons(min(cons(N, cons(M'', L''))), selsort(replace(ifmin(le(N, M''), cons(N, cons(M'', L''))), N, cons(M'', L'')))) [2] 1118.42/292.36 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(0, N, L))) [1] 1118.42/292.36 min(v0) -> 0 [0] 1118.42/292.36 ifmin(v0, v1) -> 0 [0] 1118.42/292.36 ifrepl(v0, v1, v2, v3) -> nil [0] 1118.42/292.36 1118.42/292.36 The TRS has the following type information: 1118.42/292.36 eq :: 0:s -> 0:s -> true:false 1118.42/292.36 0 :: 0:s 1118.42/292.36 true :: true:false 1118.42/292.36 s :: 0:s -> 0:s 1118.42/292.36 false :: true:false 1118.42/292.36 le :: 0:s -> 0:s -> true:false 1118.42/292.36 min :: nil:cons -> 0:s 1118.42/292.36 cons :: 0:s -> nil:cons -> nil:cons 1118.42/292.36 nil :: nil:cons 1118.42/292.36 ifmin :: true:false -> nil:cons -> 0:s 1118.42/292.36 replace :: 0:s -> 0:s -> nil:cons -> nil:cons 1118.42/292.36 ifrepl :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons 1118.42/292.36 selsort :: nil:cons -> nil:cons 1118.42/292.36 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.36 1118.42/292.36 Rewrite Strategy: INNERMOST 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1118.42/292.36 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1118.42/292.36 The constant constructors are abstracted as follows: 1118.42/292.36 1118.42/292.36 0 => 0 1118.42/292.36 true => 1 1118.42/292.36 false => 0 1118.42/292.36 nil => 0 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (10) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(X, Y) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: Y >= 0, z' = 1 + Y, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z = 1 + X, X >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(N, M, L) :|: K >= 0, z' = N, L >= 0, z = 0, M >= 0, z'' = M, z1 = 1 + K + L, N >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + M + L :|: z = 1, K >= 0, z' = N, L >= 0, M >= 0, z'' = M, z1 = 1 + K + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(le(N, M''), 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + N'') + 0) + selsort(replace(1 + N'', 1 + N'', 0)) :|: z' = 1 + (1 + N'') + 0, N'' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> le(X, Y) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' = Y, Y >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z = 1 + X, X >= 0, z' = 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(le(X'', Y'), 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 1118.42/292.36 min(z) -{ 1 }-> 1 + N :|: z = 1 + (1 + N) + 0, N >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(X2, Y1), 1 + X2, M, 1 + (1 + Y1) + L) :|: z' = M, Y1 >= 0, z'' = 1 + (1 + Y1) + L, z = 1 + X2, L >= 0, X2 >= 0, M >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, M, 1 + 0 + L) :|: z'' = 1 + 0 + L, z' = M, L >= 0, z = 0, M >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, M, 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, z' = M, Y'' >= 0, L >= 0, z = 0, M >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + X1, M, 1 + 0 + L) :|: z'' = 1 + 0 + L, X1 >= 0, z' = M, z = 1 + X1, L >= 0, M >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = M, z = N, M >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(N, ifmin(le(N, M'), 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + N', 1 + N'), 1 + (1 + N') + 0) :|: z = 1 + (1 + N') + 0, N' >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (11) SimplificationProof (BOTH BOUNDS(ID, ID)) 1118.42/292.36 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (12) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(le(N, M''), 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(le(X'', Y'), 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(N, ifmin(le(N, M'), 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (13) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 1118.42/292.36 Found the following analysis order by SCC decomposition: 1118.42/292.36 1118.42/292.36 { le } 1118.42/292.36 { eq } 1118.42/292.36 { min, ifmin } 1118.42/292.36 { replace, ifrepl } 1118.42/292.36 { ifselsort, selsort } 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (14) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(le(N, M''), 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(le(X'', Y'), 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(N, ifmin(le(N, M'), 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {le}, {eq}, {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (15) ResultPropagationProof (UPPER BOUND(ID)) 1118.42/292.36 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (16) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(le(N, M''), 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(le(X'', Y'), 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(N, ifmin(le(N, M'), 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {le}, {eq}, {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (17) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.36 1118.42/292.36 Computed SIZE bound using CoFloCo for: le 1118.42/292.36 after applying outer abstraction to obtain an ITS, 1118.42/292.36 resulting in: O(1) with polynomial bound: 1 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (18) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(le(N, M''), 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(le(X'', Y'), 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(N, ifmin(le(N, M'), 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {le}, {eq}, {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 Previous analysis results are: 1118.42/292.36 le: runtime: ?, size: O(1) [1] 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (19) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.36 1118.42/292.36 Computed RUNTIME bound using KoAT for: le 1118.42/292.36 after applying outer abstraction to obtain an ITS, 1118.42/292.36 resulting in: O(n^1) with polynomial bound: 2 + z' 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (20) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(le(N, M''), 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(le(X'', Y'), 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(N, ifmin(le(N, M'), 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {eq}, {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 Previous analysis results are: 1118.42/292.36 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (21) ResultPropagationProof (UPPER BOUND(ID)) 1118.42/292.36 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (22) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 4 + M'' }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(s1, 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 4 + Y' }-> ifmin(s', 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 4 + M' }-> ifselsort(eq(N, ifmin(s'', 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {eq}, {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 Previous analysis results are: 1118.42/292.36 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (23) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.36 1118.42/292.36 Computed SIZE bound using CoFloCo for: eq 1118.42/292.36 after applying outer abstraction to obtain an ITS, 1118.42/292.36 resulting in: O(1) with polynomial bound: 1 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (24) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 4 + M'' }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(s1, 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 4 + Y' }-> ifmin(s', 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 4 + M' }-> ifselsort(eq(N, ifmin(s'', 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {eq}, {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 Previous analysis results are: 1118.42/292.36 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.36 eq: runtime: ?, size: O(1) [1] 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (25) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.36 1118.42/292.36 Computed RUNTIME bound using KoAT for: eq 1118.42/292.36 after applying outer abstraction to obtain an ITS, 1118.42/292.36 resulting in: O(n^1) with polynomial bound: 3 + z' 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (26) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 4 + M'' }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(s1, 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 4 + Y' }-> ifmin(s', 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(eq(z - 1, Y1), 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 4 + M' }-> ifselsort(eq(N, ifmin(s'', 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> ifselsort(eq(N, 0), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(0, 0), 1 + 0 + 0) :|: z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 2 }-> ifselsort(eq(1 + (z - 2), 1 + (z - 2)), 1 + (1 + (z - 2)) + 0) :|: z - 2 >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 Previous analysis results are: 1118.42/292.36 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.36 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (27) ResultPropagationProof (UPPER BOUND(ID)) 1118.42/292.36 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (28) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 4 + M'' }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(s1, 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.36 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.36 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.36 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 min(z) -{ 4 + Y' }-> ifmin(s', 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.36 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.36 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.36 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.36 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.36 replace(z, z', z'') -{ 5 + Y1 }-> ifrepl(s3, 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.36 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.36 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.36 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.36 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 4 + M' }-> ifselsort(eq(N, ifmin(s'', 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.36 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.36 1118.42/292.36 Function symbols to be analyzed: {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.36 Previous analysis results are: 1118.42/292.36 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.36 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (29) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.36 1118.42/292.36 Computed SIZE bound using KoAT for: min 1118.42/292.36 after applying outer abstraction to obtain an ITS, 1118.42/292.36 resulting in: O(n^1) with polynomial bound: z 1118.42/292.36 1118.42/292.36 Computed SIZE bound using KoAT for: ifmin 1118.42/292.36 after applying outer abstraction to obtain an ITS, 1118.42/292.36 resulting in: O(n^1) with polynomial bound: z' 1118.42/292.36 1118.42/292.36 ---------------------------------------- 1118.42/292.36 1118.42/292.36 (30) 1118.42/292.36 Obligation: 1118.42/292.36 Complexity RNTS consisting of the following rules: 1118.42/292.36 1118.42/292.36 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.36 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.36 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.36 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.36 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.37 ifselsort(z, z') -{ 4 + M'' }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(s1, 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.37 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.37 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.37 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.37 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.37 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.37 min(z) -{ 4 + Y' }-> ifmin(s', 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.37 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.37 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.37 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.37 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.37 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.37 replace(z, z', z'') -{ 5 + Y1 }-> ifrepl(s3, 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.37 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.37 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.37 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.37 selsort(z) -{ 4 + M' }-> ifselsort(eq(N, ifmin(s'', 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.37 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.37 1118.42/292.37 Function symbols to be analyzed: {min,ifmin}, {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.37 Previous analysis results are: 1118.42/292.37 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.37 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.37 min: runtime: ?, size: O(n^1) [z] 1118.42/292.37 ifmin: runtime: ?, size: O(n^1) [z'] 1118.42/292.37 1118.42/292.37 ---------------------------------------- 1118.42/292.37 1118.42/292.37 (31) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.37 1118.42/292.37 Computed RUNTIME bound using KoAT for: min 1118.42/292.37 after applying outer abstraction to obtain an ITS, 1118.42/292.37 resulting in: O(n^2) with polynomial bound: 2 + 20*z + 2*z^2 1118.42/292.37 1118.42/292.37 Computed RUNTIME bound using KoAT for: ifmin 1118.42/292.37 after applying outer abstraction to obtain an ITS, 1118.42/292.37 resulting in: O(n^2) with polynomial bound: 50 + 96*z' + 16*z'^2 1118.42/292.37 1118.42/292.37 ---------------------------------------- 1118.42/292.37 1118.42/292.37 (32) 1118.42/292.37 Obligation: 1118.42/292.37 Complexity RNTS consisting of the following rules: 1118.42/292.37 1118.42/292.37 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.37 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.37 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.37 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.37 ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.37 ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.37 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.37 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.37 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.37 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.37 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.37 ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(0, N, L)) :|: L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.37 ifselsort(z, z') -{ 4 + M'' }-> 1 + min(1 + N + (1 + M'' + L'')) + selsort(replace(ifmin(s1, 1 + N + (1 + M'' + L'')), N, 1 + M'' + L'')) :|: s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.37 ifselsort(z, z') -{ 2 }-> 1 + min(1 + 0 + 0) + selsort(replace(0, 0, 0)) :|: z' = 1 + 0 + 0, z = 0 1118.42/292.37 ifselsort(z, z') -{ 2 }-> 1 + min(1 + (1 + (z' - 2)) + 0) + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: z' - 2 >= 0, z = 0 1118.42/292.37 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.37 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.37 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.37 min(z) -{ 4 + Y' }-> ifmin(s', 1 + (1 + X'') + (1 + (1 + Y') + L)) :|: s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.37 min(z) -{ 2 }-> ifmin(1, 1 + 0 + (1 + M + L)) :|: z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.37 min(z) -{ 2 }-> ifmin(0, 1 + (1 + X') + (1 + 0 + L)) :|: X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.37 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.37 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.37 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.37 replace(z, z', z'') -{ 5 + Y1 }-> ifrepl(s3, 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.37 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.37 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.37 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.37 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.37 selsort(z) -{ 4 + M' }-> ifselsort(eq(N, ifmin(s'', 1 + N + (1 + M' + L'))), 1 + N + (1 + M' + L')) :|: s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.37 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.37 1118.42/292.37 Function symbols to be analyzed: {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.37 Previous analysis results are: 1118.42/292.37 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.37 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.37 min: runtime: O(n^2) [2 + 20*z + 2*z^2], size: O(n^1) [z] 1118.42/292.37 ifmin: runtime: O(n^2) [50 + 96*z' + 16*z'^2], size: O(n^1) [z'] 1118.42/292.37 1118.42/292.37 ---------------------------------------- 1118.42/292.37 1118.42/292.37 (33) ResultPropagationProof (UPPER BOUND(ID)) 1118.42/292.37 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1118.42/292.37 ---------------------------------------- 1118.42/292.37 1118.42/292.37 (34) 1118.42/292.37 Obligation: 1118.42/292.37 Complexity RNTS consisting of the following rules: 1118.42/292.37 1118.42/292.37 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.37 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.37 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.37 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.37 ifmin(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> s10 :|: s10 >= 0, s10 <= 1 + N + L, z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.37 ifmin(z, z') -{ 25 + 24*L + 4*L*M + 2*L^2 + 24*M + 2*M^2 }-> s11 :|: s11 >= 0, s11 <= 1 + M + L, z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.37 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.37 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.37 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.37 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.37 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.37 ifselsort(z, z') -{ 26 }-> 1 + s14 + selsort(replace(0, 0, 0)) :|: s14 >= 0, s14 <= 1 + 0 + 0, z' = 1 + 0 + 0, z = 0 1118.42/292.37 ifselsort(z, z') -{ 4 + 20*z' + 2*z'^2 }-> 1 + s15 + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: s15 >= 0, s15 <= 1 + (1 + (z' - 2)) + 0, z' - 2 >= 0, z = 0 1118.42/292.37 ifselsort(z, z') -{ 360 + 188*L'' + 36*L''*M'' + 36*L''*N + 18*L''^2 + 189*M'' + 36*M''*N + 18*M''^2 + 188*N + 18*N^2 }-> 1 + s16 + selsort(replace(s17, N, 1 + M'' + L'')) :|: s16 >= 0, s16 <= 1 + N + (1 + M'' + L''), s17 >= 0, s17 <= 1 + N + (1 + M'' + L''), s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> 1 + s18 + selsort(replace(0, N, L)) :|: s18 >= 0, s18 <= 1 + N + L, L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.39 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.39 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 min(z) -{ 308 + 160*L + 32*L*M + 16*L^2 + 160*M + 16*M^2 }-> s7 :|: s7 >= 0, s7 <= 1 + 0 + (1 + M + L), z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.39 min(z) -{ 484 + 192*L + 32*L*X' + 16*L^2 + 192*X' + 16*X'^2 }-> s8 :|: s8 >= 0, s8 <= 1 + (1 + X') + (1 + 0 + L), X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.39 min(z) -{ 694 + 224*L + 32*L*X'' + 32*L*Y' + 16*L^2 + 224*X'' + 32*X''*Y' + 16*X''^2 + 225*Y' + 16*Y'^2 }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + X'') + (1 + (1 + Y') + L), s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.39 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.39 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.39 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.39 replace(z, z', z'') -{ 5 + Y1 }-> ifrepl(s3, 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.39 selsort(z) -{ 313 + 160*L' + 32*L'*M' + 32*L'*N + 16*L'^2 + 161*M' + 32*M'*N + 16*M'^2 + 160*N + 16*N^2 + s12 }-> ifselsort(s13, 1 + N + (1 + M' + L')) :|: s12 >= 0, s12 <= 1 + N + (1 + M' + L'), s13 >= 0, s13 <= 1, s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.39 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.39 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.39 1118.42/292.39 Function symbols to be analyzed: {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.39 Previous analysis results are: 1118.42/292.39 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.39 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.39 min: runtime: O(n^2) [2 + 20*z + 2*z^2], size: O(n^1) [z] 1118.42/292.39 ifmin: runtime: O(n^2) [50 + 96*z' + 16*z'^2], size: O(n^1) [z'] 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (35) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.39 1118.42/292.39 Computed SIZE bound using KoAT for: replace 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^1) with polynomial bound: z' + z'' 1118.42/292.39 1118.42/292.39 Computed SIZE bound using KoAT for: ifrepl 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^1) with polynomial bound: z'' + z1 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (36) 1118.42/292.39 Obligation: 1118.42/292.39 Complexity RNTS consisting of the following rules: 1118.42/292.39 1118.42/292.39 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> s10 :|: s10 >= 0, s10 <= 1 + N + L, z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*M + 2*L^2 + 24*M + 2*M^2 }-> s11 :|: s11 >= 0, s11 <= 1 + M + L, z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 26 }-> 1 + s14 + selsort(replace(0, 0, 0)) :|: s14 >= 0, s14 <= 1 + 0 + 0, z' = 1 + 0 + 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 4 + 20*z' + 2*z'^2 }-> 1 + s15 + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: s15 >= 0, s15 <= 1 + (1 + (z' - 2)) + 0, z' - 2 >= 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 360 + 188*L'' + 36*L''*M'' + 36*L''*N + 18*L''^2 + 189*M'' + 36*M''*N + 18*M''^2 + 188*N + 18*N^2 }-> 1 + s16 + selsort(replace(s17, N, 1 + M'' + L'')) :|: s16 >= 0, s16 <= 1 + N + (1 + M'' + L''), s17 >= 0, s17 <= 1 + N + (1 + M'' + L''), s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> 1 + s18 + selsort(replace(0, N, L)) :|: s18 >= 0, s18 <= 1 + N + L, L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.39 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.39 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 min(z) -{ 308 + 160*L + 32*L*M + 16*L^2 + 160*M + 16*M^2 }-> s7 :|: s7 >= 0, s7 <= 1 + 0 + (1 + M + L), z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.39 min(z) -{ 484 + 192*L + 32*L*X' + 16*L^2 + 192*X' + 16*X'^2 }-> s8 :|: s8 >= 0, s8 <= 1 + (1 + X') + (1 + 0 + L), X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.39 min(z) -{ 694 + 224*L + 32*L*X'' + 32*L*Y' + 16*L^2 + 224*X'' + 32*X''*Y' + 16*X''^2 + 225*Y' + 16*Y'^2 }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + X'') + (1 + (1 + Y') + L), s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.39 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.39 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.39 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.39 replace(z, z', z'') -{ 5 + Y1 }-> ifrepl(s3, 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.39 selsort(z) -{ 313 + 160*L' + 32*L'*M' + 32*L'*N + 16*L'^2 + 161*M' + 32*M'*N + 16*M'^2 + 160*N + 16*N^2 + s12 }-> ifselsort(s13, 1 + N + (1 + M' + L')) :|: s12 >= 0, s12 <= 1 + N + (1 + M' + L'), s13 >= 0, s13 <= 1, s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.39 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.39 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.39 1118.42/292.39 Function symbols to be analyzed: {replace,ifrepl}, {ifselsort,selsort} 1118.42/292.39 Previous analysis results are: 1118.42/292.39 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.39 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.39 min: runtime: O(n^2) [2 + 20*z + 2*z^2], size: O(n^1) [z] 1118.42/292.39 ifmin: runtime: O(n^2) [50 + 96*z' + 16*z'^2], size: O(n^1) [z'] 1118.42/292.39 replace: runtime: ?, size: O(n^1) [z' + z''] 1118.42/292.39 ifrepl: runtime: ?, size: O(n^1) [z'' + z1] 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (37) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.39 1118.42/292.39 Computed RUNTIME bound using KoAT for: replace 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^2) with polynomial bound: 2 + 24*z'' + 2*z''^2 1118.42/292.39 1118.42/292.39 Computed RUNTIME bound using KoAT for: ifrepl 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^2) with polynomial bound: 4 + 24*z1 + 2*z1^2 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (38) 1118.42/292.39 Obligation: 1118.42/292.39 Complexity RNTS consisting of the following rules: 1118.42/292.39 1118.42/292.39 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> s10 :|: s10 >= 0, s10 <= 1 + N + L, z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*M + 2*L^2 + 24*M + 2*M^2 }-> s11 :|: s11 >= 0, s11 <= 1 + M + L, z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(z', z'', L) :|: K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 26 }-> 1 + s14 + selsort(replace(0, 0, 0)) :|: s14 >= 0, s14 <= 1 + 0 + 0, z' = 1 + 0 + 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 4 + 20*z' + 2*z'^2 }-> 1 + s15 + selsort(replace(1 + (z' - 2), 1 + (z' - 2), 0)) :|: s15 >= 0, s15 <= 1 + (1 + (z' - 2)) + 0, z' - 2 >= 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 360 + 188*L'' + 36*L''*M'' + 36*L''*N + 18*L''^2 + 189*M'' + 36*M''*N + 18*M''^2 + 188*N + 18*N^2 }-> 1 + s16 + selsort(replace(s17, N, 1 + M'' + L'')) :|: s16 >= 0, s16 <= 1 + N + (1 + M'' + L''), s17 >= 0, s17 <= 1 + N + (1 + M'' + L''), s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> 1 + s18 + selsort(replace(0, N, L)) :|: s18 >= 0, s18 <= 1 + N + L, L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.39 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.39 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 min(z) -{ 308 + 160*L + 32*L*M + 16*L^2 + 160*M + 16*M^2 }-> s7 :|: s7 >= 0, s7 <= 1 + 0 + (1 + M + L), z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.39 min(z) -{ 484 + 192*L + 32*L*X' + 16*L^2 + 192*X' + 16*X'^2 }-> s8 :|: s8 >= 0, s8 <= 1 + (1 + X') + (1 + 0 + L), X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.39 min(z) -{ 694 + 224*L + 32*L*X'' + 32*L*Y' + 16*L^2 + 224*X'' + 32*X''*Y' + 16*X''^2 + 225*Y' + 16*Y'^2 }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + X'') + (1 + (1 + Y') + L), s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.39 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.39 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.39 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.39 replace(z, z', z'') -{ 5 + Y1 }-> ifrepl(s3, 1 + (z - 1), z', 1 + (1 + Y1) + L) :|: s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(0, 0, z', 1 + (1 + Y'') + L) :|: z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 2 }-> ifrepl(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.39 selsort(z) -{ 313 + 160*L' + 32*L'*M' + 32*L'*N + 16*L'^2 + 161*M' + 32*M'*N + 16*M'^2 + 160*N + 16*N^2 + s12 }-> ifselsort(s13, 1 + N + (1 + M' + L')) :|: s12 >= 0, s12 <= 1 + N + (1 + M' + L'), s13 >= 0, s13 <= 1, s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.39 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.39 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.39 1118.42/292.39 Function symbols to be analyzed: {ifselsort,selsort} 1118.42/292.39 Previous analysis results are: 1118.42/292.39 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.39 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.39 min: runtime: O(n^2) [2 + 20*z + 2*z^2], size: O(n^1) [z] 1118.42/292.39 ifmin: runtime: O(n^2) [50 + 96*z' + 16*z'^2], size: O(n^1) [z'] 1118.42/292.39 replace: runtime: O(n^2) [2 + 24*z'' + 2*z''^2], size: O(n^1) [z' + z''] 1118.42/292.39 ifrepl: runtime: O(n^2) [4 + 24*z1 + 2*z1^2], size: O(n^1) [z'' + z1] 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (39) ResultPropagationProof (UPPER BOUND(ID)) 1118.42/292.39 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (40) 1118.42/292.39 Obligation: 1118.42/292.39 Complexity RNTS consisting of the following rules: 1118.42/292.39 1118.42/292.39 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> s10 :|: s10 >= 0, s10 <= 1 + N + L, z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*M + 2*L^2 + 24*M + 2*M^2 }-> s11 :|: s11 >= 0, s11 <= 1 + M + L, z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 3 + 24*L + 2*L^2 }-> 1 + K + s23 :|: s23 >= 0, s23 <= z'' + L, K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 28 }-> 1 + s14 + selsort(s24) :|: s24 >= 0, s24 <= 0 + 0, s14 >= 0, s14 <= 1 + 0 + 0, z' = 1 + 0 + 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 6 + 20*z' + 2*z'^2 }-> 1 + s15 + selsort(s25) :|: s25 >= 0, s25 <= 1 + (z' - 2) + 0, s15 >= 0, s15 <= 1 + (1 + (z' - 2)) + 0, z' - 2 >= 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 388 + 216*L'' + 40*L''*M'' + 36*L''*N + 20*L''^2 + 217*M'' + 36*M''*N + 20*M''^2 + 188*N + 18*N^2 }-> 1 + s16 + selsort(s26) :|: s26 >= 0, s26 <= N + (1 + M'' + L''), s16 >= 0, s16 <= 1 + N + (1 + M'' + L''), s17 >= 0, s17 <= 1 + N + (1 + M'' + L''), s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 27 + 48*L + 4*L*N + 4*L^2 + 24*N + 2*N^2 }-> 1 + s18 + selsort(s27) :|: s27 >= 0, s27 <= N + L, s18 >= 0, s18 <= 1 + N + L, L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.39 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.39 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 min(z) -{ 308 + 160*L + 32*L*M + 16*L^2 + 160*M + 16*M^2 }-> s7 :|: s7 >= 0, s7 <= 1 + 0 + (1 + M + L), z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.39 min(z) -{ 484 + 192*L + 32*L*X' + 16*L^2 + 192*X' + 16*X'^2 }-> s8 :|: s8 >= 0, s8 <= 1 + (1 + X') + (1 + 0 + L), X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.39 min(z) -{ 694 + 224*L + 32*L*X'' + 32*L*Y' + 16*L^2 + 224*X'' + 32*X''*Y' + 16*X''^2 + 225*Y' + 16*Y'^2 }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + X'') + (1 + (1 + Y') + L), s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.39 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.39 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.39 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.39 replace(z, z', z'') -{ 6 + 24*z'' + 2*z''^2 }-> s19 :|: s19 >= 0, s19 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 62 + 32*L + 4*L*Y'' + 2*L^2 + 32*Y'' + 2*Y''^2 }-> s20 :|: s20 >= 0, s20 <= z' + (1 + (1 + Y'') + L), z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 6 + 24*z'' + 2*z''^2 }-> s21 :|: s21 >= 0, s21 <= z' + (1 + 0 + (z'' - 1)), z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 65 + 32*L + 4*L*Y1 + 2*L^2 + 33*Y1 + 2*Y1^2 }-> s22 :|: s22 >= 0, s22 <= z' + (1 + (1 + Y1) + L), s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.39 selsort(z) -{ 313 + 160*L' + 32*L'*M' + 32*L'*N + 16*L'^2 + 161*M' + 32*M'*N + 16*M'^2 + 160*N + 16*N^2 + s12 }-> ifselsort(s13, 1 + N + (1 + M' + L')) :|: s12 >= 0, s12 <= 1 + N + (1 + M' + L'), s13 >= 0, s13 <= 1, s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.39 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.39 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.39 1118.42/292.39 Function symbols to be analyzed: {ifselsort,selsort} 1118.42/292.39 Previous analysis results are: 1118.42/292.39 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.39 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.39 min: runtime: O(n^2) [2 + 20*z + 2*z^2], size: O(n^1) [z] 1118.42/292.39 ifmin: runtime: O(n^2) [50 + 96*z' + 16*z'^2], size: O(n^1) [z'] 1118.42/292.39 replace: runtime: O(n^2) [2 + 24*z'' + 2*z''^2], size: O(n^1) [z' + z''] 1118.42/292.39 ifrepl: runtime: O(n^2) [4 + 24*z1 + 2*z1^2], size: O(n^1) [z'' + z1] 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (41) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.39 1118.42/292.39 Computed SIZE bound using KoAT for: ifselsort 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^2) with polynomial bound: 20*z' + 8*z'^2 1118.42/292.39 1118.42/292.39 Computed SIZE bound using KoAT for: selsort 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^2) with polynomial bound: 128 + 248*z + 112*z^2 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (42) 1118.42/292.39 Obligation: 1118.42/292.39 Complexity RNTS consisting of the following rules: 1118.42/292.39 1118.42/292.39 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> s10 :|: s10 >= 0, s10 <= 1 + N + L, z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*M + 2*L^2 + 24*M + 2*M^2 }-> s11 :|: s11 >= 0, s11 <= 1 + M + L, z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 3 + 24*L + 2*L^2 }-> 1 + K + s23 :|: s23 >= 0, s23 <= z'' + L, K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 28 }-> 1 + s14 + selsort(s24) :|: s24 >= 0, s24 <= 0 + 0, s14 >= 0, s14 <= 1 + 0 + 0, z' = 1 + 0 + 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 6 + 20*z' + 2*z'^2 }-> 1 + s15 + selsort(s25) :|: s25 >= 0, s25 <= 1 + (z' - 2) + 0, s15 >= 0, s15 <= 1 + (1 + (z' - 2)) + 0, z' - 2 >= 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 388 + 216*L'' + 40*L''*M'' + 36*L''*N + 20*L''^2 + 217*M'' + 36*M''*N + 20*M''^2 + 188*N + 18*N^2 }-> 1 + s16 + selsort(s26) :|: s26 >= 0, s26 <= N + (1 + M'' + L''), s16 >= 0, s16 <= 1 + N + (1 + M'' + L''), s17 >= 0, s17 <= 1 + N + (1 + M'' + L''), s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 27 + 48*L + 4*L*N + 4*L^2 + 24*N + 2*N^2 }-> 1 + s18 + selsort(s27) :|: s27 >= 0, s27 <= N + L, s18 >= 0, s18 <= 1 + N + L, L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.39 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.39 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 min(z) -{ 308 + 160*L + 32*L*M + 16*L^2 + 160*M + 16*M^2 }-> s7 :|: s7 >= 0, s7 <= 1 + 0 + (1 + M + L), z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.39 min(z) -{ 484 + 192*L + 32*L*X' + 16*L^2 + 192*X' + 16*X'^2 }-> s8 :|: s8 >= 0, s8 <= 1 + (1 + X') + (1 + 0 + L), X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.39 min(z) -{ 694 + 224*L + 32*L*X'' + 32*L*Y' + 16*L^2 + 224*X'' + 32*X''*Y' + 16*X''^2 + 225*Y' + 16*Y'^2 }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + X'') + (1 + (1 + Y') + L), s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.39 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.39 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.39 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.39 replace(z, z', z'') -{ 6 + 24*z'' + 2*z''^2 }-> s19 :|: s19 >= 0, s19 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 62 + 32*L + 4*L*Y'' + 2*L^2 + 32*Y'' + 2*Y''^2 }-> s20 :|: s20 >= 0, s20 <= z' + (1 + (1 + Y'') + L), z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 6 + 24*z'' + 2*z''^2 }-> s21 :|: s21 >= 0, s21 <= z' + (1 + 0 + (z'' - 1)), z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 65 + 32*L + 4*L*Y1 + 2*L^2 + 33*Y1 + 2*Y1^2 }-> s22 :|: s22 >= 0, s22 <= z' + (1 + (1 + Y1) + L), s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.39 selsort(z) -{ 313 + 160*L' + 32*L'*M' + 32*L'*N + 16*L'^2 + 161*M' + 32*M'*N + 16*M'^2 + 160*N + 16*N^2 + s12 }-> ifselsort(s13, 1 + N + (1 + M' + L')) :|: s12 >= 0, s12 <= 1 + N + (1 + M' + L'), s13 >= 0, s13 <= 1, s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.39 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.39 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.39 1118.42/292.39 Function symbols to be analyzed: {ifselsort,selsort} 1118.42/292.39 Previous analysis results are: 1118.42/292.39 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.39 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.39 min: runtime: O(n^2) [2 + 20*z + 2*z^2], size: O(n^1) [z] 1118.42/292.39 ifmin: runtime: O(n^2) [50 + 96*z' + 16*z'^2], size: O(n^1) [z'] 1118.42/292.39 replace: runtime: O(n^2) [2 + 24*z'' + 2*z''^2], size: O(n^1) [z' + z''] 1118.42/292.39 ifrepl: runtime: O(n^2) [4 + 24*z1 + 2*z1^2], size: O(n^1) [z'' + z1] 1118.42/292.39 ifselsort: runtime: ?, size: O(n^2) [20*z' + 8*z'^2] 1118.42/292.39 selsort: runtime: ?, size: O(n^2) [128 + 248*z + 112*z^2] 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (43) IntTrsBoundProof (UPPER BOUND(ID)) 1118.42/292.39 1118.42/292.39 Computed RUNTIME bound using KoAT for: ifselsort 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^3) with polynomial bound: 1 + 4604*z' + 3700*z'^2 + 652*z'^3 1118.42/292.39 1118.42/292.39 Computed RUNTIME bound using KoAT for: selsort 1118.42/292.39 after applying outer abstraction to obtain an ITS, 1118.42/292.39 resulting in: O(n^3) with polynomial bound: 47469 + 114693*z + 94976*z^2 + 23472*z^3 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (44) 1118.42/292.39 Obligation: 1118.42/292.39 Complexity RNTS consisting of the following rules: 1118.42/292.39 1118.42/292.39 eq(z, z') -{ 3 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0 1118.42/292.39 eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*N + 2*L^2 + 24*N + 2*N^2 }-> s10 :|: s10 >= 0, s10 <= 1 + N + L, z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 25 + 24*L + 4*L*M + 2*L^2 + 24*M + 2*M^2 }-> s11 :|: s11 >= 0, s11 <= 1 + M + L, z' = 1 + N + (1 + M + L), L >= 0, z = 0, M >= 0, N >= 0 1118.42/292.39 ifmin(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 3 + 24*L + 2*L^2 }-> 1 + K + s23 :|: s23 >= 0, s23 <= z'' + L, K >= 0, L >= 0, z = 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifrepl(z, z', z'', z1) -{ 1 }-> 1 + z'' + L :|: z = 1, K >= 0, L >= 0, z'' >= 0, z1 = 1 + K + L, z' >= 0 1118.42/292.39 ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 28 }-> 1 + s14 + selsort(s24) :|: s24 >= 0, s24 <= 0 + 0, s14 >= 0, s14 <= 1 + 0 + 0, z' = 1 + 0 + 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 6 + 20*z' + 2*z'^2 }-> 1 + s15 + selsort(s25) :|: s25 >= 0, s25 <= 1 + (z' - 2) + 0, s15 >= 0, s15 <= 1 + (1 + (z' - 2)) + 0, z' - 2 >= 0, z = 0 1118.42/292.39 ifselsort(z, z') -{ 388 + 216*L'' + 40*L''*M'' + 36*L''*N + 20*L''^2 + 217*M'' + 36*M''*N + 20*M''^2 + 188*N + 18*N^2 }-> 1 + s16 + selsort(s26) :|: s26 >= 0, s26 <= N + (1 + M'' + L''), s16 >= 0, s16 <= 1 + N + (1 + M'' + L''), s17 >= 0, s17 <= 1 + N + (1 + M'' + L''), s1 >= 0, s1 <= 1, L'' >= 0, M'' >= 0, z' = 1 + N + (1 + M'' + L''), z = 0, N >= 0 1118.42/292.39 ifselsort(z, z') -{ 27 + 48*L + 4*L*N + 4*L^2 + 24*N + 2*N^2 }-> 1 + s18 + selsort(s27) :|: s27 >= 0, s27 <= N + L, s18 >= 0, s18 <= 1 + N + L, L >= 0, z = 0, z' = 1 + N + L, N >= 0 1118.42/292.39 le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z - 1 >= 0 1118.42/292.39 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1118.42/292.39 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1118.42/292.39 min(z) -{ 308 + 160*L + 32*L*M + 16*L^2 + 160*M + 16*M^2 }-> s7 :|: s7 >= 0, s7 <= 1 + 0 + (1 + M + L), z = 1 + 0 + (1 + M + L), L >= 0, M >= 0 1118.42/292.39 min(z) -{ 484 + 192*L + 32*L*X' + 16*L^2 + 192*X' + 16*X'^2 }-> s8 :|: s8 >= 0, s8 <= 1 + (1 + X') + (1 + 0 + L), X' >= 0, L >= 0, z = 1 + (1 + X') + (1 + 0 + L) 1118.42/292.39 min(z) -{ 694 + 224*L + 32*L*X'' + 32*L*Y' + 16*L^2 + 224*X'' + 32*X''*Y' + 16*X''^2 + 225*Y' + 16*Y'^2 }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + X'') + (1 + (1 + Y') + L), s' >= 0, s' <= 1, z = 1 + (1 + X'') + (1 + (1 + Y') + L), Y' >= 0, X'' >= 0, L >= 0 1118.42/292.39 min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0 1118.42/292.39 min(z) -{ 0 }-> 0 :|: z >= 0 1118.42/292.39 min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0 1118.42/292.39 replace(z, z', z'') -{ 6 + 24*z'' + 2*z''^2 }-> s19 :|: s19 >= 0, s19 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 62 + 32*L + 4*L*Y'' + 2*L^2 + 32*Y'' + 2*Y''^2 }-> s20 :|: s20 >= 0, s20 <= z' + (1 + (1 + Y'') + L), z'' = 1 + (1 + Y'') + L, Y'' >= 0, L >= 0, z = 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 6 + 24*z'' + 2*z''^2 }-> s21 :|: s21 >= 0, s21 <= z' + (1 + 0 + (z'' - 1)), z - 1 >= 0, z'' - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 65 + 32*L + 4*L*Y1 + 2*L^2 + 33*Y1 + 2*Y1^2 }-> s22 :|: s22 >= 0, s22 <= z' + (1 + (1 + Y1) + L), s3 >= 0, s3 <= 1, Y1 >= 0, z'' = 1 + (1 + Y1) + L, L >= 0, z - 1 >= 0, z' >= 0 1118.42/292.39 replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' >= 0, z >= 0 1118.42/292.39 selsort(z) -{ 313 + 160*L' + 32*L'*M' + 32*L'*N + 16*L'^2 + 161*M' + 32*M'*N + 16*M'^2 + 160*N + 16*N^2 + s12 }-> ifselsort(s13, 1 + N + (1 + M' + L')) :|: s12 >= 0, s12 <= 1 + N + (1 + M' + L'), s13 >= 0, s13 <= 1, s'' >= 0, s'' <= 1, L' >= 0, z = 1 + N + (1 + M' + L'), M' >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 5 }-> ifselsort(s4, 1 + 0 + 0) :|: s4 >= 0, s4 <= 1, z = 1 + 0 + 0 1118.42/292.39 selsort(z) -{ 4 + z }-> ifselsort(s5, 1 + (1 + (z - 2)) + 0) :|: s5 >= 0, s5 <= 1, z - 2 >= 0 1118.42/292.39 selsort(z) -{ 4 }-> ifselsort(s6, 1 + N + L) :|: s6 >= 0, s6 <= 1, z = 1 + N + L, L >= 0, N >= 0 1118.42/292.39 selsort(z) -{ 1 }-> 0 :|: z = 0 1118.42/292.39 1118.42/292.39 Function symbols to be analyzed: 1118.42/292.39 Previous analysis results are: 1118.42/292.39 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1118.42/292.39 eq: runtime: O(n^1) [3 + z'], size: O(1) [1] 1118.42/292.39 min: runtime: O(n^2) [2 + 20*z + 2*z^2], size: O(n^1) [z] 1118.42/292.39 ifmin: runtime: O(n^2) [50 + 96*z' + 16*z'^2], size: O(n^1) [z'] 1118.42/292.39 replace: runtime: O(n^2) [2 + 24*z'' + 2*z''^2], size: O(n^1) [z' + z''] 1118.42/292.39 ifrepl: runtime: O(n^2) [4 + 24*z1 + 2*z1^2], size: O(n^1) [z'' + z1] 1118.42/292.39 ifselsort: runtime: O(n^3) [1 + 4604*z' + 3700*z'^2 + 652*z'^3], size: O(n^2) [20*z' + 8*z'^2] 1118.42/292.39 selsort: runtime: O(n^3) [47469 + 114693*z + 94976*z^2 + 23472*z^3], size: O(n^2) [128 + 248*z + 112*z^2] 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (45) FinalProof (FINISHED) 1118.42/292.39 Computed overall runtime complexity 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (46) 1118.42/292.39 BOUNDS(1, n^3) 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (47) RenamingProof (BOTH BOUNDS(ID, ID)) 1118.42/292.39 Renamed function symbols to avoid clashes with predefined symbol. 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (48) 1118.42/292.39 Obligation: 1118.42/292.39 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1118.42/292.39 1118.42/292.39 1118.42/292.39 The TRS R consists of the following rules: 1118.42/292.39 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 S is empty. 1118.42/292.39 Rewrite Strategy: INNERMOST 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (49) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1118.42/292.39 Infered types. 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (50) 1118.42/292.39 Obligation: 1118.42/292.39 Innermost TRS: 1118.42/292.39 Rules: 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 Types: 1118.42/292.39 eq :: 0':s -> 0':s -> true:false 1118.42/292.39 0' :: 0':s 1118.42/292.39 true :: true:false 1118.42/292.39 s :: 0':s -> 0':s 1118.42/292.39 false :: true:false 1118.42/292.39 le :: 0':s -> 0':s -> true:false 1118.42/292.39 min :: nil:cons -> 0':s 1118.42/292.39 cons :: 0':s -> nil:cons -> nil:cons 1118.42/292.39 nil :: nil:cons 1118.42/292.39 ifmin :: true:false -> nil:cons -> 0':s 1118.42/292.39 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 selsort :: nil:cons -> nil:cons 1118.42/292.39 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.39 hole_true:false1_0 :: true:false 1118.42/292.39 hole_0':s2_0 :: 0':s 1118.42/292.39 hole_nil:cons3_0 :: nil:cons 1118.42/292.39 gen_0':s4_0 :: Nat -> 0':s 1118.42/292.39 gen_nil:cons5_0 :: Nat -> nil:cons 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (51) OrderProof (LOWER BOUND(ID)) 1118.42/292.39 Heuristically decided to analyse the following defined symbols: 1118.42/292.39 eq, le, min, replace, selsort 1118.42/292.39 1118.42/292.39 They will be analysed ascendingly in the following order: 1118.42/292.39 eq < replace 1118.42/292.39 eq < selsort 1118.42/292.39 le < min 1118.42/292.39 min < selsort 1118.42/292.39 replace < selsort 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (52) 1118.42/292.39 Obligation: 1118.42/292.39 Innermost TRS: 1118.42/292.39 Rules: 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 Types: 1118.42/292.39 eq :: 0':s -> 0':s -> true:false 1118.42/292.39 0' :: 0':s 1118.42/292.39 true :: true:false 1118.42/292.39 s :: 0':s -> 0':s 1118.42/292.39 false :: true:false 1118.42/292.39 le :: 0':s -> 0':s -> true:false 1118.42/292.39 min :: nil:cons -> 0':s 1118.42/292.39 cons :: 0':s -> nil:cons -> nil:cons 1118.42/292.39 nil :: nil:cons 1118.42/292.39 ifmin :: true:false -> nil:cons -> 0':s 1118.42/292.39 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 selsort :: nil:cons -> nil:cons 1118.42/292.39 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.39 hole_true:false1_0 :: true:false 1118.42/292.39 hole_0':s2_0 :: 0':s 1118.42/292.39 hole_nil:cons3_0 :: nil:cons 1118.42/292.39 gen_0':s4_0 :: Nat -> 0':s 1118.42/292.39 gen_nil:cons5_0 :: Nat -> nil:cons 1118.42/292.39 1118.42/292.39 1118.42/292.39 Generator Equations: 1118.42/292.39 gen_0':s4_0(0) <=> 0' 1118.42/292.39 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.42/292.39 gen_nil:cons5_0(0) <=> nil 1118.42/292.39 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1118.42/292.39 1118.42/292.39 1118.42/292.39 The following defined symbols remain to be analysed: 1118.42/292.39 eq, le, min, replace, selsort 1118.42/292.39 1118.42/292.39 They will be analysed ascendingly in the following order: 1118.42/292.39 eq < replace 1118.42/292.39 eq < selsort 1118.42/292.39 le < min 1118.42/292.39 min < selsort 1118.42/292.39 replace < selsort 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (53) RewriteLemmaProof (LOWER BOUND(ID)) 1118.42/292.39 Proved the following rewrite lemma: 1118.42/292.39 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1118.42/292.39 1118.42/292.39 Induction Base: 1118.42/292.39 eq(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1118.42/292.39 true 1118.42/292.39 1118.42/292.39 Induction Step: 1118.42/292.39 eq(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1) 1118.42/292.39 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH 1118.42/292.39 true 1118.42/292.39 1118.42/292.39 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (54) 1118.42/292.39 Complex Obligation (BEST) 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (55) 1118.42/292.39 Obligation: 1118.42/292.39 Proved the lower bound n^1 for the following obligation: 1118.42/292.39 1118.42/292.39 Innermost TRS: 1118.42/292.39 Rules: 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 Types: 1118.42/292.39 eq :: 0':s -> 0':s -> true:false 1118.42/292.39 0' :: 0':s 1118.42/292.39 true :: true:false 1118.42/292.39 s :: 0':s -> 0':s 1118.42/292.39 false :: true:false 1118.42/292.39 le :: 0':s -> 0':s -> true:false 1118.42/292.39 min :: nil:cons -> 0':s 1118.42/292.39 cons :: 0':s -> nil:cons -> nil:cons 1118.42/292.39 nil :: nil:cons 1118.42/292.39 ifmin :: true:false -> nil:cons -> 0':s 1118.42/292.39 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 selsort :: nil:cons -> nil:cons 1118.42/292.39 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.39 hole_true:false1_0 :: true:false 1118.42/292.39 hole_0':s2_0 :: 0':s 1118.42/292.39 hole_nil:cons3_0 :: nil:cons 1118.42/292.39 gen_0':s4_0 :: Nat -> 0':s 1118.42/292.39 gen_nil:cons5_0 :: Nat -> nil:cons 1118.42/292.39 1118.42/292.39 1118.42/292.39 Generator Equations: 1118.42/292.39 gen_0':s4_0(0) <=> 0' 1118.42/292.39 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.42/292.39 gen_nil:cons5_0(0) <=> nil 1118.42/292.39 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1118.42/292.39 1118.42/292.39 1118.42/292.39 The following defined symbols remain to be analysed: 1118.42/292.39 eq, le, min, replace, selsort 1118.42/292.39 1118.42/292.39 They will be analysed ascendingly in the following order: 1118.42/292.39 eq < replace 1118.42/292.39 eq < selsort 1118.42/292.39 le < min 1118.42/292.39 min < selsort 1118.42/292.39 replace < selsort 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (56) LowerBoundPropagationProof (FINISHED) 1118.42/292.39 Propagated lower bound. 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (57) 1118.42/292.39 BOUNDS(n^1, INF) 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (58) 1118.42/292.39 Obligation: 1118.42/292.39 Innermost TRS: 1118.42/292.39 Rules: 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 Types: 1118.42/292.39 eq :: 0':s -> 0':s -> true:false 1118.42/292.39 0' :: 0':s 1118.42/292.39 true :: true:false 1118.42/292.39 s :: 0':s -> 0':s 1118.42/292.39 false :: true:false 1118.42/292.39 le :: 0':s -> 0':s -> true:false 1118.42/292.39 min :: nil:cons -> 0':s 1118.42/292.39 cons :: 0':s -> nil:cons -> nil:cons 1118.42/292.39 nil :: nil:cons 1118.42/292.39 ifmin :: true:false -> nil:cons -> 0':s 1118.42/292.39 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 selsort :: nil:cons -> nil:cons 1118.42/292.39 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.39 hole_true:false1_0 :: true:false 1118.42/292.39 hole_0':s2_0 :: 0':s 1118.42/292.39 hole_nil:cons3_0 :: nil:cons 1118.42/292.39 gen_0':s4_0 :: Nat -> 0':s 1118.42/292.39 gen_nil:cons5_0 :: Nat -> nil:cons 1118.42/292.39 1118.42/292.39 1118.42/292.39 Lemmas: 1118.42/292.39 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1118.42/292.39 1118.42/292.39 1118.42/292.39 Generator Equations: 1118.42/292.39 gen_0':s4_0(0) <=> 0' 1118.42/292.39 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.42/292.39 gen_nil:cons5_0(0) <=> nil 1118.42/292.39 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1118.42/292.39 1118.42/292.39 1118.42/292.39 The following defined symbols remain to be analysed: 1118.42/292.39 le, min, replace, selsort 1118.42/292.39 1118.42/292.39 They will be analysed ascendingly in the following order: 1118.42/292.39 le < min 1118.42/292.39 min < selsort 1118.42/292.39 replace < selsort 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (59) RewriteLemmaProof (LOWER BOUND(ID)) 1118.42/292.39 Proved the following rewrite lemma: 1118.42/292.39 le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0) 1118.42/292.39 1118.42/292.39 Induction Base: 1118.42/292.39 le(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1118.42/292.39 true 1118.42/292.39 1118.42/292.39 Induction Step: 1118.42/292.39 le(gen_0':s4_0(+(n560_0, 1)), gen_0':s4_0(+(n560_0, 1))) ->_R^Omega(1) 1118.42/292.39 le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) ->_IH 1118.42/292.39 true 1118.42/292.39 1118.42/292.39 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (60) 1118.42/292.39 Obligation: 1118.42/292.39 Innermost TRS: 1118.42/292.39 Rules: 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 Types: 1118.42/292.39 eq :: 0':s -> 0':s -> true:false 1118.42/292.39 0' :: 0':s 1118.42/292.39 true :: true:false 1118.42/292.39 s :: 0':s -> 0':s 1118.42/292.39 false :: true:false 1118.42/292.39 le :: 0':s -> 0':s -> true:false 1118.42/292.39 min :: nil:cons -> 0':s 1118.42/292.39 cons :: 0':s -> nil:cons -> nil:cons 1118.42/292.39 nil :: nil:cons 1118.42/292.39 ifmin :: true:false -> nil:cons -> 0':s 1118.42/292.39 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 selsort :: nil:cons -> nil:cons 1118.42/292.39 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.39 hole_true:false1_0 :: true:false 1118.42/292.39 hole_0':s2_0 :: 0':s 1118.42/292.39 hole_nil:cons3_0 :: nil:cons 1118.42/292.39 gen_0':s4_0 :: Nat -> 0':s 1118.42/292.39 gen_nil:cons5_0 :: Nat -> nil:cons 1118.42/292.39 1118.42/292.39 1118.42/292.39 Lemmas: 1118.42/292.39 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1118.42/292.39 le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0) 1118.42/292.39 1118.42/292.39 1118.42/292.39 Generator Equations: 1118.42/292.39 gen_0':s4_0(0) <=> 0' 1118.42/292.39 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.42/292.39 gen_nil:cons5_0(0) <=> nil 1118.42/292.39 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1118.42/292.39 1118.42/292.39 1118.42/292.39 The following defined symbols remain to be analysed: 1118.42/292.39 min, replace, selsort 1118.42/292.39 1118.42/292.39 They will be analysed ascendingly in the following order: 1118.42/292.39 min < selsort 1118.42/292.39 replace < selsort 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (61) RewriteLemmaProof (LOWER BOUND(ID)) 1118.42/292.39 Proved the following rewrite lemma: 1118.42/292.39 min(gen_nil:cons5_0(+(1, n907_0))) -> gen_0':s4_0(0), rt in Omega(1 + n907_0) 1118.42/292.39 1118.42/292.39 Induction Base: 1118.42/292.39 min(gen_nil:cons5_0(+(1, 0))) ->_R^Omega(1) 1118.42/292.39 0' 1118.42/292.39 1118.42/292.39 Induction Step: 1118.42/292.39 min(gen_nil:cons5_0(+(1, +(n907_0, 1)))) ->_R^Omega(1) 1118.42/292.39 ifmin(le(0', 0'), cons(0', cons(0', gen_nil:cons5_0(n907_0)))) ->_L^Omega(1) 1118.42/292.39 ifmin(true, cons(0', cons(0', gen_nil:cons5_0(n907_0)))) ->_R^Omega(1) 1118.42/292.39 min(cons(0', gen_nil:cons5_0(n907_0))) ->_IH 1118.42/292.39 gen_0':s4_0(0) 1118.42/292.39 1118.42/292.39 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (62) 1118.42/292.39 Obligation: 1118.42/292.39 Innermost TRS: 1118.42/292.39 Rules: 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 Types: 1118.42/292.39 eq :: 0':s -> 0':s -> true:false 1118.42/292.39 0' :: 0':s 1118.42/292.39 true :: true:false 1118.42/292.39 s :: 0':s -> 0':s 1118.42/292.39 false :: true:false 1118.42/292.39 le :: 0':s -> 0':s -> true:false 1118.42/292.39 min :: nil:cons -> 0':s 1118.42/292.39 cons :: 0':s -> nil:cons -> nil:cons 1118.42/292.39 nil :: nil:cons 1118.42/292.39 ifmin :: true:false -> nil:cons -> 0':s 1118.42/292.39 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 selsort :: nil:cons -> nil:cons 1118.42/292.39 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.39 hole_true:false1_0 :: true:false 1118.42/292.39 hole_0':s2_0 :: 0':s 1118.42/292.39 hole_nil:cons3_0 :: nil:cons 1118.42/292.39 gen_0':s4_0 :: Nat -> 0':s 1118.42/292.39 gen_nil:cons5_0 :: Nat -> nil:cons 1118.42/292.39 1118.42/292.39 1118.42/292.39 Lemmas: 1118.42/292.39 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1118.42/292.39 le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0) 1118.42/292.39 min(gen_nil:cons5_0(+(1, n907_0))) -> gen_0':s4_0(0), rt in Omega(1 + n907_0) 1118.42/292.39 1118.42/292.39 1118.42/292.39 Generator Equations: 1118.42/292.39 gen_0':s4_0(0) <=> 0' 1118.42/292.39 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.42/292.39 gen_nil:cons5_0(0) <=> nil 1118.42/292.39 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1118.42/292.39 1118.42/292.39 1118.42/292.39 The following defined symbols remain to be analysed: 1118.42/292.39 replace, selsort 1118.42/292.39 1118.42/292.39 They will be analysed ascendingly in the following order: 1118.42/292.39 replace < selsort 1118.42/292.39 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (63) RewriteLemmaProof (LOWER BOUND(ID)) 1118.42/292.39 Proved the following rewrite lemma: 1118.42/292.39 selsort(gen_nil:cons5_0(n1660_0)) -> gen_nil:cons5_0(n1660_0), rt in Omega(1 + n1660_0 + n1660_0^2) 1118.42/292.39 1118.42/292.39 Induction Base: 1118.42/292.39 selsort(gen_nil:cons5_0(0)) ->_R^Omega(1) 1118.42/292.39 nil 1118.42/292.39 1118.42/292.39 Induction Step: 1118.42/292.39 selsort(gen_nil:cons5_0(+(n1660_0, 1))) ->_R^Omega(1) 1118.42/292.39 ifselsort(eq(0', min(cons(0', gen_nil:cons5_0(n1660_0)))), cons(0', gen_nil:cons5_0(n1660_0))) ->_L^Omega(1 + n1660_0) 1118.42/292.39 ifselsort(eq(0', gen_0':s4_0(0)), cons(0', gen_nil:cons5_0(n1660_0))) ->_L^Omega(1) 1118.42/292.39 ifselsort(true, cons(0', gen_nil:cons5_0(n1660_0))) ->_R^Omega(1) 1118.42/292.39 cons(0', selsort(gen_nil:cons5_0(n1660_0))) ->_IH 1118.42/292.39 cons(0', gen_nil:cons5_0(c1661_0)) 1118.42/292.39 1118.42/292.39 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (64) 1118.42/292.39 Obligation: 1118.42/292.39 Proved the lower bound n^2 for the following obligation: 1118.42/292.39 1118.42/292.39 Innermost TRS: 1118.42/292.39 Rules: 1118.42/292.39 eq(0', 0') -> true 1118.42/292.39 eq(0', s(Y)) -> false 1118.42/292.39 eq(s(X), 0') -> false 1118.42/292.39 eq(s(X), s(Y)) -> eq(X, Y) 1118.42/292.39 le(0', Y) -> true 1118.42/292.39 le(s(X), 0') -> false 1118.42/292.39 le(s(X), s(Y)) -> le(X, Y) 1118.42/292.39 min(cons(0', nil)) -> 0' 1118.42/292.39 min(cons(s(N), nil)) -> s(N) 1118.42/292.39 min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) 1118.42/292.39 ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) 1118.42/292.39 ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) 1118.42/292.39 replace(N, M, nil) -> nil 1118.42/292.39 replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) 1118.42/292.39 ifrepl(true, N, M, cons(K, L)) -> cons(M, L) 1118.42/292.39 ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) 1118.42/292.39 selsort(nil) -> nil 1118.42/292.39 selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) 1118.42/292.39 ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) 1118.42/292.39 ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) 1118.42/292.39 1118.42/292.39 Types: 1118.42/292.39 eq :: 0':s -> 0':s -> true:false 1118.42/292.39 0' :: 0':s 1118.42/292.39 true :: true:false 1118.42/292.39 s :: 0':s -> 0':s 1118.42/292.39 false :: true:false 1118.42/292.39 le :: 0':s -> 0':s -> true:false 1118.42/292.39 min :: nil:cons -> 0':s 1118.42/292.39 cons :: 0':s -> nil:cons -> nil:cons 1118.42/292.39 nil :: nil:cons 1118.42/292.39 ifmin :: true:false -> nil:cons -> 0':s 1118.42/292.39 replace :: 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1118.42/292.39 selsort :: nil:cons -> nil:cons 1118.42/292.39 ifselsort :: true:false -> nil:cons -> nil:cons 1118.42/292.39 hole_true:false1_0 :: true:false 1118.42/292.39 hole_0':s2_0 :: 0':s 1118.42/292.39 hole_nil:cons3_0 :: nil:cons 1118.42/292.39 gen_0':s4_0 :: Nat -> 0':s 1118.42/292.39 gen_nil:cons5_0 :: Nat -> nil:cons 1118.42/292.39 1118.42/292.39 1118.42/292.39 Lemmas: 1118.42/292.39 eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1118.42/292.39 le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0) 1118.42/292.39 min(gen_nil:cons5_0(+(1, n907_0))) -> gen_0':s4_0(0), rt in Omega(1 + n907_0) 1118.42/292.39 1118.42/292.39 1118.42/292.39 Generator Equations: 1118.42/292.39 gen_0':s4_0(0) <=> 0' 1118.42/292.39 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.42/292.39 gen_nil:cons5_0(0) <=> nil 1118.42/292.39 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1118.42/292.39 1118.42/292.39 1118.42/292.39 The following defined symbols remain to be analysed: 1118.42/292.39 selsort 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (65) LowerBoundPropagationProof (FINISHED) 1118.42/292.39 Propagated lower bound. 1118.42/292.39 ---------------------------------------- 1118.42/292.39 1118.42/292.39 (66) 1118.42/292.39 BOUNDS(n^2, INF) 1118.68/292.44 EOF