/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). (0) CpxRelTRS (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 237 ms] (2) CpxRelTRS (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxWeightedTrs (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 4 ms] (6) CpxTypedWeightedTrs (7) CompletionProof [UPPER BOUND(ID), 0 ms] (8) CpxTypedWeightedCompleteTrs (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (10) CpxRNTS (11) CompleteCoflocoProof [FINISHED, 34.3 s] (12) BOUNDS(1, n^2) (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (14) TRS for Loop Detection (15) DecreasingLoopProof [LOWER BOUND(ID), 56 ms] (16) BEST (17) proven lower bound (18) LowerBoundPropagationProof [FINISHED, 0 ms] (19) BOUNDS(n^1, INF) (20) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) #less(@x, @y) -> #cklt(#compare(@x, @y)) and(@x, @y) -> #and(@x, @y) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) isortlist(@l) -> isortlist#1(@l) isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) isortlist#1(nil) -> nil leq(@l1, @l2) -> leq#1(@l1, @l2) leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) leq#1(nil, @l2) -> #true leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) leq#2(nil, @x, @xs) -> #false or(@x, @y) -> #or(@x, @y) The (relative) TRS S consists of the following rules: #and(#false, #false) -> #false #and(#false, #true) -> #false #and(#true, #false) -> #false #and(#true, #true) -> #true #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) #eq(#0, #0) -> #true #eq(#0, #neg(@y)) -> #false #eq(#0, #pos(@y)) -> #false #eq(#0, #s(@y)) -> #false #eq(#neg(@x), #0) -> #false #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) #eq(#neg(@x), #pos(@y)) -> #false #eq(#pos(@x), #0) -> #false #eq(#pos(@x), #neg(@y)) -> #false #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) #eq(#s(@x), #0) -> #false #eq(#s(@x), #s(@y)) -> #eq(@x, @y) #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) #eq(::(@x_1, @x_2), nil) -> #false #eq(nil, ::(@y_1, @y_2)) -> #false #eq(nil, nil) -> #true #or(#false, #false) -> #false #or(#false, #true) -> #true #or(#true, #false) -> #true #or(#true, #true) -> #true Rewrite Strategy: INNERMOST ---------------------------------------- (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved termination of relative rules ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) #less(@x, @y) -> #cklt(#compare(@x, @y)) and(@x, @y) -> #and(@x, @y) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) isortlist(@l) -> isortlist#1(@l) isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) isortlist#1(nil) -> nil leq(@l1, @l2) -> leq#1(@l1, @l2) leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) leq#1(nil, @l2) -> #true leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) leq#2(nil, @x, @xs) -> #false or(@x, @y) -> #or(@x, @y) The (relative) TRS S consists of the following rules: #and(#false, #false) -> #false #and(#false, #true) -> #false #and(#true, #false) -> #false #and(#true, #true) -> #true #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) #eq(#0, #0) -> #true #eq(#0, #neg(@y)) -> #false #eq(#0, #pos(@y)) -> #false #eq(#0, #s(@y)) -> #false #eq(#neg(@x), #0) -> #false #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) #eq(#neg(@x), #pos(@y)) -> #false #eq(#pos(@x), #0) -> #false #eq(#pos(@x), #neg(@y)) -> #false #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) #eq(#s(@x), #0) -> #false #eq(#s(@x), #s(@y)) -> #eq(@x, @y) #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) #eq(::(@x_1, @x_2), nil) -> #false #eq(nil, ::(@y_1, @y_2)) -> #false #eq(nil, nil) -> #true #or(#false, #false) -> #false #or(#false, #true) -> #true #or(#true, #false) -> #true #or(#true, #true) -> #true Rewrite Strategy: INNERMOST ---------------------------------------- (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) [1] #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] and(@x, @y) -> #and(@x, @y) [1] insert(@x, @l) -> insert#1(@l, @x) [1] insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) [1] insert#1(nil, @x) -> ::(@x, nil) [1] insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) [1] insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] isortlist(@l) -> isortlist#1(@l) [1] isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) [1] isortlist#1(nil) -> nil [1] leq(@l1, @l2) -> leq#1(@l1, @l2) [1] leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) [1] leq#1(nil, @l2) -> #true [1] leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) [1] leq#2(nil, @x, @xs) -> #false [1] or(@x, @y) -> #or(@x, @y) [1] #and(#false, #false) -> #false [0] #and(#false, #true) -> #false [0] #and(#true, #false) -> #false [0] #and(#true, #true) -> #true [0] #cklt(#EQ) -> #false [0] #cklt(#GT) -> #false [0] #cklt(#LT) -> #true [0] #compare(#0, #0) -> #EQ [0] #compare(#0, #neg(@y)) -> #GT [0] #compare(#0, #pos(@y)) -> #LT [0] #compare(#0, #s(@y)) -> #LT [0] #compare(#neg(@x), #0) -> #LT [0] #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] #compare(#neg(@x), #pos(@y)) -> #LT [0] #compare(#pos(@x), #0) -> #GT [0] #compare(#pos(@x), #neg(@y)) -> #GT [0] #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] #compare(#s(@x), #0) -> #GT [0] #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] #eq(#0, #0) -> #true [0] #eq(#0, #neg(@y)) -> #false [0] #eq(#0, #pos(@y)) -> #false [0] #eq(#0, #s(@y)) -> #false [0] #eq(#neg(@x), #0) -> #false [0] #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) [0] #eq(#neg(@x), #pos(@y)) -> #false [0] #eq(#pos(@x), #0) -> #false [0] #eq(#pos(@x), #neg(@y)) -> #false [0] #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) [0] #eq(#s(@x), #0) -> #false [0] #eq(#s(@x), #s(@y)) -> #eq(@x, @y) [0] #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) [0] #eq(::(@x_1, @x_2), nil) -> #false [0] #eq(nil, ::(@y_1, @y_2)) -> #false [0] #eq(nil, nil) -> #true [0] #or(#false, #false) -> #false [0] #or(#false, #true) -> #true [0] #or(#true, #false) -> #true [0] #or(#true, #true) -> #true [0] Rewrite Strategy: INNERMOST ---------------------------------------- (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (6) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) [1] #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] and(@x, @y) -> #and(@x, @y) [1] insert(@x, @l) -> insert#1(@l, @x) [1] insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) [1] insert#1(nil, @x) -> ::(@x, nil) [1] insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) [1] insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] isortlist(@l) -> isortlist#1(@l) [1] isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) [1] isortlist#1(nil) -> nil [1] leq(@l1, @l2) -> leq#1(@l1, @l2) [1] leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) [1] leq#1(nil, @l2) -> #true [1] leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) [1] leq#2(nil, @x, @xs) -> #false [1] or(@x, @y) -> #or(@x, @y) [1] #and(#false, #false) -> #false [0] #and(#false, #true) -> #false [0] #and(#true, #false) -> #false [0] #and(#true, #true) -> #true [0] #cklt(#EQ) -> #false [0] #cklt(#GT) -> #false [0] #cklt(#LT) -> #true [0] #compare(#0, #0) -> #EQ [0] #compare(#0, #neg(@y)) -> #GT [0] #compare(#0, #pos(@y)) -> #LT [0] #compare(#0, #s(@y)) -> #LT [0] #compare(#neg(@x), #0) -> #LT [0] #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] #compare(#neg(@x), #pos(@y)) -> #LT [0] #compare(#pos(@x), #0) -> #GT [0] #compare(#pos(@x), #neg(@y)) -> #GT [0] #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] #compare(#s(@x), #0) -> #GT [0] #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] #eq(#0, #0) -> #true [0] #eq(#0, #neg(@y)) -> #false [0] #eq(#0, #pos(@y)) -> #false [0] #eq(#0, #s(@y)) -> #false [0] #eq(#neg(@x), #0) -> #false [0] #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) [0] #eq(#neg(@x), #pos(@y)) -> #false [0] #eq(#pos(@x), #0) -> #false [0] #eq(#pos(@x), #neg(@y)) -> #false [0] #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) [0] #eq(#s(@x), #0) -> #false [0] #eq(#s(@x), #s(@y)) -> #eq(@x, @y) [0] #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) [0] #eq(::(@x_1, @x_2), nil) -> #false [0] #eq(nil, ::(@y_1, @y_2)) -> #false [0] #eq(nil, nil) -> #true [0] #or(#false, #false) -> #false [0] #or(#false, #true) -> #true [0] #or(#true, #false) -> #true [0] #or(#true, #true) -> #true [0] The TRS has the following type information: #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true #less :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true #cklt :: #EQ:#GT:#LT -> #false:#true #compare :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #EQ:#GT:#LT and :: #false:#true -> #false:#true -> #false:#true #and :: #false:#true -> #false:#true -> #false:#true insert :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s insert#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s insert#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s leq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true nil :: :::nil:#0:#neg:#pos:#s #false :: #false:#true #true :: #false:#true isortlist :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s isortlist#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s leq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true leq#2 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true or :: #false:#true -> #false:#true -> #false:#true #or :: #false:#true -> #false:#true -> #false:#true #EQ :: #EQ:#GT:#LT #GT :: #EQ:#GT:#LT #LT :: #EQ:#GT:#LT #0 :: :::nil:#0:#neg:#pos:#s #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s Rewrite Strategy: INNERMOST ---------------------------------------- (7) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: #and(v0, v1) -> null_#and [0] #cklt(v0) -> null_#cklt [0] #compare(v0, v1) -> null_#compare [0] #eq(v0, v1) -> null_#eq [0] #or(v0, v1) -> null_#or [0] insert#1(v0, v1) -> null_insert#1 [0] insert#2(v0, v1, v2, v3) -> null_insert#2 [0] isortlist#1(v0) -> null_isortlist#1 [0] leq#1(v0, v1) -> null_leq#1 [0] leq#2(v0, v1, v2) -> null_leq#2 [0] And the following fresh constants: null_#and, null_#cklt, null_#compare, null_#eq, null_#or, null_insert#1, null_insert#2, null_isortlist#1, null_leq#1, null_leq#2 ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) [1] #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] and(@x, @y) -> #and(@x, @y) [1] insert(@x, @l) -> insert#1(@l, @x) [1] insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) [1] insert#1(nil, @x) -> ::(@x, nil) [1] insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) [1] insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] isortlist(@l) -> isortlist#1(@l) [1] isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) [1] isortlist#1(nil) -> nil [1] leq(@l1, @l2) -> leq#1(@l1, @l2) [1] leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) [1] leq#1(nil, @l2) -> #true [1] leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) [1] leq#2(nil, @x, @xs) -> #false [1] or(@x, @y) -> #or(@x, @y) [1] #and(#false, #false) -> #false [0] #and(#false, #true) -> #false [0] #and(#true, #false) -> #false [0] #and(#true, #true) -> #true [0] #cklt(#EQ) -> #false [0] #cklt(#GT) -> #false [0] #cklt(#LT) -> #true [0] #compare(#0, #0) -> #EQ [0] #compare(#0, #neg(@y)) -> #GT [0] #compare(#0, #pos(@y)) -> #LT [0] #compare(#0, #s(@y)) -> #LT [0] #compare(#neg(@x), #0) -> #LT [0] #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] #compare(#neg(@x), #pos(@y)) -> #LT [0] #compare(#pos(@x), #0) -> #GT [0] #compare(#pos(@x), #neg(@y)) -> #GT [0] #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] #compare(#s(@x), #0) -> #GT [0] #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] #eq(#0, #0) -> #true [0] #eq(#0, #neg(@y)) -> #false [0] #eq(#0, #pos(@y)) -> #false [0] #eq(#0, #s(@y)) -> #false [0] #eq(#neg(@x), #0) -> #false [0] #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) [0] #eq(#neg(@x), #pos(@y)) -> #false [0] #eq(#pos(@x), #0) -> #false [0] #eq(#pos(@x), #neg(@y)) -> #false [0] #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) [0] #eq(#s(@x), #0) -> #false [0] #eq(#s(@x), #s(@y)) -> #eq(@x, @y) [0] #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) [0] #eq(::(@x_1, @x_2), nil) -> #false [0] #eq(nil, ::(@y_1, @y_2)) -> #false [0] #eq(nil, nil) -> #true [0] #or(#false, #false) -> #false [0] #or(#false, #true) -> #true [0] #or(#true, #false) -> #true [0] #or(#true, #true) -> #true [0] #and(v0, v1) -> null_#and [0] #cklt(v0) -> null_#cklt [0] #compare(v0, v1) -> null_#compare [0] #eq(v0, v1) -> null_#eq [0] #or(v0, v1) -> null_#or [0] insert#1(v0, v1) -> null_insert#1 [0] insert#2(v0, v1, v2, v3) -> null_insert#2 [0] isortlist#1(v0) -> null_isortlist#1 [0] leq#1(v0, v1) -> null_leq#1 [0] leq#2(v0, v1, v2) -> null_leq#2 [0] The TRS has the following type information: #equal :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #eq :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #less :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #cklt :: #EQ:#GT:#LT:null_#compare -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #compare :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> #EQ:#GT:#LT:null_#compare and :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #and :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 insert :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 insert#1 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 :: :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 insert#2 :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 leq :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 nil :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 #false :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #true :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 isortlist :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 isortlist#1 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 leq#1 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 leq#2 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 or :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #or :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 -> #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 #EQ :: #EQ:#GT:#LT:null_#compare #GT :: #EQ:#GT:#LT:null_#compare #LT :: #EQ:#GT:#LT:null_#compare #0 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 #neg :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 #pos :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 #s :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 -> :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 null_#and :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 null_#cklt :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 null_#compare :: #EQ:#GT:#LT:null_#compare null_#eq :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 null_#or :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 null_insert#1 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 null_insert#2 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 null_isortlist#1 :: :::nil:#0:#neg:#pos:#s:null_insert#1:null_insert#2:null_isortlist#1 null_leq#1 :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 null_leq#2 :: #false:#true:null_#and:null_#cklt:null_#eq:null_#or:null_leq#1:null_leq#2 Rewrite Strategy: INNERMOST ---------------------------------------- (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: nil => 1 #false => 1 #true => 2 #EQ => 1 #GT => 2 #LT => 3 #0 => 0 null_#and => 0 null_#cklt => 0 null_#compare => 0 null_#eq => 0 null_#or => 0 null_insert#1 => 0 null_insert#2 => 0 null_isortlist#1 => 0 null_leq#1 => 0 null_leq#2 => 0 ---------------------------------------- (10) Obligation: Complexity RNTS consisting of the following rules: #and(z, z') -{ 0 }-> 2 :|: z = 2, z' = 2 #and(z, z') -{ 0 }-> 1 :|: z = 1, z' = 1 #and(z, z') -{ 0 }-> 1 :|: z' = 2, z = 1 #and(z, z') -{ 0 }-> 1 :|: z = 2, z' = 1 #and(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 #cklt(z) -{ 0 }-> 2 :|: z = 3 #cklt(z) -{ 0 }-> 1 :|: z = 1 #cklt(z) -{ 0 }-> 1 :|: z = 2 #cklt(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 0 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 0 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 #compare(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 #compare(z, z') -{ 0 }-> #compare(@x, @y) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> #compare(@y, @x) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #eq(z, z') -{ 0 }-> 2 :|: z = 0, z' = 0 #eq(z, z') -{ 0 }-> 2 :|: z = 1, z' = 1 #eq(z, z') -{ 0 }-> 1 :|: z = 0, z' = 1 + @y, @y >= 0 #eq(z, z') -{ 0 }-> 1 :|: @x >= 0, z = 1 + @x, z' = 0 #eq(z, z') -{ 0 }-> 1 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #eq(z, z') -{ 0 }-> 1 :|: @x_1 >= 0, z = 1 + @x_1 + @x_2, @x_2 >= 0, z' = 1 #eq(z, z') -{ 0 }-> 1 :|: z = 1, @y_1 >= 0, @y_2 >= 0, z' = 1 + @y_1 + @y_2 #eq(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 #eq(z, z') -{ 0 }-> #eq(@x, @y) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #eq(z, z') -{ 0 }-> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) :|: @x_1 >= 0, z = 1 + @x_1 + @x_2, @y_1 >= 0, @x_2 >= 0, @y_2 >= 0, z' = 1 + @y_1 + @y_2 #equal(z, z') -{ 1 }-> #eq(@x, @y) :|: z = @x, @x >= 0, z' = @y, @y >= 0 #less(z, z') -{ 1 }-> #cklt(#compare(@x, @y)) :|: z = @x, @x >= 0, z' = @y, @y >= 0 #or(z, z') -{ 0 }-> 2 :|: z' = 2, z = 1 #or(z, z') -{ 0 }-> 2 :|: z = 2, z' = 1 #or(z, z') -{ 0 }-> 2 :|: z = 2, z' = 2 #or(z, z') -{ 0 }-> 1 :|: z = 1, z' = 1 #or(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 and(z, z') -{ 1 }-> #and(@x, @y) :|: z = @x, @x >= 0, z' = @y, @y >= 0 insert(z, z') -{ 1 }-> insert#1(@l, @x) :|: z = @x, @l >= 0, @x >= 0, z' = @l insert#1(z, z') -{ 1 }-> insert#2(leq(@x, @y), @x, @y, @ys) :|: z = 1 + @y + @ys, @x >= 0, @y >= 0, z' = @x, @ys >= 0 insert#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 insert#1(z, z') -{ 1 }-> 1 + @x + 1 :|: @x >= 0, z = 1, z' = @x insert#2(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 insert#2(z, z', z'', z1) -{ 1 }-> 1 + @x + (1 + @y + @ys) :|: z = 2, @x >= 0, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y insert#2(z, z', z'', z1) -{ 1 }-> 1 + @y + insert(@x, @ys) :|: @x >= 0, z = 1, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y isortlist(z) -{ 1 }-> isortlist#1(@l) :|: z = @l, @l >= 0 isortlist#1(z) -{ 1 }-> insert(@x, isortlist(@xs)) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 isortlist#1(z) -{ 1 }-> 1 :|: z = 1 isortlist#1(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 leq(z, z') -{ 1 }-> leq#1(@l1, @l2) :|: @l1 >= 0, z' = @l2, @l2 >= 0, z = @l1 leq#1(z, z') -{ 1 }-> leq#2(@l2, @x, @xs) :|: z' = @l2, @x >= 0, z = 1 + @x + @xs, @l2 >= 0, @xs >= 0 leq#1(z, z') -{ 1 }-> 2 :|: z' = @l2, z = 1, @l2 >= 0 leq#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 leq#2(z, z', z'') -{ 1 }-> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) :|: z = 1 + @y + @ys, @x >= 0, @xs >= 0, @y >= 0, z' = @x, z'' = @xs, @ys >= 0 leq#2(z, z', z'') -{ 1 }-> 1 :|: @x >= 0, z = 1, @xs >= 0, z' = @x, z'' = @xs leq#2(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 or(z, z') -{ 1 }-> #or(@x, @y) :|: z = @x, @x >= 0, z' = @y, @y >= 0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (11) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V, V15, V17),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[and(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[insert(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun6(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun7(V1, V, V15, V17, Out)],[V1 >= 0,V >= 0,V15 >= 0,V17 >= 0]). eq(start(V1, V, V15, V17),0,[isortlist(V1, Out)],[V1 >= 0]). eq(start(V1, V, V15, V17),0,[fun8(V1, Out)],[V1 >= 0]). eq(start(V1, V, V15, V17),0,[leq(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun9(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun10(V1, V, V15, Out)],[V1 >= 0,V >= 0,V15 >= 0]). eq(start(V1, V, V15, V17),0,[or(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun5(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun3(V1, Out)],[V1 >= 0]). eq(start(V1, V, V15, V17),0,[fun4(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun1(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V15, V17),0,[fun11(V1, V, Out)],[V1 >= 0,V >= 0]). eq(fun(V1, V, Out),1,[fun1(V2, V3, Ret)],[Out = Ret,V1 = V2,V2 >= 0,V = V3,V3 >= 0]). eq(fun2(V1, V, Out),1,[fun4(V4, V5, Ret0),fun3(Ret0, Ret1)],[Out = Ret1,V1 = V4,V4 >= 0,V = V5,V5 >= 0]). eq(and(V1, V, Out),1,[fun5(V6, V7, Ret2)],[Out = Ret2,V1 = V6,V6 >= 0,V = V7,V7 >= 0]). eq(insert(V1, V, Out),1,[fun6(V9, V8, Ret3)],[Out = Ret3,V1 = V8,V9 >= 0,V8 >= 0,V = V9]). eq(fun6(V1, V, Out),1,[leq(V10, V11, Ret01),fun7(Ret01, V10, V11, V12, Ret4)],[Out = Ret4,V1 = 1 + V11 + V12,V10 >= 0,V11 >= 0,V = V10,V12 >= 0]). eq(fun6(V1, V, Out),1,[],[Out = 2 + V13,V13 >= 0,V1 = 1,V = V13]). eq(fun7(V1, V, V15, V17, Out),1,[insert(V16, V18, Ret11)],[Out = 1 + Ret11 + V14,V16 >= 0,V1 = 1,V17 = V18,V14 >= 0,V = V16,V18 >= 0,V15 = V14]). eq(fun7(V1, V, V15, V17, Out),1,[],[Out = 2 + V19 + V20 + V21,V1 = 2,V20 >= 0,V17 = V21,V19 >= 0,V = V20,V21 >= 0,V15 = V19]). eq(isortlist(V1, Out),1,[fun8(V22, Ret5)],[Out = Ret5,V1 = V22,V22 >= 0]). eq(fun8(V1, Out),1,[isortlist(V24, Ret12),insert(V23, Ret12, Ret6)],[Out = Ret6,V23 >= 0,V1 = 1 + V23 + V24,V24 >= 0]). eq(fun8(V1, Out),1,[],[Out = 1,V1 = 1]). eq(leq(V1, V, Out),1,[fun9(V26, V25, Ret7)],[Out = Ret7,V26 >= 0,V = V25,V25 >= 0,V1 = V26]). eq(fun9(V1, V, Out),1,[fun10(V27, V28, V29, Ret8)],[Out = Ret8,V = V27,V28 >= 0,V1 = 1 + V28 + V29,V27 >= 0,V29 >= 0]). eq(fun9(V1, V, Out),1,[],[Out = 2,V = V30,V1 = 1,V30 >= 0]). eq(fun10(V1, V, V15, Out),1,[fun2(V33, V32, Ret02),fun(V33, V32, Ret10),leq(V34, V31, Ret111),and(Ret10, Ret111, Ret13),or(Ret02, Ret13, Ret9)],[Out = Ret9,V1 = 1 + V31 + V32,V33 >= 0,V34 >= 0,V32 >= 0,V = V33,V15 = V34,V31 >= 0]). eq(fun10(V1, V, V15, Out),1,[],[Out = 1,V35 >= 0,V1 = 1,V36 >= 0,V = V35,V15 = V36]). eq(or(V1, V, Out),1,[fun11(V37, V38, Ret14)],[Out = Ret14,V1 = V37,V37 >= 0,V = V38,V38 >= 0]). eq(fun5(V1, V, Out),0,[],[Out = 1,V1 = 1,V = 1]). eq(fun5(V1, V, Out),0,[],[Out = 1,V = 2,V1 = 1]). eq(fun5(V1, V, Out),0,[],[Out = 1,V1 = 2,V = 1]). eq(fun5(V1, V, Out),0,[],[Out = 2,V1 = 2,V = 2]). eq(fun3(V1, Out),0,[],[Out = 1,V1 = 1]). eq(fun3(V1, Out),0,[],[Out = 1,V1 = 2]). eq(fun3(V1, Out),0,[],[Out = 2,V1 = 3]). eq(fun4(V1, V, Out),0,[],[Out = 1,V1 = 0,V = 0]). eq(fun4(V1, V, Out),0,[],[Out = 2,V1 = 0,V = 1 + V39,V39 >= 0]). eq(fun4(V1, V, Out),0,[],[Out = 3,V1 = 0,V = 1 + V40,V40 >= 0]). eq(fun4(V1, V, Out),0,[],[Out = 3,V41 >= 0,V1 = 1 + V41,V = 0]). eq(fun4(V1, V, Out),0,[fun4(V43, V42, Ret15)],[Out = Ret15,V42 >= 0,V1 = 1 + V42,V = 1 + V43,V43 >= 0]). eq(fun4(V1, V, Out),0,[],[Out = 3,V45 >= 0,V1 = 1 + V45,V = 1 + V44,V44 >= 0]). eq(fun4(V1, V, Out),0,[],[Out = 2,V46 >= 0,V1 = 1 + V46,V = 0]). eq(fun4(V1, V, Out),0,[],[Out = 2,V48 >= 0,V1 = 1 + V48,V = 1 + V47,V47 >= 0]). eq(fun4(V1, V, Out),0,[fun4(V50, V49, Ret16)],[Out = Ret16,V50 >= 0,V1 = 1 + V50,V = 1 + V49,V49 >= 0]). eq(fun1(V1, V, Out),0,[],[Out = 2,V1 = 0,V = 0]). eq(fun1(V1, V, Out),0,[],[Out = 1,V1 = 0,V = 1 + V51,V51 >= 0]). eq(fun1(V1, V, Out),0,[],[Out = 1,V52 >= 0,V1 = 1 + V52,V = 0]). eq(fun1(V1, V, Out),0,[fun1(V54, V53, Ret17)],[Out = Ret17,V54 >= 0,V1 = 1 + V54,V = 1 + V53,V53 >= 0]). eq(fun1(V1, V, Out),0,[],[Out = 1,V56 >= 0,V1 = 1 + V56,V = 1 + V55,V55 >= 0]). eq(fun1(V1, V, Out),0,[fun1(V60, V58, Ret03),fun1(V59, V57, Ret18),fun5(Ret03, Ret18, Ret19)],[Out = Ret19,V60 >= 0,V1 = 1 + V59 + V60,V58 >= 0,V59 >= 0,V57 >= 0,V = 1 + V57 + V58]). eq(fun1(V1, V, Out),0,[],[Out = 1,V62 >= 0,V1 = 1 + V61 + V62,V61 >= 0,V = 1]). eq(fun1(V1, V, Out),0,[],[Out = 1,V1 = 1,V64 >= 0,V63 >= 0,V = 1 + V63 + V64]). eq(fun1(V1, V, Out),0,[],[Out = 2,V1 = 1,V = 1]). eq(fun11(V1, V, Out),0,[],[Out = 1,V1 = 1,V = 1]). eq(fun11(V1, V, Out),0,[],[Out = 2,V = 2,V1 = 1]). eq(fun11(V1, V, Out),0,[],[Out = 2,V1 = 2,V = 1]). eq(fun11(V1, V, Out),0,[],[Out = 2,V1 = 2,V = 2]). eq(fun5(V1, V, Out),0,[],[Out = 0,V66 >= 0,V65 >= 0,V1 = V66,V = V65]). eq(fun3(V1, Out),0,[],[Out = 0,V67 >= 0,V1 = V67]). eq(fun4(V1, V, Out),0,[],[Out = 0,V69 >= 0,V68 >= 0,V1 = V69,V = V68]). eq(fun1(V1, V, Out),0,[],[Out = 0,V70 >= 0,V71 >= 0,V1 = V70,V = V71]). eq(fun11(V1, V, Out),0,[],[Out = 0,V72 >= 0,V73 >= 0,V1 = V72,V = V73]). eq(fun6(V1, V, Out),0,[],[Out = 0,V75 >= 0,V74 >= 0,V1 = V75,V = V74]). eq(fun7(V1, V, V15, V17, Out),0,[],[Out = 0,V17 = V78,V77 >= 0,V15 = V79,V76 >= 0,V1 = V77,V = V76,V79 >= 0,V78 >= 0]). eq(fun8(V1, Out),0,[],[Out = 0,V80 >= 0,V1 = V80]). eq(fun9(V1, V, Out),0,[],[Out = 0,V81 >= 0,V82 >= 0,V1 = V81,V = V82]). eq(fun10(V1, V, V15, Out),0,[],[Out = 0,V83 >= 0,V15 = V85,V84 >= 0,V1 = V83,V = V84,V85 >= 0]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). input_output_vars(and(V1,V,Out),[V1,V],[Out]). input_output_vars(insert(V1,V,Out),[V1,V],[Out]). input_output_vars(fun6(V1,V,Out),[V1,V],[Out]). input_output_vars(fun7(V1,V,V15,V17,Out),[V1,V,V15,V17],[Out]). input_output_vars(isortlist(V1,Out),[V1],[Out]). input_output_vars(fun8(V1,Out),[V1],[Out]). input_output_vars(leq(V1,V,Out),[V1,V],[Out]). input_output_vars(fun9(V1,V,Out),[V1,V],[Out]). input_output_vars(fun10(V1,V,V15,Out),[V1,V,V15],[Out]). input_output_vars(or(V1,V,Out),[V1,V],[Out]). input_output_vars(fun5(V1,V,Out),[V1,V],[Out]). input_output_vars(fun3(V1,Out),[V1],[Out]). input_output_vars(fun4(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(V1,V,Out),[V1,V],[Out]). input_output_vars(fun11(V1,V,Out),[V1,V],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [fun5/3] 1. non_recursive : [and/3] 2. recursive [non_tail,multiple] : [fun1/3] 3. non_recursive : [fun/3] 4. non_recursive : [fun3/2] 5. recursive : [fun4/3] 6. non_recursive : [fun2/3] 7. non_recursive : [fun11/3] 8. non_recursive : [or/3] 9. recursive [non_tail] : [fun10/4,fun9/3,leq/3] 10. recursive : [fun6/3,fun7/5,insert/3] 11. recursive [non_tail] : [fun8/2,isortlist/2] 12. non_recursive : [start/4] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun5/3 1. SCC is completely evaluated into other SCCs 2. SCC is partially evaluated into fun1/3 3. SCC is completely evaluated into other SCCs 4. SCC is partially evaluated into fun3/2 5. SCC is partially evaluated into fun4/3 6. SCC is partially evaluated into fun2/3 7. SCC is partially evaluated into fun11/3 8. SCC is completely evaluated into other SCCs 9. SCC is partially evaluated into leq/3 10. SCC is partially evaluated into insert/3 11. SCC is partially evaluated into isortlist/2 12. SCC is partially evaluated into start/4 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun5/3 * CE 50 is refined into CE [70] * CE 49 is refined into CE [71] * CE 48 is refined into CE [72] * CE 47 is refined into CE [73] * CE 46 is refined into CE [74] ### Cost equations --> "Loop" of fun5/3 * CEs [70] --> Loop 46 * CEs [71] --> Loop 47 * CEs [72] --> Loop 48 * CEs [73] --> Loop 49 * CEs [74] --> Loop 50 ### Ranking functions of CR fun5(V1,V,Out) #### Partial ranking functions of CR fun5(V1,V,Out) ### Specialization of cost equations fun1/3 * CE 42 is refined into CE [75] * CE 45 is refined into CE [76] * CE 40 is refined into CE [77] * CE 44 is refined into CE [78] * CE 39 is refined into CE [79] * CE 38 is refined into CE [80] * CE 43 is refined into CE [81,82,83,84,85] * CE 41 is refined into CE [86] ### Cost equations --> "Loop" of fun1/3 * CEs [86] --> Loop 51 * CEs [84] --> Loop 52 * CEs [83] --> Loop 53 * CEs [82] --> Loop 54 * CEs [81] --> Loop 55 * CEs [85] --> Loop 56 * CEs [75] --> Loop 57 * CEs [76] --> Loop 58 * CEs [77] --> Loop 59 * CEs [78] --> Loop 60 * CEs [79] --> Loop 61 * CEs [80] --> Loop 62 ### Ranking functions of CR fun1(V1,V,Out) * RF of phase [51,52,53,54,55,56]: [V,V1] #### Partial ranking functions of CR fun1(V1,V,Out) * Partial RF of phase [51,52,53,54,55,56]: - RF of loop [51:1,52:1,52:2,53:1,53:2,54:1,54:2,55:1,55:2,56:1,56:2]: V V1 ### Specialization of cost equations fun3/2 * CE 59 is refined into CE [87] * CE 58 is refined into CE [88] * CE 57 is refined into CE [89] * CE 56 is refined into CE [90] ### Cost equations --> "Loop" of fun3/2 * CEs [87] --> Loop 63 * CEs [88] --> Loop 64 * CEs [89] --> Loop 65 * CEs [90] --> Loop 66 ### Ranking functions of CR fun3(V1,Out) #### Partial ranking functions of CR fun3(V1,Out) ### Specialization of cost equations fun4/3 * CE 65 is refined into CE [91] * CE 67 is refined into CE [92] * CE 69 is refined into CE [93] * CE 63 is refined into CE [94] * CE 66 is refined into CE [95] * CE 62 is refined into CE [96] * CE 61 is refined into CE [97] * CE 60 is refined into CE [98] * CE 64 is refined into CE [99] * CE 68 is refined into CE [100] ### Cost equations --> "Loop" of fun4/3 * CEs [99] --> Loop 67 * CEs [100] --> Loop 68 * CEs [91] --> Loop 69 * CEs [92] --> Loop 70 * CEs [93] --> Loop 71 * CEs [94] --> Loop 72 * CEs [95] --> Loop 73 * CEs [96] --> Loop 74 * CEs [97] --> Loop 75 * CEs [98] --> Loop 76 ### Ranking functions of CR fun4(V1,V,Out) * RF of phase [67,68]: [V1/2+V/2-1/2] #### Partial ranking functions of CR fun4(V1,V,Out) * Partial RF of phase [67,68]: - RF of loop [67:1]: V1/2+V/2-1/2 - RF of loop [68:1]: V depends on loops [67:1] V1 depends on loops [67:1] ### Specialization of cost equations fun2/3 * CE 37 is refined into CE [101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117] ### Cost equations --> "Loop" of fun2/3 * CEs [116] --> Loop 77 * CEs [112,114] --> Loop 78 * CEs [113] --> Loop 79 * CEs [109] --> Loop 80 * CEs [107] --> Loop 81 * CEs [108,110] --> Loop 82 * CEs [105] --> Loop 83 * CEs [103] --> Loop 84 * CEs [104,106] --> Loop 85 * CEs [101] --> Loop 86 * CEs [102,111,115,117] --> Loop 87 ### Ranking functions of CR fun2(V1,V,Out) #### Partial ranking functions of CR fun2(V1,V,Out) ### Specialization of cost equations fun11/3 * CE 55 is refined into CE [118] * CE 54 is refined into CE [119] * CE 53 is refined into CE [120] * CE 52 is refined into CE [121] * CE 51 is refined into CE [122] ### Cost equations --> "Loop" of fun11/3 * CEs [118] --> Loop 88 * CEs [119] --> Loop 89 * CEs [120] --> Loop 90 * CEs [121] --> Loop 91 * CEs [122] --> Loop 92 ### Ranking functions of CR fun11(V1,V,Out) #### Partial ranking functions of CR fun11(V1,V,Out) ### Specialization of cost equations leq/3 * CE 32 is refined into CE [123] * CE 36 is refined into CE [124] * CE 35 is refined into CE [125] * CE 33 is refined into CE [126] * CE 34 is refined into CE [127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217] ### Cost equations --> "Loop" of leq/3 * CEs [194,205,209,215] --> Loop 93 * CEs [175] --> Loop 94 * CEs [159] --> Loop 95 * CEs [129] --> Loop 96 * CEs [203,207,213] --> Loop 97 * CEs [173] --> Loop 98 * CEs [157] --> Loop 99 * CEs [190,200] --> Loop 100 * CEs [169] --> Loop 101 * CEs [153] --> Loop 102 * CEs [188,192,198] --> Loop 103 * CEs [167] --> Loop 104 * CEs [151] --> Loop 105 * CEs [127] --> Loop 106 * CEs [183,184,187] --> Loop 107 * CEs [140,142,149,180,182,186,191,195,201,206,210,216] --> Loop 108 * CEs [145,164,170,176] --> Loop 109 * CEs [137,154,160] --> Loop 110 * CEs [130,134] --> Loop 111 * CEs [139,141,148,179,181,185,189,193,199,204,208,214] --> Loop 112 * CEs [144,146,163,165,166,168,171,172,174,177,178] --> Loop 113 * CEs [136,138,152,155,156,158,161,162] --> Loop 114 * CEs [128,131,132,133,135,143,147,150,196,197,202,211,212,217] --> Loop 115 * CEs [123,124] --> Loop 116 * CEs [125] --> Loop 117 * CEs [126] --> Loop 118 ### Ranking functions of CR leq(V1,V,Out) * RF of phase [93,94,95,96,97,98,99,100,101,102,103,104,105,106]: [V,V1] * RF of phase [107,113,114,115]: [V,V1] #### Partial ranking functions of CR leq(V1,V,Out) * Partial RF of phase [93,94,95,96,97,98,99,100,101,102,103,104,105,106]: - RF of loop [93:1,97:1,100:1,103:1]: V-1 V1-1 - RF of loop [94:1,96:1,98:1,101:1,104:1,106:1]: V - RF of loop [94:1,98:1,101:1,104:1]: V1/2-1/2 - RF of loop [95:1,96:1,99:1,102:1,105:1,106:1]: V1 - RF of loop [95:1,99:1,102:1,105:1]: V/2-1/2 * Partial RF of phase [107,113,114,115]: - RF of loop [107:1]: V-1 V1-1 - RF of loop [113:1]: V1/2-1/2 - RF of loop [113:1,115:1]: V - RF of loop [114:1]: V/2-1/2 - RF of loop [114:1,115:1]: V1 ### Specialization of cost equations insert/3 * CE 27 is refined into CE [218,219,220,221] * CE 30 is refined into CE [222] * CE 28 is refined into CE [223,224] * CE 31 is refined into CE [225] * CE 29 is refined into CE [226,227] ### Cost equations --> "Loop" of insert/3 * CEs [227] --> Loop 119 * CEs [226] --> Loop 120 * CEs [224] --> Loop 121 * CEs [225] --> Loop 122 * CEs [223] --> Loop 123 * CEs [218,219,220,221,222] --> Loop 124 ### Ranking functions of CR insert(V1,V,Out) * RF of phase [119,120]: [V/2-1/2] #### Partial ranking functions of CR insert(V1,V,Out) * Partial RF of phase [119,120]: - RF of loop [119:1]: V1/2+V/2-2 - RF of loop [119:1,120:1]: V/2-1/2 ### Specialization of cost equations isortlist/2 * CE 26 is refined into CE [228,229,230,231,232,233] * CE 24 is refined into CE [234] * CE 25 is refined into CE [235] ### Cost equations --> "Loop" of isortlist/2 * CEs [234] --> Loop 125 * CEs [235] --> Loop 126 * CEs [233] --> Loop 127 * CEs [232] --> Loop 128 * CEs [231] --> Loop 129 * CEs [228] --> Loop 130 * CEs [229] --> Loop 131 * CEs [230] --> Loop 132 ### Ranking functions of CR isortlist(V1,Out) * RF of phase [127,128,129,130]: [V1-1] * RF of phase [132]: [V1] #### Partial ranking functions of CR isortlist(V1,Out) * Partial RF of phase [127,128,129,130]: - RF of loop [127:1,129:1,130:1]: V1-1 - RF of loop [128:1]: V1-2 * Partial RF of phase [132]: - RF of loop [132:1]: V1 ### Specialization of cost equations start/4 * CE 10 is refined into CE [236] * CE 1 is refined into CE [237] * CE 2 is refined into CE [238] * CE 3 is refined into CE [239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257] * CE 4 is refined into CE [258,259,260,261] * CE 5 is refined into CE [262,263] * CE 6 is refined into CE [264] * CE 7 is refined into CE [265,266,267,268,269,270,271,272,273,274,275] * CE 8 is refined into CE [276,277,278,279,280,281] * CE 9 is refined into CE [282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517] * CE 11 is refined into CE [518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753] * CE 12 is refined into CE [754,755,756,757,758,759] * CE 13 is refined into CE [760,761,762,763,764,765,766,767,768,769] * CE 14 is refined into CE [770,771,772,773,774] * CE 15 is refined into CE [775,776,777,778,779,780] * CE 16 is refined into CE [781,782,783,784,785] * CE 17 is refined into CE [786,787,788,789] * CE 18 is refined into CE [790,791,792,793,794] * CE 19 is refined into CE [795,796,797,798,799] * CE 20 is refined into CE [800,801,802,803] * CE 21 is refined into CE [804,805,806,807,808,809,810,811,812] * CE 22 is refined into CE [813,814,815,816,817,818] * CE 23 is refined into CE [819,820,821,822,823] ### Cost equations --> "Loop" of start/4 * CEs [767,810] --> Loop 133 * CEs [662,663,664,672,677,678] --> Loop 134 * CEs [550,551,552,562,563,570,574,575,614,615,622,626,627,628,638,642,643,644,654,658,659,660,670,674,675,682,683,684,685,686,702,706,707,708,718,719,720,721,722,738,742,743,744] --> Loop 135 * CEs [286,287,288,296,301,302,329,330,381,382,388,394,395,396,404,410,411,412,420] --> Loop 136 * CEs [236,258,262,265,776,788] --> Loop 137 * CEs [518,519,520,521,525,526,527,528,529,530,531,533,534,535,536,539,540,541,542,543,544,545,546,547,548,549,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,757,764,765,766,807,808,816] --> Loop 138 * CEs [239,266,802] --> Loop 139 * CEs [282,283,284,294,298,299,306,307,346,347,348,358,362,363,364,374,522,523,524,532,537,538,565,566,617,618,624,630,631,632,640,646,647,648,656,772,773,792,793,797,798,801,821,822] --> Loop 140 * CEs [238,276,277,278,279,280,281,770,771,775,781,786,790,791,795,796,800,819,820] --> Loop 141 * CEs [755,762,763,805,806,814] --> Loop 142 * CEs [237,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,259,260,261,263,264,267,268,269,270,271,272,273,274,275,285,289,290,291,292,293,295,297,300,303,304,305,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,349,350,351,352,353,354,355,356,357,359,360,361,365,366,367,368,369,370,371,372,373,375,376,377,378,379,380,383,384,385,386,387,389,390,391,392,393,397,398,399,400,401,402,403,405,406,407,408,409,413,414,415,416,417,418,419,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,553,554,555,556,557,558,559,560,561,564,567,568,569,571,572,573,576,577,578,579,580,581,616,619,620,621,623,625,629,633,634,635,636,637,639,641,645,649,650,651,652,653,655,657,661,665,666,667,668,669,671,673,676,679,680,681,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,703,704,705,709,710,711,712,713,714,715,716,717,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,739,740,741,745,746,747,748,749,750,751,752,753,754,756,758,759,760,761,768,769,774,777,778,779,780,782,783,784,785,787,789,794,799,803,804,809,811,812,813,815,817,818,823] --> Loop 143 ### Ranking functions of CR start(V1,V,V15,V17) #### Partial ranking functions of CR start(V1,V,V15,V17) Computing Bounds ===================================== #### Cost of chains of fun5(V1,V,Out): * Chain [50]: 0 with precondition: [V1=1,V=1,Out=1] * Chain [49]: 0 with precondition: [V1=1,V=2,Out=1] * Chain [48]: 0 with precondition: [V1=2,V=1,Out=1] * Chain [47]: 0 with precondition: [V1=2,V=2,Out=2] * Chain [46]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of fun1(V1,V,Out): * Chain [62]: 0 with precondition: [V1=0,V=0,Out=2] * Chain [61]: 0 with precondition: [V1=0,Out=1,V>=1] * Chain [60]: 0 with precondition: [V1=1,V=1,Out=2] * Chain [59]: 0 with precondition: [V=0,Out=1,V1>=1] * Chain [58]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [57]: 0 with precondition: [Out=1,V1>=1,V>=1] * Chain [multiple([51,52,53,54,55,56],[[62],[61],[60],[59],[58],[57]])]: 0 with precondition: [2>=Out,V1>=1,V>=1,Out>=0] #### Cost of chains of fun3(V1,Out): * Chain [66]: 0 with precondition: [V1=1,Out=1] * Chain [65]: 0 with precondition: [V1=2,Out=1] * Chain [64]: 0 with precondition: [V1=3,Out=2] * Chain [63]: 0 with precondition: [Out=0,V1>=0] #### Cost of chains of fun4(V1,V,Out): * Chain [[67,68],76]: 0 with precondition: [Out=1,V=V1,V>=1] * Chain [[67,68],75]: 0 with precondition: [Out=2,V1>=1,V>=1,V+V1>=3] * Chain [[67,68],74]: 0 with precondition: [Out=3,V1>=1,V>=1,V+V1>=3] * Chain [[67,68],73]: 0 with precondition: [Out=2,V1>=1,V>=1,V+V1>=3] * Chain [[67,68],72]: 0 with precondition: [Out=3,V1>=1,V>=1,V+V1>=3] * Chain [[67,68],71]: 0 with precondition: [Out=0,V1>=1,V>=1] * Chain [[67,68],70]: 0 with precondition: [Out=2,V1>=2,V>=2] * Chain [[67,68],69]: 0 with precondition: [Out=3,V1>=2,V>=2] * Chain [76]: 0 with precondition: [V1=0,V=0,Out=1] * Chain [75]: 0 with precondition: [V1=0,Out=2,V>=1] * Chain [74]: 0 with precondition: [V1=0,Out=3,V>=1] * Chain [73]: 0 with precondition: [V=0,Out=2,V1>=1] * Chain [72]: 0 with precondition: [V=0,Out=3,V1>=1] * Chain [71]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [70]: 0 with precondition: [Out=2,V1>=1,V>=1] * Chain [69]: 0 with precondition: [Out=3,V1>=1,V>=1] #### Cost of chains of fun2(V1,V,Out): * Chain [87]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [86]: 1 with precondition: [V1=0,V=0,Out=1] * Chain [85]: 1 with precondition: [V1=0,Out=0,V>=1] * Chain [84]: 1 with precondition: [V1=0,Out=1,V>=1] * Chain [83]: 1 with precondition: [V1=0,Out=2,V>=1] * Chain [82]: 1 with precondition: [V=0,Out=0,V1>=1] * Chain [81]: 1 with precondition: [V=0,Out=1,V1>=1] * Chain [80]: 1 with precondition: [V=0,Out=2,V1>=1] * Chain [79]: 1 with precondition: [Out=0,V1=V,V1>=1] * Chain [78]: 1 with precondition: [Out=1,V1>=1,V>=1] * Chain [77]: 1 with precondition: [Out=2,V1>=1,V>=1] #### Cost of chains of fun11(V1,V,Out): * Chain [92]: 0 with precondition: [V1=1,V=1,Out=1] * Chain [91]: 0 with precondition: [V1=1,V=2,Out=2] * Chain [90]: 0 with precondition: [V1=2,V=1,Out=2] * Chain [89]: 0 with precondition: [V1=2,V=2,Out=2] * Chain [88]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of leq(V1,V,Out): * Chain [[107,113,114,115],[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 42*it(93)+28*it(94)+35*it(95)+21*it(97)+2 Such that:aux(40) =< V1/2 aux(47) =< V1 aux(48) =< V aux(49) =< V/2 it(93) =< aux(47) it(95) =< aux(49) it(94) =< aux(47) it(95) =< aux(47) it(97) =< aux(47) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(48) it(94) =< aux(48) it(95) =< aux(48) it(97) =< aux(48) it(97) =< aux(49) with precondition: [Out=0,V1>=3,V>=2] * Chain [[107,113,114,115],[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 126*it(93)+3 Such that:aux(54) =< V1 aux(55) =< V it(93) =< aux(54) it(93) =< aux(55) with precondition: [Out=0,V1>=3,V>=3] * Chain [[107,113,114,115],118]: 14*it(107)+7*it(113)+7*it(114)+2 Such that:it(113) =< V1/2 it(114) =< V/2 aux(56) =< V1 aux(57) =< V it(107) =< aux(56) it(113) =< aux(56) it(114) =< aux(56) it(107) =< aux(57) it(113) =< aux(57) it(114) =< aux(57) with precondition: [Out=0,V1>=2,V>=1] * Chain [[107,113,114,115],117]: 14*it(107)+7*it(113)+7*it(114)+3 Such that:it(113) =< V1/2 it(114) =< V/2 aux(58) =< V1 aux(59) =< V it(107) =< aux(58) it(113) =< aux(58) it(114) =< aux(58) it(107) =< aux(59) it(113) =< aux(59) it(114) =< aux(59) with precondition: [Out=0,V1>=2,V>=2] * Chain [[107,113,114,115],116]: 14*it(107)+7*it(113)+7*it(114)+2 Such that:it(113) =< V1/2 it(114) =< V/2 aux(60) =< V1 aux(61) =< V it(107) =< aux(60) it(113) =< aux(60) it(114) =< aux(60) it(107) =< aux(61) it(113) =< aux(61) it(114) =< aux(61) with precondition: [Out=0,V1>=1,V>=1] * Chain [[107,113,114,115],112,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 70*it(93)+56*it(95)+9 Such that:aux(62) =< V1 aux(63) =< V aux(64) =< V/2 it(93) =< aux(62) it(95) =< aux(64) it(95) =< aux(62) it(93) =< aux(63) it(95) =< aux(63) with precondition: [Out=0,V1>=5,V>=4,V+V1>=10] * Chain [[107,113,114,115],112,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 126*it(93)+10 Such that:aux(65) =< V1 aux(66) =< V it(93) =< aux(65) it(93) =< aux(66) with precondition: [Out=0,V1>=5,V>=5] * Chain [[107,113,114,115],112,117]: 14*it(107)+7*it(113)+7*it(114)+10 Such that:it(113) =< V1/2 it(114) =< V/2 aux(67) =< V1 aux(68) =< V it(107) =< aux(67) it(113) =< aux(67) it(114) =< aux(67) it(107) =< aux(68) it(113) =< aux(68) it(114) =< aux(68) with precondition: [Out=0,V1>=4,V>=4] * Chain [[107,113,114,115],111,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 42*it(93)+28*it(94)+35*it(95)+21*it(97)+9 Such that:aux(40) =< V1/2 aux(69) =< V1 aux(70) =< V aux(71) =< V/2 it(93) =< aux(69) it(95) =< aux(71) it(94) =< aux(69) it(95) =< aux(69) it(97) =< aux(69) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(70) it(94) =< aux(70) it(95) =< aux(70) it(97) =< aux(70) it(97) =< aux(71) with precondition: [Out=0,V1>=4,V>=3] * Chain [[107,113,114,115],111,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 70*it(93)+56*it(94)+10 Such that:aux(72) =< V1 aux(73) =< V1/2 aux(74) =< V it(94) =< aux(73) it(93) =< aux(74) it(93) =< aux(72) it(94) =< aux(72) it(94) =< aux(74) with precondition: [Out=0,V1>=4,V>=4,V+V1>=9] * Chain [[107,113,114,115],111,118]: 14*it(107)+7*it(113)+7*it(114)+9 Such that:it(113) =< V1/2 it(114) =< V/2 aux(75) =< V1 aux(76) =< V it(107) =< aux(75) it(113) =< aux(75) it(114) =< aux(75) it(107) =< aux(76) it(113) =< aux(76) it(114) =< aux(76) with precondition: [Out=0,V1>=3,V>=2] * Chain [[107,113,114,115],110,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 42*it(93)+28*it(94)+35*it(95)+21*it(97)+9 Such that:aux(40) =< V1/2 aux(77) =< V1 aux(78) =< V aux(79) =< V/2 it(93) =< aux(77) it(95) =< aux(79) it(94) =< aux(77) it(95) =< aux(77) it(97) =< aux(77) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(78) it(94) =< aux(78) it(95) =< aux(78) it(97) =< aux(78) it(97) =< aux(79) with precondition: [Out=0,V1>=4,V>=4] * Chain [[107,113,114,115],110,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 70*it(93)+56*it(94)+10 Such that:aux(80) =< V1 aux(81) =< V1/2 aux(82) =< V it(94) =< aux(81) it(93) =< aux(82) it(93) =< aux(80) it(94) =< aux(80) it(94) =< aux(82) with precondition: [Out=0,V1>=4,V>=5,V+V1>=10] * Chain [[107,113,114,115],110,118]: 14*it(107)+7*it(113)+7*it(114)+9 Such that:it(113) =< V1/2 it(114) =< V/2 aux(83) =< V1 aux(84) =< V it(107) =< aux(83) it(113) =< aux(83) it(114) =< aux(83) it(107) =< aux(84) it(113) =< aux(84) it(114) =< aux(84) with precondition: [Out=0,V1>=3,V>=3] * Chain [[107,113,114,115],109,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 42*it(93)+28*it(94)+35*it(95)+21*it(97)+9 Such that:aux(40) =< V1/2 aux(85) =< V1 aux(86) =< V aux(87) =< V/2 it(93) =< aux(85) it(95) =< aux(87) it(94) =< aux(85) it(95) =< aux(85) it(97) =< aux(85) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(86) it(94) =< aux(86) it(95) =< aux(86) it(97) =< aux(86) it(97) =< aux(87) with precondition: [Out=0,V1>=5,V>=3] * Chain [[107,113,114,115],109,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 70*it(93)+56*it(94)+10 Such that:aux(88) =< V1 aux(89) =< V1/2 aux(90) =< V it(94) =< aux(89) it(93) =< aux(90) it(93) =< aux(88) it(94) =< aux(88) it(94) =< aux(90) with precondition: [Out=0,V1>=5,V>=4,V+V1>=10] * Chain [[107,113,114,115],109,118]: 14*it(107)+7*it(113)+7*it(114)+9 Such that:it(113) =< V1/2 it(114) =< V/2 aux(91) =< V1 aux(92) =< V it(107) =< aux(91) it(113) =< aux(91) it(114) =< aux(91) it(107) =< aux(92) it(113) =< aux(92) it(114) =< aux(92) with precondition: [Out=0,V1>=4,V>=2] * Chain [[107,113,114,115],108,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 42*it(93)+28*it(94)+35*it(95)+21*it(97)+9 Such that:aux(40) =< V1/2 aux(93) =< V1 aux(94) =< V aux(95) =< V/2 it(93) =< aux(93) it(95) =< aux(95) it(94) =< aux(93) it(95) =< aux(93) it(97) =< aux(93) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(94) it(94) =< aux(94) it(95) =< aux(94) it(97) =< aux(94) it(97) =< aux(95) with precondition: [Out=0,V1>=5,V>=4] * Chain [[107,113,114,115],108,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 70*it(93)+56*it(94)+10 Such that:aux(96) =< V1 aux(97) =< V1/2 aux(98) =< V it(94) =< aux(97) it(93) =< aux(98) it(93) =< aux(96) it(94) =< aux(96) it(94) =< aux(98) with precondition: [Out=0,V1>=5,V>=5,V+V1>=11] * Chain [[107,113,114,115],108,118]: 14*it(107)+7*it(113)+7*it(114)+9 Such that:it(113) =< V1/2 it(114) =< V/2 aux(99) =< V1 aux(100) =< V it(107) =< aux(99) it(113) =< aux(99) it(114) =< aux(99) it(107) =< aux(100) it(113) =< aux(100) it(114) =< aux(100) with precondition: [Out=0,V1>=4,V>=3] * Chain [[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+2 Such that:aux(39) =< V1 aux(40) =< V1/2 aux(41) =< V aux(42) =< V/2 it(93) =< aux(39) it(94) =< aux(39) it(95) =< aux(39) it(97) =< aux(39) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(41) it(94) =< aux(41) it(95) =< aux(41) it(97) =< aux(41) it(95) =< aux(42) it(97) =< aux(42) with precondition: [2>=Out,V1>=2,V>=1,Out>=1,Out+V+V1>=5] * Chain [[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+3 Such that:aux(50) =< V1 aux(51) =< V1/2 aux(52) =< V aux(53) =< V/2 it(93) =< aux(50) it(94) =< aux(50) it(95) =< aux(50) it(97) =< aux(50) it(94) =< aux(51) it(97) =< aux(51) it(93) =< aux(52) it(94) =< aux(52) it(95) =< aux(52) it(97) =< aux(52) it(95) =< aux(53) it(97) =< aux(53) with precondition: [2>=Out,V1>=2,V>=2,Out>=1,V+V1>=Out+3] * Chain [118]: 2 with precondition: [V1=1,Out=2,V>=0] * Chain [117]: 3 with precondition: [V=1,Out=1,V1>=1] * Chain [116]: 2 with precondition: [Out=0,V1>=0,V>=0] * Chain [112,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+9 Such that:aux(39) =< V1 aux(40) =< V1/2 aux(41) =< V aux(42) =< V/2 it(93) =< aux(39) it(94) =< aux(39) it(95) =< aux(39) it(97) =< aux(39) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(41) it(94) =< aux(41) it(95) =< aux(41) it(97) =< aux(41) it(95) =< aux(42) it(97) =< aux(42) with precondition: [Out=0,V1>=4,V>=3,V+V1>=8] * Chain [112,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+10 Such that:aux(50) =< V1 aux(51) =< V1/2 aux(52) =< V aux(53) =< V/2 it(93) =< aux(50) it(94) =< aux(50) it(95) =< aux(50) it(97) =< aux(50) it(94) =< aux(51) it(97) =< aux(51) it(93) =< aux(52) it(94) =< aux(52) it(95) =< aux(52) it(97) =< aux(52) it(95) =< aux(53) it(97) =< aux(53) with precondition: [Out=0,V1>=4,V>=4] * Chain [112,117]: 10 with precondition: [Out=0,V1>=3,V>=3] * Chain [111,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+9 Such that:aux(39) =< V1 aux(40) =< V1/2 aux(41) =< V aux(42) =< V/2 it(93) =< aux(39) it(94) =< aux(39) it(95) =< aux(39) it(97) =< aux(39) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(41) it(94) =< aux(41) it(95) =< aux(41) it(97) =< aux(41) it(95) =< aux(42) it(97) =< aux(42) with precondition: [Out=0,V1>=3,V>=2] * Chain [111,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+10 Such that:aux(50) =< V1 aux(51) =< V1/2 aux(52) =< V aux(53) =< V/2 it(93) =< aux(50) it(94) =< aux(50) it(95) =< aux(50) it(97) =< aux(50) it(94) =< aux(51) it(97) =< aux(51) it(93) =< aux(52) it(94) =< aux(52) it(95) =< aux(52) it(97) =< aux(52) it(95) =< aux(53) it(97) =< aux(53) with precondition: [Out=0,V1>=3,V>=3,V+V1>=7] * Chain [111,118]: 9 with precondition: [V1=2,Out=0,V>=1] * Chain [110,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+9 Such that:aux(39) =< V1 aux(40) =< V1/2 aux(41) =< V aux(42) =< V/2 it(93) =< aux(39) it(94) =< aux(39) it(95) =< aux(39) it(97) =< aux(39) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(41) it(94) =< aux(41) it(95) =< aux(41) it(97) =< aux(41) it(95) =< aux(42) it(97) =< aux(42) with precondition: [Out=0,V1>=3,V>=3] * Chain [110,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+10 Such that:aux(50) =< V1 aux(51) =< V1/2 aux(52) =< V aux(53) =< V/2 it(93) =< aux(50) it(94) =< aux(50) it(95) =< aux(50) it(97) =< aux(50) it(94) =< aux(51) it(97) =< aux(51) it(93) =< aux(52) it(94) =< aux(52) it(95) =< aux(52) it(97) =< aux(52) it(95) =< aux(53) it(97) =< aux(53) with precondition: [Out=0,V1>=3,V>=4,V+V1>=8] * Chain [110,118]: 9 with precondition: [V1=2,Out=0,V>=2] * Chain [109,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+9 Such that:aux(39) =< V1 aux(40) =< V1/2 aux(41) =< V aux(42) =< V/2 it(93) =< aux(39) it(94) =< aux(39) it(95) =< aux(39) it(97) =< aux(39) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(41) it(94) =< aux(41) it(95) =< aux(41) it(97) =< aux(41) it(95) =< aux(42) it(97) =< aux(42) with precondition: [Out=0,V1>=4,V>=2] * Chain [109,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+10 Such that:aux(50) =< V1 aux(51) =< V1/2 aux(52) =< V aux(53) =< V/2 it(93) =< aux(50) it(94) =< aux(50) it(95) =< aux(50) it(97) =< aux(50) it(94) =< aux(51) it(97) =< aux(51) it(93) =< aux(52) it(94) =< aux(52) it(95) =< aux(52) it(97) =< aux(52) it(95) =< aux(53) it(97) =< aux(53) with precondition: [Out=0,V1>=4,V>=3,V+V1>=8] * Chain [109,118]: 9 with precondition: [Out=0,V1>=3,V>=1] * Chain [108,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],118]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+9 Such that:aux(39) =< V1 aux(40) =< V1/2 aux(41) =< V aux(42) =< V/2 it(93) =< aux(39) it(94) =< aux(39) it(95) =< aux(39) it(97) =< aux(39) it(94) =< aux(40) it(97) =< aux(40) it(93) =< aux(41) it(94) =< aux(41) it(95) =< aux(41) it(97) =< aux(41) it(95) =< aux(42) it(97) =< aux(42) with precondition: [Out=0,V1>=4,V>=3] * Chain [108,[93,94,95,96,97,98,99,100,101,102,103,104,105,106],117]: 21*it(93)+28*it(94)+28*it(95)+21*it(97)+10 Such that:aux(50) =< V1 aux(51) =< V1/2 aux(52) =< V aux(53) =< V/2 it(93) =< aux(50) it(94) =< aux(50) it(95) =< aux(50) it(97) =< aux(50) it(94) =< aux(51) it(97) =< aux(51) it(93) =< aux(52) it(94) =< aux(52) it(95) =< aux(52) it(97) =< aux(52) it(95) =< aux(53) it(97) =< aux(53) with precondition: [Out=0,V1>=4,V>=4,V+V1>=9] * Chain [108,118]: 9 with precondition: [Out=0,V1>=3,V>=2] #### Cost of chains of insert(V1,V,Out): * Chain [[119,120],124]: 6*it(119)+6*it(120)+756*s(212)+623*s(213)+1176*s(214)+357*s(215)+42*s(240)+56*s(241)+56*s(242)+42*s(243)+12 Such that:aux(116) =< V1+V+1 aux(110) =< V1/2 it(119) =< V1/2+V/2 aux(111) =< V-Out aux(119) =< V/2 aux(112) =< V/2-Out/2 aux(117) =< Out aux(121) =< V1 aux(122) =< Out/2 s(212) =< aux(110) s(213) =< aux(112) s(214) =< aux(121) s(212) =< aux(121) s(213) =< aux(121) s(215) =< aux(121) s(215) =< aux(110) s(214) =< aux(111) s(212) =< aux(111) s(213) =< aux(111) s(215) =< aux(111) s(215) =< aux(112) aux(115) =< aux(116) it(120) =< aux(116) aux(115) =< aux(117) it(120) =< aux(117) it(119) =< aux(122) it(120) =< aux(122) it(119) =< aux(119) it(120) =< aux(119) s(244) =< aux(115)*(1/2) aux(114) =< it(119)*aux(121) s(246) =< aux(114)*(1/2) s(240) =< aux(114) s(241) =< aux(114) s(242) =< aux(114) s(243) =< aux(114) s(241) =< s(246) s(243) =< s(246) s(240) =< aux(115) s(241) =< aux(115) s(242) =< aux(115) s(243) =< aux(115) s(242) =< s(244) s(243) =< s(244) with precondition: [V1>=1,Out>=2,V>=Out] * Chain [[119,120],123]: 6*it(119)+6*it(120)+42*s(240)+56*s(241)+56*s(242)+42*s(243)+5 Such that:aux(113) =< 1 aux(123) =< Out aux(124) =< Out/2 it(119) =< aux(124) it(120) =< aux(123) it(120) =< aux(124) s(244) =< aux(123)*(1/2) aux(114) =< it(119)*aux(113) s(246) =< aux(114)*(1/2) s(240) =< aux(114) s(241) =< aux(114) s(242) =< aux(114) s(243) =< aux(114) s(241) =< s(246) s(243) =< s(246) s(240) =< aux(123) s(241) =< aux(123) s(242) =< aux(123) s(243) =< aux(123) s(242) =< s(244) s(243) =< s(244) with precondition: [V1=1,V+2=Out,V>=3] * Chain [[119,120],122]: 6*it(119)+6*it(120)+42*s(240)+56*s(241)+56*s(242)+42*s(243)+2 Such that:aux(117) =< -V1+Out aux(113) =< V1 aux(116) =< Out it(119) =< Out/2 aux(125) =< -V1/2+Out/2 aux(115) =< aux(116) it(120) =< aux(116) aux(115) =< aux(117) it(120) =< aux(117) it(119) =< aux(125) it(120) =< aux(125) s(244) =< aux(115)*(1/2) aux(114) =< it(119)*aux(113) s(246) =< aux(114)*(1/2) s(240) =< aux(114) s(241) =< aux(114) s(242) =< aux(114) s(243) =< aux(114) s(241) =< s(246) s(243) =< s(246) s(240) =< aux(115) s(241) =< aux(115) s(242) =< aux(115) s(243) =< aux(115) s(242) =< s(244) s(243) =< s(244) with precondition: [V+V1+1=Out,V1>=1,V>=3] * Chain [[119,120],121]: 6*it(119)+6*it(120)+42*s(240)+56*s(241)+56*s(242)+42*s(243)+98*s(252)+98*s(253)+6 Such that:aux(119) =< -V1/2+Out/2 s(249) =< V1/2 aux(116) =< Out it(119) =< Out/2 aux(126) =< -V1+Out aux(127) =< V1 s(252) =< aux(127) s(253) =< aux(127) s(253) =< s(249) s(252) =< aux(126) s(253) =< aux(126) aux(115) =< aux(116) it(120) =< aux(116) aux(115) =< aux(126) it(120) =< aux(126) it(119) =< aux(126) it(119) =< aux(119) it(120) =< aux(119) s(244) =< aux(115)*(1/2) aux(114) =< it(119)*aux(127) s(246) =< aux(114)*(1/2) s(240) =< aux(114) s(241) =< aux(114) s(242) =< aux(114) s(243) =< aux(114) s(241) =< s(246) s(243) =< s(246) s(240) =< aux(115) s(241) =< aux(115) s(242) =< aux(115) s(243) =< aux(115) s(242) =< s(244) s(243) =< s(244) with precondition: [V+V1+1=Out,V1>=2,V>=4] * Chain [124]: 756*s(212)+623*s(213)+1176*s(214)+357*s(215)+12 Such that:aux(109) =< V1 aux(110) =< V1/2 aux(111) =< V aux(112) =< V/2 s(212) =< aux(110) s(213) =< aux(112) s(214) =< aux(109) s(212) =< aux(109) s(213) =< aux(109) s(215) =< aux(109) s(215) =< aux(110) s(214) =< aux(111) s(212) =< aux(111) s(213) =< aux(111) s(215) =< aux(111) s(215) =< aux(112) with precondition: [Out=0,V1>=0,V>=0] * Chain [123]: 5 with precondition: [V1=1,V+2=Out,V>=1] * Chain [122]: 2 with precondition: [V=1,V1+2=Out,V1>=0] * Chain [121]: 42*s(252)+56*s(253)+56*s(254)+42*s(255)+6 Such that:s(248) =< V1 s(249) =< V1/2 s(250) =< V s(251) =< V/2 s(252) =< s(248) s(253) =< s(248) s(254) =< s(248) s(255) =< s(248) s(253) =< s(249) s(255) =< s(249) s(252) =< s(250) s(253) =< s(250) s(254) =< s(250) s(255) =< s(250) s(254) =< s(251) s(255) =< s(251) with precondition: [V+V1+1=Out,V1>=2,V>=2] #### Cost of chains of isortlist(V1,Out): * Chain [[132],[127,128,129,130],131,126]: 51*it(127)+6*s(428)+1113*s(429)+1799*s(430)+6*s(431)+42*s(432)+56*s(433)+56*s(434)+42*s(435)+42*s(445)+56*s(446)+56*s(447)+42*s(448)+6*s(453)+6*s(454)+12*s(455)+42*s(456)+56*s(457)+56*s(458)+42*s(459)+98*s(460)+98*s(461)+42*s(462)+56*s(463)+56*s(464)+42*s(465)+6*s(478)+6*s(479)+42*s(480)+56*s(481)+56*s(482)+42*s(483)+756*s(505)+623*s(506)+1176*s(507)+357*s(508)+6 Such that:s(416) =< 1 aux(158) =< V1 it(127) =< aux(158) aux(135) =< aux(158)+3 aux(146) =< aux(158)+2 aux(141) =< aux(158) aux(138) =< aux(158)+1 s(444) =< aux(158)*(1/2) aux(136) =< it(127)*aux(135) aux(147) =< it(127)*aux(146) aux(142) =< it(127)*aux(141) aux(139) =< it(127)*aux(138) s(477) =< aux(136)*(1/2) s(470) =< aux(147)*(1/2) s(449) =< aux(142)*(1/2) s(440) =< aux(139)*(1/2) s(428) =< aux(136)*(1/2) s(478) =< s(477) s(479) =< aux(136) s(479) =< s(477) s(487) =< s(478)*s(416) s(486) =< s(487)*(1/2) s(480) =< s(487) s(481) =< s(487) s(482) =< s(487) s(483) =< s(487) s(481) =< s(486) s(483) =< s(486) s(480) =< aux(136) s(481) =< aux(136) s(482) =< aux(136) s(483) =< aux(136) s(482) =< s(477) s(483) =< s(477) s(453) =< s(477) s(454) =< s(477) s(467) =< aux(136) s(455) =< aux(136) s(467) =< aux(147) s(455) =< aux(147) s(454) =< s(470) s(455) =< s(470) s(466) =< s(467)*(1/2) s(475) =< s(454)*aux(158) s(474) =< s(475)*(1/2) s(456) =< s(475) s(457) =< s(475) s(458) =< s(475) s(459) =< s(475) s(457) =< s(474) s(459) =< s(474) s(456) =< s(467) s(457) =< s(467) s(458) =< s(467) s(459) =< s(467) s(458) =< s(466) s(459) =< s(466) s(460) =< aux(158) s(461) =< aux(158) s(461) =< s(444) s(460) =< aux(147) s(461) =< aux(147) s(453) =< aux(147) s(453) =< s(470) s(469) =< s(453)*aux(158) s(468) =< s(469)*(1/2) s(462) =< s(469) s(463) =< s(469) s(464) =< s(469) s(465) =< s(469) s(463) =< s(468) s(465) =< s(468) s(462) =< s(467) s(463) =< s(467) s(464) =< s(467) s(465) =< s(467) s(464) =< s(466) s(465) =< s(466) s(445) =< aux(158) s(446) =< aux(158) s(447) =< aux(158) s(448) =< aux(158) s(446) =< s(444) s(448) =< s(444) s(445) =< aux(142) s(446) =< aux(142) s(447) =< aux(142) s(448) =< aux(142) s(447) =< s(449) s(448) =< s(449) s(429) =< s(444) s(430) =< aux(139) s(430) =< aux(158) s(429) =< aux(158) s(429) =< aux(139) s(437) =< aux(136) s(431) =< aux(136) s(437) =< aux(139) s(431) =< aux(139) s(428) =< s(440) s(431) =< s(440) s(436) =< s(437)*(1/2) s(439) =< s(428)*aux(138) s(438) =< s(439)*(1/2) s(432) =< s(439) s(433) =< s(439) s(434) =< s(439) s(435) =< s(439) s(433) =< s(438) s(435) =< s(438) s(432) =< s(437) s(433) =< s(437) s(434) =< s(437) s(435) =< s(437) s(434) =< s(436) s(435) =< s(436) aux(155) =< it(127)*aux(158) s(509) =< aux(155)*(1/2) s(505) =< s(444) s(506) =< s(509) s(507) =< aux(158) s(505) =< aux(158) s(506) =< aux(158) s(508) =< aux(158) s(508) =< s(444) s(507) =< aux(155) s(505) =< aux(155) s(506) =< aux(155) s(508) =< aux(155) s(508) =< s(509) with precondition: [Out=0,V1>=5] * Chain [[132],[127,128,129,130],126]: 51*it(127)+6*s(428)+1113*s(429)+1799*s(430)+6*s(431)+42*s(432)+56*s(433)+56*s(434)+42*s(435)+42*s(445)+56*s(446)+56*s(447)+42*s(448)+6*s(453)+6*s(454)+12*s(455)+42*s(456)+56*s(457)+56*s(458)+42*s(459)+98*s(460)+98*s(461)+42*s(462)+56*s(463)+56*s(464)+42*s(465)+6*s(478)+6*s(479)+42*s(480)+56*s(481)+56*s(482)+42*s(483)+756*s(505)+623*s(506)+1176*s(507)+357*s(508)+2 Such that:s(416) =< 1 aux(160) =< V1 it(127) =< aux(160) aux(135) =< aux(160)+3 aux(146) =< aux(160)+2 aux(141) =< aux(160) aux(138) =< aux(160)+1 s(444) =< aux(160)*(1/2) aux(136) =< it(127)*aux(135) aux(147) =< it(127)*aux(146) aux(142) =< it(127)*aux(141) aux(139) =< it(127)*aux(138) s(477) =< aux(136)*(1/2) s(470) =< aux(147)*(1/2) s(449) =< aux(142)*(1/2) s(440) =< aux(139)*(1/2) s(428) =< aux(136)*(1/2) s(478) =< s(477) s(479) =< aux(136) s(479) =< s(477) s(487) =< s(478)*s(416) s(486) =< s(487)*(1/2) s(480) =< s(487) s(481) =< s(487) s(482) =< s(487) s(483) =< s(487) s(481) =< s(486) s(483) =< s(486) s(480) =< aux(136) s(481) =< aux(136) s(482) =< aux(136) s(483) =< aux(136) s(482) =< s(477) s(483) =< s(477) s(453) =< s(477) s(454) =< s(477) s(467) =< aux(136) s(455) =< aux(136) s(467) =< aux(147) s(455) =< aux(147) s(454) =< s(470) s(455) =< s(470) s(466) =< s(467)*(1/2) s(475) =< s(454)*aux(160) s(474) =< s(475)*(1/2) s(456) =< s(475) s(457) =< s(475) s(458) =< s(475) s(459) =< s(475) s(457) =< s(474) s(459) =< s(474) s(456) =< s(467) s(457) =< s(467) s(458) =< s(467) s(459) =< s(467) s(458) =< s(466) s(459) =< s(466) s(460) =< aux(160) s(461) =< aux(160) s(461) =< s(444) s(460) =< aux(147) s(461) =< aux(147) s(453) =< aux(147) s(453) =< s(470) s(469) =< s(453)*aux(160) s(468) =< s(469)*(1/2) s(462) =< s(469) s(463) =< s(469) s(464) =< s(469) s(465) =< s(469) s(463) =< s(468) s(465) =< s(468) s(462) =< s(467) s(463) =< s(467) s(464) =< s(467) s(465) =< s(467) s(464) =< s(466) s(465) =< s(466) s(445) =< aux(160) s(446) =< aux(160) s(447) =< aux(160) s(448) =< aux(160) s(446) =< s(444) s(448) =< s(444) s(445) =< aux(142) s(446) =< aux(142) s(447) =< aux(142) s(448) =< aux(142) s(447) =< s(449) s(448) =< s(449) s(429) =< s(444) s(430) =< aux(139) s(430) =< aux(160) s(429) =< aux(160) s(429) =< aux(139) s(437) =< aux(136) s(431) =< aux(136) s(437) =< aux(139) s(431) =< aux(139) s(428) =< s(440) s(431) =< s(440) s(436) =< s(437)*(1/2) s(439) =< s(428)*aux(138) s(438) =< s(439)*(1/2) s(432) =< s(439) s(433) =< s(439) s(434) =< s(439) s(435) =< s(439) s(433) =< s(438) s(435) =< s(438) s(432) =< s(437) s(433) =< s(437) s(434) =< s(437) s(435) =< s(437) s(434) =< s(436) s(435) =< s(436) aux(155) =< it(127)*aux(160) s(509) =< aux(155)*(1/2) s(505) =< s(444) s(506) =< s(509) s(507) =< aux(160) s(505) =< aux(160) s(506) =< aux(160) s(508) =< aux(160) s(508) =< s(444) s(507) =< aux(155) s(505) =< aux(155) s(506) =< aux(155) s(508) =< aux(155) s(508) =< s(509) with precondition: [Out=0,V1>=4] * Chain [[132],131,126]: 14*it(132)+756*s(505)+623*s(506)+1176*s(507)+357*s(508)+6 Such that:aux(161) =< V1 it(132) =< aux(161) aux(155) =< it(132)*aux(161) s(511) =< aux(161)*(1/2) s(509) =< aux(155)*(1/2) s(505) =< s(511) s(506) =< s(509) s(507) =< aux(161) s(505) =< aux(161) s(506) =< aux(161) s(508) =< aux(161) s(508) =< s(511) s(507) =< aux(155) s(505) =< aux(155) s(506) =< aux(155) s(508) =< aux(155) s(508) =< s(509) with precondition: [Out=0,V1>=3] * Chain [[132],126]: 14*it(132)+756*s(505)+623*s(506)+1176*s(507)+357*s(508)+2 Such that:aux(162) =< V1 it(132) =< aux(162) aux(155) =< it(132)*aux(162) s(511) =< aux(162)*(1/2) s(509) =< aux(155)*(1/2) s(505) =< s(511) s(506) =< s(509) s(507) =< aux(162) s(505) =< aux(162) s(506) =< aux(162) s(508) =< aux(162) s(508) =< s(511) s(507) =< aux(155) s(505) =< aux(155) s(506) =< aux(155) s(508) =< aux(155) s(508) =< s(509) with precondition: [Out=0,V1>=2] * Chain [[132],125]: 14*it(132)+756*s(505)+623*s(506)+1176*s(507)+357*s(508)+1 Such that:aux(163) =< V1 it(132) =< aux(163) aux(155) =< it(132)*aux(163) s(511) =< aux(163)*(1/2) s(509) =< aux(155)*(1/2) s(505) =< s(511) s(506) =< s(509) s(507) =< aux(163) s(505) =< aux(163) s(506) =< aux(163) s(508) =< aux(163) s(508) =< s(511) s(507) =< aux(155) s(505) =< aux(155) s(506) =< aux(155) s(508) =< aux(155) s(508) =< s(509) with precondition: [Out=0,V1>=1] * Chain [[127,128,129,130],131,126]: 37*it(127)+6*s(428)+1113*s(429)+1799*s(430)+6*s(431)+42*s(432)+56*s(433)+56*s(434)+42*s(435)+42*s(445)+56*s(446)+56*s(447)+42*s(448)+6*s(453)+6*s(454)+12*s(455)+42*s(456)+56*s(457)+56*s(458)+42*s(459)+98*s(460)+98*s(461)+42*s(462)+56*s(463)+56*s(464)+42*s(465)+6*s(478)+6*s(479)+42*s(480)+56*s(481)+56*s(482)+42*s(483)+6 Such that:s(416) =< 1 aux(152) =< V1 it(127) =< aux(152) aux(135) =< aux(152)+3 aux(146) =< aux(152)+2 aux(141) =< aux(152) aux(138) =< aux(152)+1 s(444) =< aux(152)*(1/2) aux(136) =< it(127)*aux(135) aux(147) =< it(127)*aux(146) aux(142) =< it(127)*aux(141) aux(139) =< it(127)*aux(138) s(477) =< aux(136)*(1/2) s(470) =< aux(147)*(1/2) s(449) =< aux(142)*(1/2) s(440) =< aux(139)*(1/2) s(428) =< aux(136)*(1/2) s(478) =< s(477) s(479) =< aux(136) s(479) =< s(477) s(487) =< s(478)*s(416) s(486) =< s(487)*(1/2) s(480) =< s(487) s(481) =< s(487) s(482) =< s(487) s(483) =< s(487) s(481) =< s(486) s(483) =< s(486) s(480) =< aux(136) s(481) =< aux(136) s(482) =< aux(136) s(483) =< aux(136) s(482) =< s(477) s(483) =< s(477) s(453) =< s(477) s(454) =< s(477) s(467) =< aux(136) s(455) =< aux(136) s(467) =< aux(147) s(455) =< aux(147) s(454) =< s(470) s(455) =< s(470) s(466) =< s(467)*(1/2) s(475) =< s(454)*aux(152) s(474) =< s(475)*(1/2) s(456) =< s(475) s(457) =< s(475) s(458) =< s(475) s(459) =< s(475) s(457) =< s(474) s(459) =< s(474) s(456) =< s(467) s(457) =< s(467) s(458) =< s(467) s(459) =< s(467) s(458) =< s(466) s(459) =< s(466) s(460) =< aux(152) s(461) =< aux(152) s(461) =< s(444) s(460) =< aux(147) s(461) =< aux(147) s(453) =< aux(147) s(453) =< s(470) s(469) =< s(453)*aux(152) s(468) =< s(469)*(1/2) s(462) =< s(469) s(463) =< s(469) s(464) =< s(469) s(465) =< s(469) s(463) =< s(468) s(465) =< s(468) s(462) =< s(467) s(463) =< s(467) s(464) =< s(467) s(465) =< s(467) s(464) =< s(466) s(465) =< s(466) s(445) =< aux(152) s(446) =< aux(152) s(447) =< aux(152) s(448) =< aux(152) s(446) =< s(444) s(448) =< s(444) s(445) =< aux(142) s(446) =< aux(142) s(447) =< aux(142) s(448) =< aux(142) s(447) =< s(449) s(448) =< s(449) s(429) =< s(444) s(430) =< aux(139) s(430) =< aux(152) s(429) =< aux(152) s(429) =< aux(139) s(437) =< aux(136) s(431) =< aux(136) s(437) =< aux(139) s(431) =< aux(139) s(428) =< s(440) s(431) =< s(440) s(436) =< s(437)*(1/2) s(439) =< s(428)*aux(138) s(438) =< s(439)*(1/2) s(432) =< s(439) s(433) =< s(439) s(434) =< s(439) s(435) =< s(439) s(433) =< s(438) s(435) =< s(438) s(432) =< s(437) s(433) =< s(437) s(434) =< s(437) s(435) =< s(437) s(434) =< s(436) s(435) =< s(436) with precondition: [V1>=4,Out>=2,V1>=Out] * Chain [[127,128,129,130],126]: 37*it(127)+6*s(428)+1113*s(429)+1799*s(430)+6*s(431)+42*s(432)+56*s(433)+56*s(434)+42*s(435)+42*s(445)+56*s(446)+56*s(447)+42*s(448)+6*s(453)+6*s(454)+12*s(455)+42*s(456)+56*s(457)+56*s(458)+42*s(459)+98*s(460)+98*s(461)+42*s(462)+56*s(463)+56*s(464)+42*s(465)+6*s(478)+6*s(479)+42*s(480)+56*s(481)+56*s(482)+42*s(483)+2 Such that:s(416) =< 1 aux(159) =< V1 it(127) =< aux(159) aux(135) =< aux(159)+3 aux(146) =< aux(159)+2 aux(141) =< aux(159) aux(138) =< aux(159)+1 s(444) =< aux(159)*(1/2) aux(136) =< it(127)*aux(135) aux(147) =< it(127)*aux(146) aux(142) =< it(127)*aux(141) aux(139) =< it(127)*aux(138) s(477) =< aux(136)*(1/2) s(470) =< aux(147)*(1/2) s(449) =< aux(142)*(1/2) s(440) =< aux(139)*(1/2) s(428) =< aux(136)*(1/2) s(478) =< s(477) s(479) =< aux(136) s(479) =< s(477) s(487) =< s(478)*s(416) s(486) =< s(487)*(1/2) s(480) =< s(487) s(481) =< s(487) s(482) =< s(487) s(483) =< s(487) s(481) =< s(486) s(483) =< s(486) s(480) =< aux(136) s(481) =< aux(136) s(482) =< aux(136) s(483) =< aux(136) s(482) =< s(477) s(483) =< s(477) s(453) =< s(477) s(454) =< s(477) s(467) =< aux(136) s(455) =< aux(136) s(467) =< aux(147) s(455) =< aux(147) s(454) =< s(470) s(455) =< s(470) s(466) =< s(467)*(1/2) s(475) =< s(454)*aux(159) s(474) =< s(475)*(1/2) s(456) =< s(475) s(457) =< s(475) s(458) =< s(475) s(459) =< s(475) s(457) =< s(474) s(459) =< s(474) s(456) =< s(467) s(457) =< s(467) s(458) =< s(467) s(459) =< s(467) s(458) =< s(466) s(459) =< s(466) s(460) =< aux(159) s(461) =< aux(159) s(461) =< s(444) s(460) =< aux(147) s(461) =< aux(147) s(453) =< aux(147) s(453) =< s(470) s(469) =< s(453)*aux(159) s(468) =< s(469)*(1/2) s(462) =< s(469) s(463) =< s(469) s(464) =< s(469) s(465) =< s(469) s(463) =< s(468) s(465) =< s(468) s(462) =< s(467) s(463) =< s(467) s(464) =< s(467) s(465) =< s(467) s(464) =< s(466) s(465) =< s(466) s(445) =< aux(159) s(446) =< aux(159) s(447) =< aux(159) s(448) =< aux(159) s(446) =< s(444) s(448) =< s(444) s(445) =< aux(142) s(446) =< aux(142) s(447) =< aux(142) s(448) =< aux(142) s(447) =< s(449) s(448) =< s(449) s(429) =< s(444) s(430) =< aux(139) s(430) =< aux(159) s(429) =< aux(159) s(429) =< aux(139) s(437) =< aux(136) s(431) =< aux(136) s(437) =< aux(139) s(431) =< aux(139) s(428) =< s(440) s(431) =< s(440) s(436) =< s(437)*(1/2) s(439) =< s(428)*aux(138) s(438) =< s(439)*(1/2) s(432) =< s(439) s(433) =< s(439) s(434) =< s(439) s(435) =< s(439) s(433) =< s(438) s(435) =< s(438) s(432) =< s(437) s(433) =< s(437) s(434) =< s(437) s(435) =< s(437) s(434) =< s(436) s(435) =< s(436) with precondition: [Out>=2,V1>=Out,V1+2*Out>=9] * Chain [131,126]: 6 with precondition: [V1=Out,V1>=2] * Chain [126]: 2 with precondition: [V1=1,Out=1] * Chain [125]: 1 with precondition: [Out=0,V1>=0] #### Cost of chains of start(V1,V,V15,V17): * Chain [143]: 756*s(674)+623*s(675)+1176*s(676)+357*s(677)+19392*s(680)+96*s(694)+96*s(695)+96*s(696)+672*s(699)+896*s(700)+896*s(701)+672*s(702)+96*s(703)+96*s(704)+192*s(706)+672*s(710)+896*s(711)+896*s(712)+672*s(713)+1568*s(714)+1568*s(715)+672*s(718)+896*s(719)+896*s(720)+672*s(721)+672*s(722)+896*s(723)+896*s(724)+672*s(725)+17808*s(726)+28784*s(727)+96*s(729)+672*s(733)+896*s(734)+896*s(735)+672*s(736)+7560*s(739)+6230*s(740)+11760*s(741)+3570*s(742)+48*s(754)+84*s(755)+126*s(759)+168*s(760)+168*s(761)+126*s(762)+210*s(784)+280*s(785)+280*s(786)+210*s(787)+168*s(792)+224*s(793)+224*s(794)+168*s(795)+27181*s(1570)+29036*s(1571)+45171*s(1572)+15036*s(1573)+12*s(1604)+18*s(1605)+30*s(1607)+126*s(1611)+168*s(1612)+168*s(1613)+126*s(1614)+84*s(1619)+112*s(1620)+112*s(1621)+84*s(1622)+98*s(1681)+98*s(1682)+12*s(1736)+42*s(1752)+56*s(1753)+56*s(1754)+42*s(1755)+14448*s(2704)+12320*s(2705)+20580*s(2706)+7476*s(2707)+2604*s(3008)+2205*s(3009)+3780*s(3010)+1323*s(3011)+6*s(3402)+6*s(3403)+12*s(3405)+42*s(3409)+56*s(3410)+56*s(3411)+42*s(3412)+98*s(3413)+98*s(3414)+42*s(3417)+56*s(3418)+56*s(3419)+42*s(3420)+6*s(3431)+6*s(3443)+42*s(3447)+56*s(3448)+56*s(3449)+42*s(3450)+19 Such that:s(673) =< 1/2 s(3401) =< V1/2+V/2+1/2 s(3397) =< V+1 s(3399) =< V/2+1/2 aux(206) =< 1 aux(207) =< V1 aux(208) =< V1-V aux(209) =< V1+V aux(210) =< V1+V+1 aux(211) =< V1/2 aux(212) =< V1/2-V/2 aux(213) =< V1/2+V/2 aux(214) =< V aux(215) =< V/2 aux(216) =< V15 aux(217) =< V15/2 s(1605) =< aux(213) s(3431) =< aux(213) s(674) =< aux(211) s(675) =< s(673) s(676) =< aux(207) s(674) =< aux(207) s(675) =< aux(207) s(677) =< aux(207) s(677) =< aux(211) s(676) =< aux(206) s(674) =< aux(206) s(675) =< aux(206) s(677) =< aux(206) s(677) =< s(673) s(680) =< aux(207) s(681) =< aux(207)+3 s(682) =< aux(207)+2 s(683) =< aux(207) s(684) =< aux(207)+1 s(685) =< aux(207)*(1/2) s(686) =< s(680)*s(681) s(687) =< s(680)*s(682) s(688) =< s(680)*s(683) s(689) =< s(680)*s(684) s(690) =< s(686)*(1/2) s(691) =< s(687)*(1/2) s(692) =< s(688)*(1/2) s(693) =< s(689)*(1/2) s(694) =< s(686)*(1/2) s(695) =< s(690) s(696) =< s(686) s(696) =< s(690) s(697) =< s(695)*aux(206) s(698) =< s(697)*(1/2) s(699) =< s(697) s(700) =< s(697) s(701) =< s(697) s(702) =< s(697) s(700) =< s(698) s(702) =< s(698) s(699) =< s(686) s(700) =< s(686) s(701) =< s(686) s(702) =< s(686) s(701) =< s(690) s(702) =< s(690) s(703) =< s(690) s(704) =< s(690) s(705) =< s(686) s(706) =< s(686) s(705) =< s(687) s(706) =< s(687) s(704) =< s(691) s(706) =< s(691) s(707) =< s(705)*(1/2) s(708) =< s(704)*aux(207) s(709) =< s(708)*(1/2) s(710) =< s(708) s(711) =< s(708) s(712) =< s(708) s(713) =< s(708) s(711) =< s(709) s(713) =< s(709) s(710) =< s(705) s(711) =< s(705) s(712) =< s(705) s(713) =< s(705) s(712) =< s(707) s(713) =< s(707) s(714) =< aux(207) s(715) =< aux(207) s(715) =< s(685) s(714) =< s(687) s(715) =< s(687) s(703) =< s(687) s(703) =< s(691) s(716) =< s(703)*aux(207) s(717) =< s(716)*(1/2) s(718) =< s(716) s(719) =< s(716) s(720) =< s(716) s(721) =< s(716) s(719) =< s(717) s(721) =< s(717) s(718) =< s(705) s(719) =< s(705) s(720) =< s(705) s(721) =< s(705) s(720) =< s(707) s(721) =< s(707) s(722) =< aux(207) s(723) =< aux(207) s(724) =< aux(207) s(725) =< aux(207) s(723) =< s(685) s(725) =< s(685) s(722) =< s(688) s(723) =< s(688) s(724) =< s(688) s(725) =< s(688) s(724) =< s(692) s(725) =< s(692) s(726) =< s(685) s(727) =< s(689) s(727) =< aux(207) s(726) =< aux(207) s(726) =< s(689) s(728) =< s(686) s(729) =< s(686) s(728) =< s(689) s(729) =< s(689) s(694) =< s(693) s(729) =< s(693) s(730) =< s(728)*(1/2) s(731) =< s(694)*s(684) s(732) =< s(731)*(1/2) s(733) =< s(731) s(734) =< s(731) s(735) =< s(731) s(736) =< s(731) s(734) =< s(732) s(736) =< s(732) s(733) =< s(728) s(734) =< s(728) s(735) =< s(728) s(736) =< s(728) s(735) =< s(730) s(736) =< s(730) s(737) =< s(680)*aux(207) s(738) =< s(737)*(1/2) s(739) =< s(685) s(740) =< s(738) s(741) =< aux(207) s(739) =< aux(207) s(740) =< aux(207) s(742) =< aux(207) s(742) =< s(685) s(741) =< s(737) s(739) =< s(737) s(740) =< s(737) s(742) =< s(737) s(742) =< s(738) s(754) =< aux(211) s(755) =< aux(207) s(755) =< aux(211) s(757) =< s(754)*aux(206) s(758) =< s(757)*(1/2) s(759) =< s(757) s(760) =< s(757) s(761) =< s(757) s(762) =< s(757) s(760) =< s(758) s(762) =< s(758) s(759) =< aux(207) s(760) =< aux(207) s(761) =< aux(207) s(762) =< aux(207) s(761) =< s(685) s(762) =< s(685) s(782) =< s(754)*aux(207) s(783) =< s(782)*(1/2) s(784) =< s(782) s(785) =< s(782) s(786) =< s(782) s(787) =< s(782) s(785) =< s(783) s(787) =< s(783) s(784) =< aux(207) s(785) =< aux(207) s(786) =< aux(207) s(787) =< aux(207) s(786) =< s(685) s(787) =< s(685) s(790) =< s(755)*aux(207) s(791) =< s(790)*(1/2) s(792) =< s(790) s(793) =< s(790) s(794) =< s(790) s(795) =< s(790) s(793) =< s(791) s(795) =< s(791) s(792) =< aux(207) s(793) =< aux(207) s(794) =< aux(207) s(795) =< aux(207) s(794) =< s(685) s(795) =< s(685) s(1736) =< aux(209) s(1570) =< aux(215) s(1572) =< aux(207) s(1572) =< aux(214) s(1570) =< aux(214) s(1570) =< aux(207) s(1606) =< aux(209) s(1606) =< aux(207) s(1736) =< aux(207) s(1608) =< s(1606)*(1/2) s(1750) =< s(1736)*aux(214) s(1751) =< s(1750)*(1/2) s(1752) =< s(1750) s(1753) =< s(1750) s(1754) =< s(1750) s(1755) =< s(1750) s(1753) =< s(1751) s(1755) =< s(1751) s(1752) =< s(1606) s(1753) =< s(1606) s(1754) =< s(1606) s(1755) =< s(1606) s(1754) =< s(1608) s(1755) =< s(1608) s(1571) =< aux(211) s(1571) =< aux(214) s(1573) =< aux(214) s(1573) =< aux(215) s(1571) =< aux(207) s(1573) =< aux(207) s(1573) =< aux(211) s(1604) =< aux(213) s(1607) =< aux(209) s(1607) =< aux(207) s(1605) =< aux(211) s(1607) =< aux(211) s(1609) =< s(1605)*aux(214) s(1610) =< s(1609)*(1/2) s(1611) =< s(1609) s(1612) =< s(1609) s(1613) =< s(1609) s(1614) =< s(1609) s(1612) =< s(1610) s(1614) =< s(1610) s(1611) =< s(1606) s(1612) =< s(1606) s(1613) =< s(1606) s(1614) =< s(1606) s(1613) =< s(1608) s(1614) =< s(1608) s(1604) =< aux(207) s(1604) =< aux(211) s(1617) =< s(1604)*aux(214) s(1618) =< s(1617)*(1/2) s(1619) =< s(1617) s(1620) =< s(1617) s(1621) =< s(1617) s(1622) =< s(1617) s(1620) =< s(1618) s(1622) =< s(1618) s(1619) =< s(1606) s(1620) =< s(1606) s(1621) =< s(1606) s(1622) =< s(1606) s(1621) =< s(1608) s(1622) =< s(1608) s(1681) =< aux(214) s(1682) =< aux(214) s(1682) =< aux(215) s(1681) =< aux(209) s(1682) =< aux(209) s(2704) =< aux(217) s(2705) =< aux(211) s(2706) =< aux(216) s(2704) =< aux(216) s(2705) =< aux(216) s(2707) =< aux(216) s(2707) =< aux(217) s(2706) =< aux(207) s(2704) =< aux(207) s(2705) =< aux(207) s(2707) =< aux(207) s(2707) =< aux(211) s(3402) =< s(3401) s(3403) =< s(3401) s(3404) =< aux(210) s(3405) =< aux(210) s(3404) =< s(3397) s(3405) =< s(3397) s(3403) =< s(3399) s(3405) =< s(3399) s(3406) =< s(3404)*(1/2) s(3407) =< s(3403)*aux(207) s(3408) =< s(3407)*(1/2) s(3409) =< s(3407) s(3410) =< s(3407) s(3411) =< s(3407) s(3412) =< s(3407) s(3410) =< s(3408) s(3412) =< s(3408) s(3409) =< s(3404) s(3410) =< s(3404) s(3411) =< s(3404) s(3412) =< s(3404) s(3411) =< s(3406) s(3412) =< s(3406) s(3413) =< aux(207) s(3414) =< aux(207) s(3414) =< aux(211) s(3413) =< s(3397) s(3414) =< s(3397) s(3402) =< s(3397) s(3402) =< s(3399) s(3415) =< s(3402)*aux(207) s(3416) =< s(3415)*(1/2) s(3417) =< s(3415) s(3418) =< s(3415) s(3419) =< s(3415) s(3420) =< s(3415) s(3418) =< s(3416) s(3420) =< s(3416) s(3417) =< s(3404) s(3418) =< s(3404) s(3419) =< s(3404) s(3420) =< s(3404) s(3419) =< s(3406) s(3420) =< s(3406) s(3442) =< aux(210) s(3443) =< aux(210) s(3442) =< aux(214) s(3443) =< aux(214) s(3431) =< aux(215) s(3443) =< aux(215) s(3444) =< s(3442)*(1/2) s(3445) =< s(3431)*aux(207) s(3446) =< s(3445)*(1/2) s(3447) =< s(3445) s(3448) =< s(3445) s(3449) =< s(3445) s(3450) =< s(3445) s(3448) =< s(3446) s(3450) =< s(3446) s(3447) =< s(3442) s(3448) =< s(3442) s(3449) =< s(3442) s(3450) =< s(3442) s(3449) =< s(3444) s(3450) =< s(3444) s(3008) =< aux(217) s(3009) =< aux(212) s(3010) =< aux(216) s(3008) =< aux(216) s(3009) =< aux(216) s(3011) =< aux(216) s(3011) =< aux(217) s(3010) =< aux(208) s(3008) =< aux(208) s(3009) =< aux(208) s(3011) =< aux(208) s(3011) =< aux(212) with precondition: [V1>=0] * Chain [142]: 1 with precondition: [V1=0,V>=1] * Chain [141]: 6*s(3653)+6*s(3654)+42*s(3658)+56*s(3659)+56*s(3660)+42*s(3661)+1568*s(3666)+1302*s(3667)+2394*s(3668)+756*s(3669)+6*s(3676)+6*s(3677)+12*s(3679)+42*s(3683)+56*s(3684)+56*s(3685)+42*s(3686)+98*s(3687)+98*s(3688)+42*s(3691)+56*s(3692)+56*s(3693)+42*s(3694)+6*s(3705)+6*s(3717)+42*s(3721)+56*s(3722)+56*s(3723)+42*s(3724)+6*s(3728)+6*s(3729)+42*s(3733)+56*s(3734)+56*s(3735)+42*s(3736)+13 Such that:s(3726) =< V+2 s(3727) =< V/2+1 s(3705) =< V/2+V17/2 s(3675) =< V/2+V17/2+1/2 s(3671) =< V17+1 s(3651) =< V17+2 s(3652) =< V17/2+1 s(3673) =< V17/2+1/2 aux(220) =< 1 aux(221) =< V aux(222) =< V+V17+1 aux(223) =< V/2 aux(224) =< V17 aux(225) =< V17/2 s(3653) =< s(3652) s(3654) =< s(3651) s(3654) =< s(3652) s(3655) =< s(3651)*(1/2) s(3656) =< s(3653)*aux(220) s(3657) =< s(3656)*(1/2) s(3658) =< s(3656) s(3659) =< s(3656) s(3660) =< s(3656) s(3661) =< s(3656) s(3659) =< s(3657) s(3661) =< s(3657) s(3658) =< s(3651) s(3659) =< s(3651) s(3660) =< s(3651) s(3661) =< s(3651) s(3660) =< s(3655) s(3661) =< s(3655) s(3728) =< s(3727) s(3729) =< s(3726) s(3729) =< s(3727) s(3730) =< s(3726)*(1/2) s(3731) =< s(3728)*aux(220) s(3732) =< s(3731)*(1/2) s(3733) =< s(3731) s(3734) =< s(3731) s(3735) =< s(3731) s(3736) =< s(3731) s(3734) =< s(3732) s(3736) =< s(3732) s(3733) =< s(3726) s(3734) =< s(3726) s(3735) =< s(3726) s(3736) =< s(3726) s(3735) =< s(3730) s(3736) =< s(3730) s(3666) =< aux(223) s(3667) =< aux(225) s(3668) =< aux(221) s(3666) =< aux(221) s(3667) =< aux(221) s(3669) =< aux(221) s(3669) =< aux(223) s(3668) =< aux(224) s(3666) =< aux(224) s(3667) =< aux(224) s(3669) =< aux(224) s(3669) =< aux(225) s(3676) =< s(3675) s(3677) =< s(3675) s(3678) =< aux(222) s(3679) =< aux(222) s(3678) =< s(3671) s(3679) =< s(3671) s(3677) =< s(3673) s(3679) =< s(3673) s(3680) =< s(3678)*(1/2) s(3681) =< s(3677)*aux(221) s(3682) =< s(3681)*(1/2) s(3683) =< s(3681) s(3684) =< s(3681) s(3685) =< s(3681) s(3686) =< s(3681) s(3684) =< s(3682) s(3686) =< s(3682) s(3683) =< s(3678) s(3684) =< s(3678) s(3685) =< s(3678) s(3686) =< s(3678) s(3685) =< s(3680) s(3686) =< s(3680) s(3687) =< aux(221) s(3688) =< aux(221) s(3688) =< aux(223) s(3687) =< s(3671) s(3688) =< s(3671) s(3676) =< s(3671) s(3676) =< s(3673) s(3689) =< s(3676)*aux(221) s(3690) =< s(3689)*(1/2) s(3691) =< s(3689) s(3692) =< s(3689) s(3693) =< s(3689) s(3694) =< s(3689) s(3692) =< s(3690) s(3694) =< s(3690) s(3691) =< s(3678) s(3692) =< s(3678) s(3693) =< s(3678) s(3694) =< s(3678) s(3693) =< s(3680) s(3694) =< s(3680) s(3716) =< aux(222) s(3717) =< aux(222) s(3716) =< aux(224) s(3717) =< aux(224) s(3705) =< aux(225) s(3717) =< aux(225) s(3718) =< s(3716)*(1/2) s(3719) =< s(3705)*aux(221) s(3720) =< s(3719)*(1/2) s(3721) =< s(3719) s(3722) =< s(3719) s(3723) =< s(3719) s(3724) =< s(3719) s(3722) =< s(3720) s(3724) =< s(3720) s(3721) =< s(3716) s(3722) =< s(3716) s(3723) =< s(3716) s(3724) =< s(3716) s(3723) =< s(3718) s(3724) =< s(3718) with precondition: [V1=1] * Chain [140]: 8 with precondition: [V1=2] * Chain [139]: 329 with precondition: [V1=3] * Chain [138]: 6944*s(3753)+5880*s(3754)+10080*s(3755)+3528*s(3756)+15 Such that:aux(226) =< V1 aux(227) =< V1/2 aux(228) =< V15 aux(229) =< V15/2 s(3753) =< aux(229) s(3754) =< aux(227) s(3755) =< aux(228) s(3753) =< aux(228) s(3754) =< aux(228) s(3756) =< aux(228) s(3756) =< aux(229) s(3755) =< aux(226) s(3753) =< aux(226) s(3754) =< aux(226) s(3756) =< aux(226) s(3756) =< aux(227) with precondition: [V=0,V1>=1] * Chain [137]: 6*s(4008)+6*s(4009)+42*s(4013)+56*s(4014)+56*s(4015)+42*s(4016)+10 Such that:s(4005) =< 1 s(4006) =< V1 s(4007) =< V1/2 s(4008) =< s(4007) s(4009) =< s(4006) s(4009) =< s(4007) s(4010) =< s(4006)*(1/2) s(4011) =< s(4008)*s(4005) s(4012) =< s(4011)*(1/2) s(4013) =< s(4011) s(4014) =< s(4011) s(4015) =< s(4011) s(4016) =< s(4011) s(4014) =< s(4012) s(4016) =< s(4012) s(4013) =< s(4006) s(4014) =< s(4006) s(4015) =< s(4006) s(4016) =< s(4006) s(4015) =< s(4010) s(4016) =< s(4010) with precondition: [V=1,V1>=0] * Chain [136]: 9 with precondition: [V=2,V1>=2] * Chain [135]: 7 with precondition: [V15=1,V1>=1,V>=0] * Chain [134]: 8 with precondition: [V1=V+2,V1>=3,V15>=1] * Chain [133]: 1 with precondition: [V1=V,V1>=1] Closed-form bounds of start(V1,V,V15,V17): ------------------------------------- * Chain [143] with precondition: [V1>=0] - Upper bound: 170563*V1+5239/2+11552*V1*V1+nat(V)*15232+nat(V15)*33159+nat(V1+V)*1218+nat(V1+V+1)*606+nat(V1/2+V/2+1/2)*12+nat(V1/2+V/2)*36+nat(V1/2-V/2)*2205+20996*V1+nat(V/2)*27181+nat(V15/2)*17052 - Complexity: n^2 * Chain [142] with precondition: [V1=0,V>=1] - Upper bound: 1 - Complexity: constant * Chain [141] with precondition: [V1=1] - Upper bound: nat(V)*3346+13+nat(V+2)*6+nat(V17+2)*6+nat(V+V17+1)*606+nat(V/2+V17/2+1/2)*12+nat(V/2+1)*202+nat(V/2+V17/2)*6+nat(V17/2+1)*202+nat(V/2)*1568+nat(V17/2)*1302 - Complexity: n * Chain [140] with precondition: [V1=2] - Upper bound: 8 - Complexity: constant * Chain [139] with precondition: [V1=3] - Upper bound: 329 - Complexity: constant * Chain [138] with precondition: [V=0,V1>=1] - Upper bound: nat(V15)*13608+15+2940*V1+nat(V15/2)*6944 - Complexity: n * Chain [137] with precondition: [V=1,V1>=0] - Upper bound: 107*V1+10 - Complexity: n * Chain [136] with precondition: [V=2,V1>=2] - Upper bound: 9 - Complexity: constant * Chain [135] with precondition: [V15=1,V1>=1,V>=0] - Upper bound: 7 - Complexity: constant * Chain [134] with precondition: [V1=V+2,V1>=3,V15>=1] - Upper bound: 8 - Complexity: constant * Chain [133] with precondition: [V1=V,V1>=1] - Upper bound: 1 - Complexity: constant ### Maximum cost of start(V1,V,V15,V17): max([max([328,nat(V)*3346+12+nat(V+2)*6+nat(V17+2)*6+nat(V+V17+1)*606+nat(V/2+V17/2+1/2)*12+nat(V/2+1)*202+nat(V/2+V17/2)*6+nat(V17/2+1)*202+nat(V/2)*1568+nat(V17/2)*1302]),101*V1+9+max([nat(V15)*13608+5+2839*V1+nat(V15/2)*6944,170557*V1+5219/2+11552*V1*V1+nat(V)*15232+nat(V15)*33159+nat(V1+V)*1218+nat(V1+V+1)*606+nat(V1/2+V/2+1/2)*12+nat(V1/2+V/2)*36+nat(V1/2-V/2)*2205+20895*V1+nat(V/2)*27181+nat(V15/2)*17052+6*V1])])+1 Asymptotic class: n^2 * Total analysis performed in 26636 ms. ---------------------------------------- (12) BOUNDS(1, n^2) ---------------------------------------- (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (14) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) #less(@x, @y) -> #cklt(#compare(@x, @y)) and(@x, @y) -> #and(@x, @y) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) isortlist(@l) -> isortlist#1(@l) isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) isortlist#1(nil) -> nil leq(@l1, @l2) -> leq#1(@l1, @l2) leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) leq#1(nil, @l2) -> #true leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) leq#2(nil, @x, @xs) -> #false or(@x, @y) -> #or(@x, @y) The (relative) TRS S consists of the following rules: #and(#false, #false) -> #false #and(#false, #true) -> #false #and(#true, #false) -> #false #and(#true, #true) -> #true #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) #eq(#0, #0) -> #true #eq(#0, #neg(@y)) -> #false #eq(#0, #pos(@y)) -> #false #eq(#0, #s(@y)) -> #false #eq(#neg(@x), #0) -> #false #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) #eq(#neg(@x), #pos(@y)) -> #false #eq(#pos(@x), #0) -> #false #eq(#pos(@x), #neg(@y)) -> #false #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) #eq(#s(@x), #0) -> #false #eq(#s(@x), #s(@y)) -> #eq(@x, @y) #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) #eq(::(@x_1, @x_2), nil) -> #false #eq(nil, ::(@y_1, @y_2)) -> #false #eq(nil, nil) -> #true #or(#false, #false) -> #false #or(#false, #true) -> #true #or(#true, #false) -> #true #or(#true, #true) -> #true Rewrite Strategy: INNERMOST ---------------------------------------- (15) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence isortlist(::(@x1_0, @xs2_0)) ->^+ insert(@x1_0, isortlist(@xs2_0)) gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. The pumping substitution is [@xs2_0 / ::(@x1_0, @xs2_0)]. The result substitution is [ ]. ---------------------------------------- (16) Complex Obligation (BEST) ---------------------------------------- (17) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) #less(@x, @y) -> #cklt(#compare(@x, @y)) and(@x, @y) -> #and(@x, @y) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) isortlist(@l) -> isortlist#1(@l) isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) isortlist#1(nil) -> nil leq(@l1, @l2) -> leq#1(@l1, @l2) leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) leq#1(nil, @l2) -> #true leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) leq#2(nil, @x, @xs) -> #false or(@x, @y) -> #or(@x, @y) The (relative) TRS S consists of the following rules: #and(#false, #false) -> #false #and(#false, #true) -> #false #and(#true, #false) -> #false #and(#true, #true) -> #true #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) #eq(#0, #0) -> #true #eq(#0, #neg(@y)) -> #false #eq(#0, #pos(@y)) -> #false #eq(#0, #s(@y)) -> #false #eq(#neg(@x), #0) -> #false #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) #eq(#neg(@x), #pos(@y)) -> #false #eq(#pos(@x), #0) -> #false #eq(#pos(@x), #neg(@y)) -> #false #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) #eq(#s(@x), #0) -> #false #eq(#s(@x), #s(@y)) -> #eq(@x, @y) #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) #eq(::(@x_1, @x_2), nil) -> #false #eq(nil, ::(@y_1, @y_2)) -> #false #eq(nil, nil) -> #true #or(#false, #false) -> #false #or(#false, #true) -> #true #or(#true, #false) -> #true #or(#true, #true) -> #true Rewrite Strategy: INNERMOST ---------------------------------------- (18) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (19) BOUNDS(n^1, INF) ---------------------------------------- (20) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #equal(@x, @y) -> #eq(@x, @y) #less(@x, @y) -> #cklt(#compare(@x, @y)) and(@x, @y) -> #and(@x, @y) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(leq(@x, @y), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) isortlist(@l) -> isortlist#1(@l) isortlist#1(::(@x, @xs)) -> insert(@x, isortlist(@xs)) isortlist#1(nil) -> nil leq(@l1, @l2) -> leq#1(@l1, @l2) leq#1(::(@x, @xs), @l2) -> leq#2(@l2, @x, @xs) leq#1(nil, @l2) -> #true leq#2(::(@y, @ys), @x, @xs) -> or(#less(@x, @y), and(#equal(@x, @y), leq(@xs, @ys))) leq#2(nil, @x, @xs) -> #false or(@x, @y) -> #or(@x, @y) The (relative) TRS S consists of the following rules: #and(#false, #false) -> #false #and(#false, #true) -> #false #and(#true, #false) -> #false #and(#true, #true) -> #true #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) #eq(#0, #0) -> #true #eq(#0, #neg(@y)) -> #false #eq(#0, #pos(@y)) -> #false #eq(#0, #s(@y)) -> #false #eq(#neg(@x), #0) -> #false #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) #eq(#neg(@x), #pos(@y)) -> #false #eq(#pos(@x), #0) -> #false #eq(#pos(@x), #neg(@y)) -> #false #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) #eq(#s(@x), #0) -> #false #eq(#s(@x), #s(@y)) -> #eq(@x, @y) #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) #eq(::(@x_1, @x_2), nil) -> #false #eq(nil, ::(@y_1, @y_2)) -> #false #eq(nil, nil) -> #true #or(#false, #false) -> #false #or(#false, #true) -> #true #or(#true, #false) -> #true #or(#true, #true) -> #true Rewrite Strategy: INNERMOST