361.37/291.57 WORST_CASE(Omega(n^1), O(n^2)) 361.37/291.59 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 361.37/291.59 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 361.37/291.59 361.37/291.59 361.37/291.59 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 361.37/291.59 361.37/291.59 (0) CpxRelTRS 361.37/291.59 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 199 ms] 361.37/291.59 (2) CpxRelTRS 361.37/291.59 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 361.37/291.59 (4) CpxWeightedTrs 361.37/291.59 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 361.37/291.59 (6) CpxTypedWeightedTrs 361.37/291.59 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (8) CpxTypedWeightedCompleteTrs 361.37/291.59 (9) NarrowingProof [BOTH BOUNDS(ID, ID), 1 ms] 361.37/291.59 (10) CpxTypedWeightedCompleteTrs 361.37/291.59 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (12) CpxRNTS 361.37/291.59 (13) InliningProof [UPPER BOUND(ID), 718 ms] 361.37/291.59 (14) CpxRNTS 361.37/291.59 (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 361.37/291.59 (16) CpxRNTS 361.37/291.59 (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 361.37/291.59 (18) CpxRNTS 361.37/291.59 (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (20) CpxRNTS 361.37/291.59 (21) IntTrsBoundProof [UPPER BOUND(ID), 1114 ms] 361.37/291.59 (22) CpxRNTS 361.37/291.59 (23) IntTrsBoundProof [UPPER BOUND(ID), 258 ms] 361.37/291.59 (24) CpxRNTS 361.37/291.59 (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (26) CpxRNTS 361.37/291.59 (27) IntTrsBoundProof [UPPER BOUND(ID), 383 ms] 361.37/291.59 (28) CpxRNTS 361.37/291.59 (29) IntTrsBoundProof [UPPER BOUND(ID), 83 ms] 361.37/291.59 (30) CpxRNTS 361.37/291.59 (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (32) CpxRNTS 361.37/291.59 (33) IntTrsBoundProof [UPPER BOUND(ID), 179 ms] 361.37/291.59 (34) CpxRNTS 361.37/291.59 (35) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (36) CpxRNTS 361.37/291.59 (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (38) CpxRNTS 361.37/291.59 (39) IntTrsBoundProof [UPPER BOUND(ID), 392 ms] 361.37/291.59 (40) CpxRNTS 361.37/291.59 (41) IntTrsBoundProof [UPPER BOUND(ID), 120 ms] 361.37/291.59 (42) CpxRNTS 361.37/291.59 (43) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (44) CpxRNTS 361.37/291.59 (45) IntTrsBoundProof [UPPER BOUND(ID), 254 ms] 361.37/291.59 (46) CpxRNTS 361.37/291.59 (47) IntTrsBoundProof [UPPER BOUND(ID), 64 ms] 361.37/291.59 (48) CpxRNTS 361.37/291.59 (49) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (50) CpxRNTS 361.37/291.59 (51) IntTrsBoundProof [UPPER BOUND(ID), 268 ms] 361.37/291.59 (52) CpxRNTS 361.37/291.59 (53) IntTrsBoundProof [UPPER BOUND(ID), 74 ms] 361.37/291.59 (54) CpxRNTS 361.37/291.59 (55) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (56) CpxRNTS 361.37/291.59 (57) IntTrsBoundProof [UPPER BOUND(ID), 337 ms] 361.37/291.59 (58) CpxRNTS 361.37/291.59 (59) IntTrsBoundProof [UPPER BOUND(ID), 115 ms] 361.37/291.59 (60) CpxRNTS 361.37/291.59 (61) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 361.37/291.59 (62) CpxRNTS 361.37/291.59 (63) IntTrsBoundProof [UPPER BOUND(ID), 177 ms] 361.37/291.59 (64) CpxRNTS 361.37/291.59 (65) IntTrsBoundProof [UPPER BOUND(ID), 52 ms] 361.37/291.59 (66) CpxRNTS 361.37/291.59 (67) FinalProof [FINISHED, 0 ms] 361.37/291.59 (68) BOUNDS(1, n^2) 361.37/291.59 (69) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 361.37/291.59 (70) TRS for Loop Detection 361.37/291.59 (71) DecreasingLoopProof [LOWER BOUND(ID), 28 ms] 361.37/291.59 (72) BEST 361.37/291.59 (73) proven lower bound 361.37/291.59 (74) LowerBoundPropagationProof [FINISHED, 0 ms] 361.37/291.59 (75) BOUNDS(n^1, INF) 361.37/291.59 (76) TRS for Loop Detection 361.37/291.59 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (0) 361.37/291.59 Obligation: 361.37/291.59 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 361.37/291.59 361.37/291.59 361.37/291.59 The TRS R consists of the following rules: 361.37/291.59 361.37/291.59 #less(@x, @y) -> #cklt(#compare(@x, @y)) 361.37/291.59 findMin(@l) -> findMin#1(@l) 361.37/291.59 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) 361.37/291.59 findMin#1(nil) -> nil 361.37/291.59 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) 361.37/291.59 findMin#2(nil, @x) -> ::(@x, nil) 361.37/291.59 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) 361.37/291.59 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) 361.37/291.59 minSort(@l) -> minSort#1(findMin(@l)) 361.37/291.59 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) 361.37/291.59 minSort#1(nil) -> nil 361.37/291.59 361.37/291.59 The (relative) TRS S consists of the following rules: 361.37/291.59 361.37/291.59 #cklt(#EQ) -> #false 361.37/291.59 #cklt(#GT) -> #false 361.37/291.59 #cklt(#LT) -> #true 361.37/291.59 #compare(#0, #0) -> #EQ 361.37/291.59 #compare(#0, #neg(@y)) -> #GT 361.37/291.59 #compare(#0, #pos(@y)) -> #LT 361.37/291.59 #compare(#0, #s(@y)) -> #LT 361.37/291.59 #compare(#neg(@x), #0) -> #LT 361.37/291.59 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) 361.37/291.59 #compare(#neg(@x), #pos(@y)) -> #LT 361.37/291.59 #compare(#pos(@x), #0) -> #GT 361.37/291.59 #compare(#pos(@x), #neg(@y)) -> #GT 361.37/291.59 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) 361.37/291.59 #compare(#s(@x), #0) -> #GT 361.37/291.59 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) 361.37/291.59 361.37/291.59 Rewrite Strategy: INNERMOST 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 361.37/291.59 proved termination of relative rules 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (2) 361.37/291.59 Obligation: 361.37/291.59 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 361.37/291.59 361.37/291.59 361.37/291.59 The TRS R consists of the following rules: 361.37/291.59 361.37/291.59 #less(@x, @y) -> #cklt(#compare(@x, @y)) 361.37/291.59 findMin(@l) -> findMin#1(@l) 361.37/291.59 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) 361.37/291.59 findMin#1(nil) -> nil 361.37/291.59 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) 361.37/291.59 findMin#2(nil, @x) -> ::(@x, nil) 361.37/291.59 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) 361.37/291.59 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) 361.37/291.59 minSort(@l) -> minSort#1(findMin(@l)) 361.37/291.59 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) 361.37/291.59 minSort#1(nil) -> nil 361.37/291.59 361.37/291.59 The (relative) TRS S consists of the following rules: 361.37/291.59 361.37/291.59 #cklt(#EQ) -> #false 361.37/291.59 #cklt(#GT) -> #false 361.37/291.59 #cklt(#LT) -> #true 361.37/291.59 #compare(#0, #0) -> #EQ 361.37/291.59 #compare(#0, #neg(@y)) -> #GT 361.37/291.59 #compare(#0, #pos(@y)) -> #LT 361.37/291.59 #compare(#0, #s(@y)) -> #LT 361.37/291.59 #compare(#neg(@x), #0) -> #LT 361.37/291.59 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) 361.37/291.59 #compare(#neg(@x), #pos(@y)) -> #LT 361.37/291.59 #compare(#pos(@x), #0) -> #GT 361.37/291.59 #compare(#pos(@x), #neg(@y)) -> #GT 361.37/291.59 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) 361.37/291.59 #compare(#s(@x), #0) -> #GT 361.37/291.59 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) 361.37/291.59 361.37/291.59 Rewrite Strategy: INNERMOST 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 361.37/291.59 Transformed relative TRS to weighted TRS 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (4) 361.37/291.59 Obligation: 361.37/291.59 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 361.37/291.59 361.37/291.59 361.37/291.59 The TRS R consists of the following rules: 361.37/291.59 361.37/291.59 #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] 361.37/291.59 findMin(@l) -> findMin#1(@l) [1] 361.37/291.59 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) [1] 361.37/291.59 findMin#1(nil) -> nil [1] 361.37/291.59 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) [1] 361.37/291.59 findMin#2(nil, @x) -> ::(@x, nil) [1] 361.37/291.59 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) [1] 361.37/291.59 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] 361.37/291.59 minSort(@l) -> minSort#1(findMin(@l)) [1] 361.37/291.59 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) [1] 361.37/291.59 minSort#1(nil) -> nil [1] 361.37/291.59 #cklt(#EQ) -> #false [0] 361.37/291.59 #cklt(#GT) -> #false [0] 361.37/291.59 #cklt(#LT) -> #true [0] 361.37/291.59 #compare(#0, #0) -> #EQ [0] 361.37/291.59 #compare(#0, #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#0, #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#0, #s(@y)) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #0) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] 361.37/291.59 #compare(#neg(@x), #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#pos(@x), #0) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] 361.37/291.59 #compare(#s(@x), #0) -> #GT [0] 361.37/291.59 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] 361.37/291.59 361.37/291.59 Rewrite Strategy: INNERMOST 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 361.37/291.59 Infered types. 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (6) 361.37/291.59 Obligation: 361.37/291.59 Runtime Complexity Weighted TRS with Types. 361.37/291.59 The TRS R consists of the following rules: 361.37/291.59 361.37/291.59 #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] 361.37/291.59 findMin(@l) -> findMin#1(@l) [1] 361.37/291.59 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) [1] 361.37/291.59 findMin#1(nil) -> nil [1] 361.37/291.59 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) [1] 361.37/291.59 findMin#2(nil, @x) -> ::(@x, nil) [1] 361.37/291.59 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) [1] 361.37/291.59 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] 361.37/291.59 minSort(@l) -> minSort#1(findMin(@l)) [1] 361.37/291.59 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) [1] 361.37/291.59 minSort#1(nil) -> nil [1] 361.37/291.59 #cklt(#EQ) -> #false [0] 361.37/291.59 #cklt(#GT) -> #false [0] 361.37/291.59 #cklt(#LT) -> #true [0] 361.37/291.59 #compare(#0, #0) -> #EQ [0] 361.37/291.59 #compare(#0, #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#0, #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#0, #s(@y)) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #0) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] 361.37/291.59 #compare(#neg(@x), #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#pos(@x), #0) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] 361.37/291.59 #compare(#s(@x), #0) -> #GT [0] 361.37/291.59 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] 361.37/291.59 361.37/291.59 The TRS has the following type information: 361.37/291.59 #less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true 361.37/291.59 #cklt :: #EQ:#GT:#LT -> #false:#true 361.37/291.59 #compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT 361.37/291.59 findMin :: :::nil -> :::nil 361.37/291.59 findMin#1 :: :::nil -> :::nil 361.37/291.59 :: :: #0:#neg:#pos:#s -> :::nil -> :::nil 361.37/291.59 findMin#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil 361.37/291.59 nil :: :::nil 361.37/291.59 findMin#3 :: #false:#true -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> :::nil -> :::nil 361.37/291.59 #false :: #false:#true 361.37/291.59 #true :: #false:#true 361.37/291.59 minSort :: :::nil -> :::nil 361.37/291.59 minSort#1 :: :::nil -> :::nil 361.37/291.59 #EQ :: #EQ:#GT:#LT 361.37/291.59 #GT :: #EQ:#GT:#LT 361.37/291.59 #LT :: #EQ:#GT:#LT 361.37/291.59 #0 :: #0:#neg:#pos:#s 361.37/291.59 #neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 #pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 #s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 361.37/291.59 Rewrite Strategy: INNERMOST 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (7) CompletionProof (UPPER BOUND(ID)) 361.37/291.59 The transformation into a RNTS is sound, since: 361.37/291.59 361.37/291.59 (a) The obligation is a constructor system where every type has a constant constructor, 361.37/291.59 361.37/291.59 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 361.37/291.59 361.37/291.59 minSort_1 361.37/291.59 minSort#1_1 361.37/291.59 361.37/291.59 (c) The following functions are completely defined: 361.37/291.59 361.37/291.59 #less_2 361.37/291.59 findMin_1 361.37/291.59 findMin#1_1 361.37/291.59 findMin#2_2 361.37/291.59 findMin#3_4 361.37/291.59 #cklt_1 361.37/291.59 #compare_2 361.37/291.59 361.37/291.59 Due to the following rules being added: 361.37/291.59 361.37/291.59 #cklt(v0) -> null_#cklt [0] 361.37/291.59 #compare(v0, v1) -> null_#compare [0] 361.37/291.59 findMin#3(v0, v1, v2, v3) -> nil [0] 361.37/291.59 361.37/291.59 And the following fresh constants: null_#cklt, null_#compare 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (8) 361.37/291.59 Obligation: 361.37/291.59 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 361.37/291.59 361.37/291.59 Runtime Complexity Weighted TRS with Types. 361.37/291.59 The TRS R consists of the following rules: 361.37/291.59 361.37/291.59 #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] 361.37/291.59 findMin(@l) -> findMin#1(@l) [1] 361.37/291.59 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) [1] 361.37/291.59 findMin#1(nil) -> nil [1] 361.37/291.59 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) [1] 361.37/291.59 findMin#2(nil, @x) -> ::(@x, nil) [1] 361.37/291.59 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) [1] 361.37/291.59 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] 361.37/291.59 minSort(@l) -> minSort#1(findMin(@l)) [1] 361.37/291.59 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) [1] 361.37/291.59 minSort#1(nil) -> nil [1] 361.37/291.59 #cklt(#EQ) -> #false [0] 361.37/291.59 #cklt(#GT) -> #false [0] 361.37/291.59 #cklt(#LT) -> #true [0] 361.37/291.59 #compare(#0, #0) -> #EQ [0] 361.37/291.59 #compare(#0, #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#0, #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#0, #s(@y)) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #0) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] 361.37/291.59 #compare(#neg(@x), #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#pos(@x), #0) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] 361.37/291.59 #compare(#s(@x), #0) -> #GT [0] 361.37/291.59 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] 361.37/291.59 #cklt(v0) -> null_#cklt [0] 361.37/291.59 #compare(v0, v1) -> null_#compare [0] 361.37/291.59 findMin#3(v0, v1, v2, v3) -> nil [0] 361.37/291.59 361.37/291.59 The TRS has the following type information: 361.37/291.59 #less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true:null_#cklt 361.37/291.59 #cklt :: #EQ:#GT:#LT:null_#compare -> #false:#true:null_#cklt 361.37/291.59 #compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT:null_#compare 361.37/291.59 findMin :: :::nil -> :::nil 361.37/291.59 findMin#1 :: :::nil -> :::nil 361.37/291.59 :: :: #0:#neg:#pos:#s -> :::nil -> :::nil 361.37/291.59 findMin#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil 361.37/291.59 nil :: :::nil 361.37/291.59 findMin#3 :: #false:#true:null_#cklt -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> :::nil -> :::nil 361.37/291.59 #false :: #false:#true:null_#cklt 361.37/291.59 #true :: #false:#true:null_#cklt 361.37/291.59 minSort :: :::nil -> :::nil 361.37/291.59 minSort#1 :: :::nil -> :::nil 361.37/291.59 #EQ :: #EQ:#GT:#LT:null_#compare 361.37/291.59 #GT :: #EQ:#GT:#LT:null_#compare 361.37/291.59 #LT :: #EQ:#GT:#LT:null_#compare 361.37/291.59 #0 :: #0:#neg:#pos:#s 361.37/291.59 #neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 #pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 #s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 null_#cklt :: #false:#true:null_#cklt 361.37/291.59 null_#compare :: #EQ:#GT:#LT:null_#compare 361.37/291.59 361.37/291.59 Rewrite Strategy: INNERMOST 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (9) NarrowingProof (BOTH BOUNDS(ID, ID)) 361.37/291.59 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (10) 361.37/291.59 Obligation: 361.37/291.59 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 361.37/291.59 361.37/291.59 Runtime Complexity Weighted TRS with Types. 361.37/291.59 The TRS R consists of the following rules: 361.37/291.59 361.37/291.59 #less(#0, #0) -> #cklt(#EQ) [1] 361.37/291.59 #less(#0, #neg(@y')) -> #cklt(#GT) [1] 361.37/291.59 #less(#0, #pos(@y'')) -> #cklt(#LT) [1] 361.37/291.59 #less(#0, #s(@y1)) -> #cklt(#LT) [1] 361.37/291.59 #less(#neg(@x'), #0) -> #cklt(#LT) [1] 361.37/291.59 #less(#neg(@x''), #neg(@y2)) -> #cklt(#compare(@y2, @x'')) [1] 361.37/291.59 #less(#neg(@x1), #pos(@y3)) -> #cklt(#LT) [1] 361.37/291.59 #less(#pos(@x2), #0) -> #cklt(#GT) [1] 361.37/291.59 #less(#pos(@x3), #neg(@y4)) -> #cklt(#GT) [1] 361.37/291.59 #less(#pos(@x4), #pos(@y5)) -> #cklt(#compare(@x4, @y5)) [1] 361.37/291.59 #less(#s(@x5), #0) -> #cklt(#GT) [1] 361.37/291.59 #less(#s(@x6), #s(@y6)) -> #cklt(#compare(@x6, @y6)) [1] 361.37/291.59 #less(@x, @y) -> #cklt(null_#compare) [1] 361.37/291.59 findMin(@l) -> findMin#1(@l) [1] 361.37/291.59 findMin#1(::(@x, @xs)) -> findMin#2(findMin#1(@xs), @x) [2] 361.37/291.59 findMin#1(nil) -> nil [1] 361.37/291.59 findMin#2(::(@y, @ys), @x) -> findMin#3(#cklt(#compare(@x, @y)), @x, @y, @ys) [2] 361.37/291.59 findMin#2(nil, @x) -> ::(@x, nil) [1] 361.37/291.59 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) [1] 361.37/291.59 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] 361.37/291.59 minSort(@l) -> minSort#1(findMin#1(@l)) [2] 361.37/291.59 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) [1] 361.37/291.59 minSort#1(nil) -> nil [1] 361.37/291.59 #cklt(#EQ) -> #false [0] 361.37/291.59 #cklt(#GT) -> #false [0] 361.37/291.59 #cklt(#LT) -> #true [0] 361.37/291.59 #compare(#0, #0) -> #EQ [0] 361.37/291.59 #compare(#0, #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#0, #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#0, #s(@y)) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #0) -> #LT [0] 361.37/291.59 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] 361.37/291.59 #compare(#neg(@x), #pos(@y)) -> #LT [0] 361.37/291.59 #compare(#pos(@x), #0) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #neg(@y)) -> #GT [0] 361.37/291.59 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] 361.37/291.59 #compare(#s(@x), #0) -> #GT [0] 361.37/291.59 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] 361.37/291.59 #cklt(v0) -> null_#cklt [0] 361.37/291.59 #compare(v0, v1) -> null_#compare [0] 361.37/291.59 findMin#3(v0, v1, v2, v3) -> nil [0] 361.37/291.59 361.37/291.59 The TRS has the following type information: 361.37/291.59 #less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true:null_#cklt 361.37/291.59 #cklt :: #EQ:#GT:#LT:null_#compare -> #false:#true:null_#cklt 361.37/291.59 #compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT:null_#compare 361.37/291.59 findMin :: :::nil -> :::nil 361.37/291.59 findMin#1 :: :::nil -> :::nil 361.37/291.59 :: :: #0:#neg:#pos:#s -> :::nil -> :::nil 361.37/291.59 findMin#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil 361.37/291.59 nil :: :::nil 361.37/291.59 findMin#3 :: #false:#true:null_#cklt -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> :::nil -> :::nil 361.37/291.59 #false :: #false:#true:null_#cklt 361.37/291.59 #true :: #false:#true:null_#cklt 361.37/291.59 minSort :: :::nil -> :::nil 361.37/291.59 minSort#1 :: :::nil -> :::nil 361.37/291.59 #EQ :: #EQ:#GT:#LT:null_#compare 361.37/291.59 #GT :: #EQ:#GT:#LT:null_#compare 361.37/291.59 #LT :: #EQ:#GT:#LT:null_#compare 361.37/291.59 #0 :: #0:#neg:#pos:#s 361.37/291.59 #neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 #pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 #s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s 361.37/291.59 null_#cklt :: #false:#true:null_#cklt 361.37/291.59 null_#compare :: #EQ:#GT:#LT:null_#compare 361.37/291.59 361.37/291.59 Rewrite Strategy: INNERMOST 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 361.37/291.59 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 361.37/291.59 The constant constructors are abstracted as follows: 361.37/291.59 361.37/291.59 nil => 0 361.37/291.59 #false => 1 361.37/291.59 #true => 2 361.37/291.59 #EQ => 1 361.37/291.59 #GT => 2 361.37/291.59 #LT => 3 361.37/291.59 #0 => 0 361.37/291.59 null_#cklt => 0 361.37/291.59 null_#compare => 0 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (12) 361.37/291.59 Obligation: 361.37/291.59 Complexity RNTS consisting of the following rules: 361.37/291.59 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(@x, @y) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(@y, @x) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(3) :|: z' = 1 + @y'', @y'' >= 0, z = 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(3) :|: z' = 1 + @y1, @y1 >= 0, z = 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(3) :|: z = 1 + @x', @x' >= 0, z' = 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(3) :|: @y3 >= 0, @x1 >= 0, z' = 1 + @y3, z = 1 + @x1 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(2) :|: @y' >= 0, z' = 1 + @y', z = 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(2) :|: @x2 >= 0, z = 1 + @x2, z' = 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(2) :|: @x3 >= 0, z' = 1 + @y4, z = 1 + @x3, @y4 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(2) :|: z = 1 + @x5, @x5 >= 0, z' = 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(1) :|: z = 0, z' = 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(0) :|: z = @x, @x >= 0, z' = @y, @y >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(@x4, @y5)) :|: z' = 1 + @y5, @y5 >= 0, z = 1 + @x4, @x4 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(@x6, @y6)) :|: z = 1 + @x6, z' = 1 + @y6, @x6 >= 0, @y6 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(@y2, @x'')) :|: z = 1 + @x'', z' = 1 + @y2, @y2 >= 0, @x'' >= 0 361.37/291.59 findMin(z) -{ 1 }-> findMin#1(@l) :|: z = @l, @l >= 0 361.37/291.59 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(#compare(@x, @y)), @x, @y, @ys) :|: z = 1 + @y + @ys, @x >= 0, @y >= 0, z' = @x, @ys >= 0 361.37/291.59 findMin#2(z, z') -{ 1 }-> 1 + @x + 0 :|: @x >= 0, z = 0, z' = @x 361.37/291.59 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + @x + (1 + @y + @ys) :|: z = 2, @x >= 0, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + @y + (1 + @x + @ys) :|: @x >= 0, z = 1, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 361.37/291.59 minSort(z) -{ 2 }-> minSort#1(findMin#1(@l)) :|: z = @l, @l >= 0 361.37/291.59 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (13) InliningProof (UPPER BOUND(ID)) 361.37/291.59 Inlined the following terminating rules on right-hand sides where appropriate: 361.37/291.59 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + @x + (1 + @y + @ys) :|: z = 2, @x >= 0, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + @y + (1 + @x + @ys) :|: @x >= 0, z = 1, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 361.37/291.59 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (14) 361.37/291.59 Obligation: 361.37/291.59 Complexity RNTS consisting of the following rules: 361.37/291.59 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(@x, @y) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(@y, @x) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' = 1 + @y'', @y'' >= 0, z = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' = 1 + @y1, @y1 >= 0, z = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z = 1 + @x', @x' >= 0, z' = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: @y3 >= 0, @x1 >= 0, z' = 1 + @y3, z = 1 + @x1, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: @y' >= 0, z' = 1 + @y', z = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: @x2 >= 0, z = 1 + @x2, z' = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: @x3 >= 0, z' = 1 + @y4, z = 1 + @x3, @y4 >= 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z = 1 + @x5, @x5 >= 0, z' = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: @y' >= 0, z' = 1 + @y', z = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' = 1 + @y'', @y'' >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' = 1 + @y1, @y1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 1 + @x', @x' >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: @y3 >= 0, @x1 >= 0, z' = 1 + @y3, z = 1 + @x1, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: @x2 >= 0, z = 1 + @x2, z' = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: @x3 >= 0, z' = 1 + @y4, z = 1 + @x3, @y4 >= 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 1 + @x5, @x5 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = @x, @x >= 0, z' = @y, @y >= 0, v0 >= 0, 0 = v0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(@x4, @y5)) :|: z' = 1 + @y5, @y5 >= 0, z = 1 + @x4, @x4 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(@x6, @y6)) :|: z = 1 + @x6, z' = 1 + @y6, @x6 >= 0, @y6 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(@y2, @x'')) :|: z = 1 + @x'', z' = 1 + @y2, @y2 >= 0, @x'' >= 0 361.37/291.59 findMin(z) -{ 1 }-> findMin#1(@l) :|: z = @l, @l >= 0 361.37/291.59 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(#compare(@x, @y)), @x, @y, @ys) :|: z = 1 + @y + @ys, @x >= 0, @y >= 0, z' = @x, @ys >= 0 361.37/291.59 findMin#2(z, z') -{ 1 }-> 1 + @x + 0 :|: @x >= 0, z = 0, z' = @x 361.37/291.59 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + @x + (1 + @y + @ys) :|: z = 2, @x >= 0, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + @y + (1 + @x + @ys) :|: @x >= 0, z = 1, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 361.37/291.59 minSort(z) -{ 2 }-> minSort#1(findMin#1(@l)) :|: z = @l, @l >= 0 361.37/291.59 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (15) SimplificationProof (BOTH BOUNDS(ID, ID)) 361.37/291.59 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (16) 361.37/291.59 Obligation: 361.37/291.59 Complexity RNTS consisting of the following rules: 361.37/291.59 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z' - 1, z - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z - 1, z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z' - 1, z - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.59 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(#compare(z', @y)), z', @y, @ys) :|: z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.59 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.59 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.59 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 361.37/291.59 Found the following analysis order by SCC decomposition: 361.37/291.59 361.37/291.59 { #compare } 361.37/291.59 { findMin#3 } 361.37/291.59 { #cklt } 361.37/291.59 { #less } 361.37/291.59 { findMin#2 } 361.37/291.59 { findMin#1 } 361.37/291.59 { minSort#1, minSort } 361.37/291.59 { findMin } 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (18) 361.37/291.59 Obligation: 361.37/291.59 Complexity RNTS consisting of the following rules: 361.37/291.59 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z' - 1, z - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z - 1, z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z' - 1, z - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.59 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(#compare(z', @y)), z', @y, @ys) :|: z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.59 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.59 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.59 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 361.37/291.59 Function symbols to be analyzed: {#compare}, {findMin#3}, {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (19) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.59 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (20) 361.37/291.59 Obligation: 361.37/291.59 Complexity RNTS consisting of the following rules: 361.37/291.59 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z' - 1, z - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z - 1, z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z' - 1, z - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.59 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(#compare(z', @y)), z', @y, @ys) :|: z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.59 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.59 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.59 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 361.37/291.59 Function symbols to be analyzed: {#compare}, {findMin#3}, {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (21) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.59 361.37/291.59 Computed SIZE bound using CoFloCo for: #compare 361.37/291.59 after applying outer abstraction to obtain an ITS, 361.37/291.59 resulting in: O(1) with polynomial bound: 3 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (22) 361.37/291.59 Obligation: 361.37/291.59 Complexity RNTS consisting of the following rules: 361.37/291.59 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z' - 1, z - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z - 1, z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> #cklt(#compare(z' - 1, z - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.59 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.59 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(#compare(z', @y)), z', @y, @ys) :|: z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.59 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.59 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.59 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.59 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.59 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.59 361.37/291.59 Function symbols to be analyzed: {#compare}, {findMin#3}, {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.59 Previous analysis results are: 361.37/291.59 #compare: runtime: ?, size: O(1) [3] 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (23) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.59 361.37/291.59 Computed RUNTIME bound using CoFloCo for: #compare 361.37/291.59 after applying outer abstraction to obtain an ITS, 361.37/291.59 resulting in: O(1) with polynomial bound: 0 361.37/291.59 361.37/291.59 ---------------------------------------- 361.37/291.59 361.37/291.59 (24) 361.37/291.59 Obligation: 361.37/291.59 Complexity RNTS consisting of the following rules: 361.37/291.59 361.37/291.59 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.59 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.59 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.59 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #compare(z, z') -{ 0 }-> #compare(z' - 1, z - 1) :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.59 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(#compare(z - 1, z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(#compare(z' - 1, z - 1)) :|: z' - 1 >= 0, z - 1 >= 0 361.37/291.60 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.60 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(#compare(z', @y)), z', @y, @ys) :|: z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.60 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.60 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.60 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 361.37/291.60 Function symbols to be analyzed: {findMin#3}, {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.60 Previous analysis results are: 361.37/291.60 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.60 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (25) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.60 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (26) 361.37/291.60 Obligation: 361.37/291.60 Complexity RNTS consisting of the following rules: 361.37/291.60 361.37/291.60 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.60 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(s'') :|: s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(s1) :|: s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.60 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.60 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(s2), z', @y, @ys) :|: s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.60 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.60 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.60 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 361.37/291.60 Function symbols to be analyzed: {findMin#3}, {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.60 Previous analysis results are: 361.37/291.60 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.60 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (27) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.60 361.37/291.60 Computed SIZE bound using CoFloCo for: findMin#3 361.37/291.60 after applying outer abstraction to obtain an ITS, 361.37/291.60 resulting in: O(n^1) with polynomial bound: 2 + z' + z'' + z1 361.37/291.60 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (28) 361.37/291.60 Obligation: 361.37/291.60 Complexity RNTS consisting of the following rules: 361.37/291.60 361.37/291.60 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.60 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(s'') :|: s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(s1) :|: s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.60 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.60 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(s2), z', @y, @ys) :|: s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.60 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.60 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.60 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 361.37/291.60 Function symbols to be analyzed: {findMin#3}, {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.60 Previous analysis results are: 361.37/291.60 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.60 findMin#3: runtime: ?, size: O(n^1) [2 + z' + z'' + z1] 361.37/291.60 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (29) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.60 361.37/291.60 Computed RUNTIME bound using CoFloCo for: findMin#3 361.37/291.60 after applying outer abstraction to obtain an ITS, 361.37/291.60 resulting in: O(1) with polynomial bound: 1 361.37/291.60 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (30) 361.37/291.60 Obligation: 361.37/291.60 Complexity RNTS consisting of the following rules: 361.37/291.60 361.37/291.60 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.60 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.60 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.60 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(s'') :|: s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.60 #less(z, z') -{ 1 }-> #cklt(s1) :|: s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.60 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.60 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(s2), z', @y, @ys) :|: s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.60 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.60 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.60 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.60 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.60 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.60 361.37/291.60 Function symbols to be analyzed: {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.60 Previous analysis results are: 361.37/291.60 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.60 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.60 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (31) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.60 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.60 ---------------------------------------- 361.37/291.60 361.37/291.60 (32) 361.37/291.60 Obligation: 361.37/291.60 Complexity RNTS consisting of the following rules: 361.37/291.60 361.37/291.60 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.60 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.60 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.60 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 #less(z, z') -{ 1 }-> #cklt(s'') :|: s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> #cklt(s1) :|: s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(s2), z', @y, @ys) :|: s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (33) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed SIZE bound using CoFloCo for: #cklt 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(1) with polynomial bound: 2 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (34) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 #less(z, z') -{ 1 }-> #cklt(s'') :|: s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> #cklt(s1) :|: s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(s2), z', @y, @ys) :|: s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {#cklt}, {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: ?, size: O(1) [2] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (35) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed RUNTIME bound using CoFloCo for: #cklt 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(1) with polynomial bound: 0 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (36) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 #less(z, z') -{ 1 }-> #cklt(s'') :|: s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> #cklt(s1) :|: s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 2 }-> findMin#3(#cklt(s2), z', @y, @ys) :|: s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (37) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.61 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (38) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (39) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed SIZE bound using CoFloCo for: #less 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(1) with polynomial bound: 2 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (40) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {#less}, {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: ?, size: O(1) [2] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (41) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed RUNTIME bound using CoFloCo for: #less 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(1) with polynomial bound: 1 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (42) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (43) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.61 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (44) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (45) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed SIZE bound using CoFloCo for: findMin#2 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^1) with polynomial bound: 1 + z + z' 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (46) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin#2}, {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: ?, size: O(n^1) [1 + z + z'] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (47) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed RUNTIME bound using CoFloCo for: findMin#2 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(1) with polynomial bound: 3 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (48) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (49) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.61 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (50) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (51) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed SIZE bound using CoFloCo for: findMin#1 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^1) with polynomial bound: z 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (52) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin#1}, {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: ?, size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (53) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed RUNTIME bound using CoFloCo for: findMin#1 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^1) with polynomial bound: 1 + 5*z 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (54) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 1 }-> findMin#1(z) :|: z >= 0 361.37/291.61 findMin#1(z) -{ 2 }-> findMin#2(findMin#1(@xs), @x) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 2 }-> minSort#1(findMin#1(z)) :|: z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: O(n^1) [1 + 5*z], size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (55) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.61 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (56) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 2 + 5*z }-> s7 :|: s7 >= 0, s7 <= z, z >= 0 361.37/291.61 findMin#1(z) -{ 6 + 5*@xs }-> s9 :|: s8 >= 0, s8 <= @xs, s9 >= 0, s9 <= s8 + @x + 1, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 3 + 5*z }-> minSort#1(s10) :|: s10 >= 0, s10 <= z, z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: O(n^1) [1 + 5*z], size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (57) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed SIZE bound using CoFloCo for: minSort#1 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^1) with polynomial bound: z 361.37/291.61 361.37/291.61 Computed SIZE bound using CoFloCo for: minSort 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^1) with polynomial bound: z 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (58) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 2 + 5*z }-> s7 :|: s7 >= 0, s7 <= z, z >= 0 361.37/291.61 findMin#1(z) -{ 6 + 5*@xs }-> s9 :|: s8 >= 0, s8 <= @xs, s9 >= 0, s9 <= s8 + @x + 1, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 3 + 5*z }-> minSort#1(s10) :|: s10 >= 0, s10 <= z, z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {minSort#1,minSort}, {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: O(n^1) [1 + 5*z], size: O(n^1) [z] 361.37/291.61 minSort#1: runtime: ?, size: O(n^1) [z] 361.37/291.61 minSort: runtime: ?, size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (59) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed RUNTIME bound using CoFloCo for: minSort#1 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^2) with polynomial bound: 4 + 8*z + 5*z^2 361.37/291.61 361.37/291.61 Computed RUNTIME bound using KoAT for: minSort 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^2) with polynomial bound: 7 + 13*z + 5*z^2 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (60) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 2 + 5*z }-> s7 :|: s7 >= 0, s7 <= z, z >= 0 361.37/291.61 findMin#1(z) -{ 6 + 5*@xs }-> s9 :|: s8 >= 0, s8 <= @xs, s9 >= 0, s9 <= s8 + @x + 1, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 3 + 5*z }-> minSort#1(s10) :|: s10 >= 0, s10 <= z, z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 1 }-> 1 + @x + minSort(@xs) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: O(n^1) [1 + 5*z], size: O(n^1) [z] 361.37/291.61 minSort#1: runtime: O(n^2) [4 + 8*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 minSort: runtime: O(n^2) [7 + 13*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (61) ResultPropagationProof (UPPER BOUND(ID)) 361.37/291.61 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (62) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 2 + 5*z }-> s7 :|: s7 >= 0, s7 <= z, z >= 0 361.37/291.61 findMin#1(z) -{ 6 + 5*@xs }-> s9 :|: s8 >= 0, s8 <= @xs, s9 >= 0, s9 <= s8 + @x + 1, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 7 + 8*s10 + 5*s10^2 + 5*z }-> s11 :|: s11 >= 0, s11 <= s10, s10 >= 0, s10 <= z, z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 8 + 13*@xs + 5*@xs^2 }-> 1 + @x + s12 :|: s12 >= 0, s12 <= @xs, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: O(n^1) [1 + 5*z], size: O(n^1) [z] 361.37/291.61 minSort#1: runtime: O(n^2) [4 + 8*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 minSort: runtime: O(n^2) [7 + 13*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (63) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed SIZE bound using CoFloCo for: findMin 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^1) with polynomial bound: z 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (64) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 2 + 5*z }-> s7 :|: s7 >= 0, s7 <= z, z >= 0 361.37/291.61 findMin#1(z) -{ 6 + 5*@xs }-> s9 :|: s8 >= 0, s8 <= @xs, s9 >= 0, s9 <= s8 + @x + 1, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 7 + 8*s10 + 5*s10^2 + 5*z }-> s11 :|: s11 >= 0, s11 <= s10, s10 >= 0, s10 <= z, z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 8 + 13*@xs + 5*@xs^2 }-> 1 + @x + s12 :|: s12 >= 0, s12 <= @xs, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: {findMin} 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: O(n^1) [1 + 5*z], size: O(n^1) [z] 361.37/291.61 minSort#1: runtime: O(n^2) [4 + 8*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 minSort: runtime: O(n^2) [7 + 13*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 findMin: runtime: ?, size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (65) IntTrsBoundProof (UPPER BOUND(ID)) 361.37/291.61 361.37/291.61 Computed RUNTIME bound using CoFloCo for: findMin 361.37/291.61 after applying outer abstraction to obtain an ITS, 361.37/291.61 resulting in: O(n^1) with polynomial bound: 2 + 5*z 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (66) 361.37/291.61 Obligation: 361.37/291.61 Complexity RNTS consisting of the following rules: 361.37/291.61 361.37/291.61 #cklt(z) -{ 0 }-> 2 :|: z = 3 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 1 361.37/291.61 #cklt(z) -{ 0 }-> 1 :|: z = 2 361.37/291.61 #cklt(z) -{ 0 }-> 0 :|: z >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s :|: s >= 0, s <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> s' :|: s' >= 0, s' <= 3, z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 3 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' - 1 >= 0 361.37/291.61 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 361.37/291.61 #compare(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s3 :|: s3 >= 0, s3 <= 2, s'' >= 0, s'' <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> s4 :|: s4 >= 0, s4 <= 2, s1 >= 0, s1 <= 3, z' - 1 >= 0, z - 1 >= 0 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z - 1 >= 0, z' = 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 2 :|: z' - 1 >= 0, z - 1 >= 0, 3 = 3 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0, 1 = 1 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z' - 1 >= 0, z = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' - 1 >= 0, 2 = 2 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0, v0 >= 0, 1 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z' - 1 >= 0, z - 1 >= 0, v0 >= 0, 3 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 2 = v0 361.37/291.61 #less(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, 0 = v0 361.37/291.61 findMin(z) -{ 2 + 5*z }-> s7 :|: s7 >= 0, s7 <= z, z >= 0 361.37/291.61 findMin#1(z) -{ 6 + 5*@xs }-> s9 :|: s8 >= 0, s8 <= @xs, s9 >= 0, s9 <= s8 + @x + 1, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 findMin#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 findMin#2(z, z') -{ 3 }-> s6 :|: s5 >= 0, s5 <= 2, s6 >= 0, s6 <= z' + @y + @ys + 2, s2 >= 0, s2 <= 3, z = 1 + @y + @ys, z' >= 0, @y >= 0, @ys >= 0 361.37/291.61 findMin#2(z, z') -{ 1 }-> 1 + z' + 0 :|: z' >= 0, z = 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z' + (1 + z'' + z1) :|: z = 2, z' >= 0, z'' >= 0, z1 >= 0 361.37/291.61 findMin#3(z, z', z'', z1) -{ 1 }-> 1 + z'' + (1 + z' + z1) :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 361.37/291.61 minSort(z) -{ 7 + 8*s10 + 5*s10^2 + 5*z }-> s11 :|: s11 >= 0, s11 <= s10, s10 >= 0, s10 <= z, z >= 0 361.37/291.61 minSort#1(z) -{ 1 }-> 0 :|: z = 0 361.37/291.61 minSort#1(z) -{ 8 + 13*@xs + 5*@xs^2 }-> 1 + @x + s12 :|: s12 >= 0, s12 <= @xs, @x >= 0, z = 1 + @x + @xs, @xs >= 0 361.37/291.61 361.37/291.61 Function symbols to be analyzed: 361.37/291.61 Previous analysis results are: 361.37/291.61 #compare: runtime: O(1) [0], size: O(1) [3] 361.37/291.61 findMin#3: runtime: O(1) [1], size: O(n^1) [2 + z' + z'' + z1] 361.37/291.61 #cklt: runtime: O(1) [0], size: O(1) [2] 361.37/291.61 #less: runtime: O(1) [1], size: O(1) [2] 361.37/291.61 findMin#2: runtime: O(1) [3], size: O(n^1) [1 + z + z'] 361.37/291.61 findMin#1: runtime: O(n^1) [1 + 5*z], size: O(n^1) [z] 361.37/291.61 minSort#1: runtime: O(n^2) [4 + 8*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 minSort: runtime: O(n^2) [7 + 13*z + 5*z^2], size: O(n^1) [z] 361.37/291.61 findMin: runtime: O(n^1) [2 + 5*z], size: O(n^1) [z] 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (67) FinalProof (FINISHED) 361.37/291.61 Computed overall runtime complexity 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (68) 361.37/291.61 BOUNDS(1, n^2) 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (69) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 361.37/291.61 Transformed a relative TRS into a decreasing-loop problem. 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (70) 361.37/291.61 Obligation: 361.37/291.61 Analyzing the following TRS for decreasing loops: 361.37/291.61 361.37/291.61 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 361.37/291.61 361.37/291.61 361.37/291.61 The TRS R consists of the following rules: 361.37/291.61 361.37/291.61 #less(@x, @y) -> #cklt(#compare(@x, @y)) 361.37/291.61 findMin(@l) -> findMin#1(@l) 361.37/291.61 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) 361.37/291.61 findMin#1(nil) -> nil 361.37/291.61 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) 361.37/291.61 findMin#2(nil, @x) -> ::(@x, nil) 361.37/291.61 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) 361.37/291.61 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) 361.37/291.61 minSort(@l) -> minSort#1(findMin(@l)) 361.37/291.61 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) 361.37/291.61 minSort#1(nil) -> nil 361.37/291.61 361.37/291.61 The (relative) TRS S consists of the following rules: 361.37/291.61 361.37/291.61 #cklt(#EQ) -> #false 361.37/291.61 #cklt(#GT) -> #false 361.37/291.61 #cklt(#LT) -> #true 361.37/291.61 #compare(#0, #0) -> #EQ 361.37/291.61 #compare(#0, #neg(@y)) -> #GT 361.37/291.61 #compare(#0, #pos(@y)) -> #LT 361.37/291.61 #compare(#0, #s(@y)) -> #LT 361.37/291.61 #compare(#neg(@x), #0) -> #LT 361.37/291.61 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) 361.37/291.61 #compare(#neg(@x), #pos(@y)) -> #LT 361.37/291.61 #compare(#pos(@x), #0) -> #GT 361.37/291.61 #compare(#pos(@x), #neg(@y)) -> #GT 361.37/291.61 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) 361.37/291.61 #compare(#s(@x), #0) -> #GT 361.37/291.61 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) 361.37/291.61 361.37/291.61 Rewrite Strategy: INNERMOST 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (71) DecreasingLoopProof (LOWER BOUND(ID)) 361.37/291.61 The following loop(s) give(s) rise to the lower bound Omega(n^1): 361.37/291.61 361.37/291.61 The rewrite sequence 361.37/291.61 361.37/291.61 findMin#1(::(@x, @xs)) ->^+ findMin#2(findMin#1(@xs), @x) 361.37/291.61 361.37/291.61 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 361.37/291.61 361.37/291.61 The pumping substitution is [@xs / ::(@x, @xs)]. 361.37/291.61 361.37/291.61 The result substitution is [ ]. 361.37/291.61 361.37/291.61 361.37/291.61 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (72) 361.37/291.61 Complex Obligation (BEST) 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (73) 361.37/291.61 Obligation: 361.37/291.61 Proved the lower bound n^1 for the following obligation: 361.37/291.61 361.37/291.61 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 361.37/291.61 361.37/291.61 361.37/291.61 The TRS R consists of the following rules: 361.37/291.61 361.37/291.61 #less(@x, @y) -> #cklt(#compare(@x, @y)) 361.37/291.61 findMin(@l) -> findMin#1(@l) 361.37/291.61 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) 361.37/291.61 findMin#1(nil) -> nil 361.37/291.61 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) 361.37/291.61 findMin#2(nil, @x) -> ::(@x, nil) 361.37/291.61 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) 361.37/291.61 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) 361.37/291.61 minSort(@l) -> minSort#1(findMin(@l)) 361.37/291.61 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) 361.37/291.61 minSort#1(nil) -> nil 361.37/291.61 361.37/291.61 The (relative) TRS S consists of the following rules: 361.37/291.61 361.37/291.61 #cklt(#EQ) -> #false 361.37/291.61 #cklt(#GT) -> #false 361.37/291.61 #cklt(#LT) -> #true 361.37/291.61 #compare(#0, #0) -> #EQ 361.37/291.61 #compare(#0, #neg(@y)) -> #GT 361.37/291.61 #compare(#0, #pos(@y)) -> #LT 361.37/291.61 #compare(#0, #s(@y)) -> #LT 361.37/291.61 #compare(#neg(@x), #0) -> #LT 361.37/291.61 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) 361.37/291.61 #compare(#neg(@x), #pos(@y)) -> #LT 361.37/291.61 #compare(#pos(@x), #0) -> #GT 361.37/291.61 #compare(#pos(@x), #neg(@y)) -> #GT 361.37/291.61 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) 361.37/291.61 #compare(#s(@x), #0) -> #GT 361.37/291.61 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) 361.37/291.61 361.37/291.61 Rewrite Strategy: INNERMOST 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (74) LowerBoundPropagationProof (FINISHED) 361.37/291.61 Propagated lower bound. 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (75) 361.37/291.61 BOUNDS(n^1, INF) 361.37/291.61 361.37/291.61 ---------------------------------------- 361.37/291.61 361.37/291.61 (76) 361.37/291.61 Obligation: 361.37/291.61 Analyzing the following TRS for decreasing loops: 361.37/291.61 361.37/291.61 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 361.37/291.61 361.37/291.61 361.37/291.61 The TRS R consists of the following rules: 361.37/291.61 361.37/291.61 #less(@x, @y) -> #cklt(#compare(@x, @y)) 361.37/291.61 findMin(@l) -> findMin#1(@l) 361.37/291.61 findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x) 361.37/291.61 findMin#1(nil) -> nil 361.37/291.61 findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys) 361.37/291.61 findMin#2(nil, @x) -> ::(@x, nil) 361.37/291.61 findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys)) 361.37/291.61 findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) 361.37/291.61 minSort(@l) -> minSort#1(findMin(@l)) 361.37/291.61 minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs)) 361.37/291.61 minSort#1(nil) -> nil 361.37/291.61 361.37/291.61 The (relative) TRS S consists of the following rules: 361.37/291.61 361.37/291.61 #cklt(#EQ) -> #false 361.37/291.61 #cklt(#GT) -> #false 361.37/291.61 #cklt(#LT) -> #true 361.37/291.61 #compare(#0, #0) -> #EQ 361.37/291.61 #compare(#0, #neg(@y)) -> #GT 361.37/291.61 #compare(#0, #pos(@y)) -> #LT 361.37/291.61 #compare(#0, #s(@y)) -> #LT 361.37/291.61 #compare(#neg(@x), #0) -> #LT 361.37/291.61 #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) 361.37/291.61 #compare(#neg(@x), #pos(@y)) -> #LT 361.37/291.61 #compare(#pos(@x), #0) -> #GT 361.37/291.61 #compare(#pos(@x), #neg(@y)) -> #GT 361.37/291.61 #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) 361.37/291.61 #compare(#s(@x), #0) -> #GT 361.37/291.61 #compare(#s(@x), #s(@y)) -> #compare(@x, @y) 361.37/291.61 361.37/291.61 Rewrite Strategy: INNERMOST 361.54/291.67 EOF