404.78/291.70 WORST_CASE(Omega(n^1), O(n^2)) 404.78/291.71 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 404.78/291.71 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 404.78/291.71 404.78/291.71 404.78/291.71 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 404.78/291.71 404.78/291.71 (0) CpxRelTRS 404.78/291.71 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 191 ms] 404.78/291.71 (2) CpxRelTRS 404.78/291.71 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 404.78/291.71 (4) CpxWeightedTrs 404.78/291.71 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 404.78/291.71 (6) CpxTypedWeightedTrs 404.78/291.71 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 404.78/291.71 (8) CpxTypedWeightedCompleteTrs 404.78/291.71 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 20 ms] 404.78/291.71 (10) CpxRNTS 404.78/291.71 (11) CompleteCoflocoProof [FINISHED, 3902 ms] 404.78/291.71 (12) BOUNDS(1, n^2) 404.78/291.71 (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 404.78/291.71 (14) CpxRelTRS 404.78/291.71 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 404.78/291.71 (16) typed CpxTrs 404.78/291.71 (17) OrderProof [LOWER BOUND(ID), 0 ms] 404.78/291.71 (18) typed CpxTrs 404.78/291.71 (19) RewriteLemmaProof [LOWER BOUND(ID), 25.6 s] 404.78/291.71 (20) typed CpxTrs 404.78/291.71 (21) RewriteLemmaProof [LOWER BOUND(ID), 30 ms] 404.78/291.71 (22) BEST 404.78/291.71 (23) proven lower bound 404.78/291.71 (24) LowerBoundPropagationProof [FINISHED, 0 ms] 404.78/291.71 (25) BOUNDS(n^1, INF) 404.78/291.71 (26) typed CpxTrs 404.78/291.71 (27) RewriteLemmaProof [LOWER BOUND(ID), 82 ms] 404.78/291.71 (28) typed CpxTrs 404.78/291.71 404.78/291.71 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (0) 404.78/291.71 Obligation: 404.78/291.71 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 404.78/291.71 404.78/291.71 404.78/291.71 The TRS R consists of the following rules: 404.78/291.71 404.78/291.71 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.71 and(@x, @y) -> #and(@x, @y) 404.78/291.71 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.71 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.71 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.71 eq#2(::(@y, @ys)) -> #false 404.78/291.71 eq#2(nil) -> #true 404.78/291.71 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.71 eq#3(nil, @x, @xs) -> #false 404.78/291.71 nub(@l) -> nub#1(@l) 404.78/291.71 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.71 nub#1(nil) -> nil 404.78/291.71 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.71 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.71 remove#1(nil, @x) -> nil 404.78/291.71 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.71 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.71 404.78/291.71 The (relative) TRS S consists of the following rules: 404.78/291.71 404.78/291.71 #and(#false, #false) -> #false 404.78/291.71 #and(#false, #true) -> #false 404.78/291.71 #and(#true, #false) -> #false 404.78/291.71 #and(#true, #true) -> #true 404.78/291.71 #eq(#0, #0) -> #true 404.78/291.71 #eq(#0, #neg(@y)) -> #false 404.78/291.71 #eq(#0, #pos(@y)) -> #false 404.78/291.71 #eq(#0, #s(@y)) -> #false 404.78/291.71 #eq(#neg(@x), #0) -> #false 404.78/291.71 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.71 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.71 #eq(#pos(@x), #0) -> #false 404.78/291.71 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.71 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.71 #eq(#s(@x), #0) -> #false 404.78/291.71 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.71 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.71 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.71 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.71 #eq(nil, nil) -> #true 404.78/291.71 404.78/291.71 Rewrite Strategy: INNERMOST 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 404.78/291.71 proved termination of relative rules 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (2) 404.78/291.71 Obligation: 404.78/291.71 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 404.78/291.71 404.78/291.71 404.78/291.71 The TRS R consists of the following rules: 404.78/291.71 404.78/291.71 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.71 and(@x, @y) -> #and(@x, @y) 404.78/291.71 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.71 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.71 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.71 eq#2(::(@y, @ys)) -> #false 404.78/291.71 eq#2(nil) -> #true 404.78/291.71 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.71 eq#3(nil, @x, @xs) -> #false 404.78/291.71 nub(@l) -> nub#1(@l) 404.78/291.71 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.71 nub#1(nil) -> nil 404.78/291.71 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.71 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.71 remove#1(nil, @x) -> nil 404.78/291.71 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.71 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.71 404.78/291.71 The (relative) TRS S consists of the following rules: 404.78/291.71 404.78/291.71 #and(#false, #false) -> #false 404.78/291.71 #and(#false, #true) -> #false 404.78/291.71 #and(#true, #false) -> #false 404.78/291.71 #and(#true, #true) -> #true 404.78/291.71 #eq(#0, #0) -> #true 404.78/291.71 #eq(#0, #neg(@y)) -> #false 404.78/291.71 #eq(#0, #pos(@y)) -> #false 404.78/291.71 #eq(#0, #s(@y)) -> #false 404.78/291.71 #eq(#neg(@x), #0) -> #false 404.78/291.71 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.71 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.71 #eq(#pos(@x), #0) -> #false 404.78/291.71 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.71 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.71 #eq(#s(@x), #0) -> #false 404.78/291.71 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.71 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.71 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.71 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.71 #eq(nil, nil) -> #true 404.78/291.71 404.78/291.71 Rewrite Strategy: INNERMOST 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 404.78/291.71 Transformed relative TRS to weighted TRS 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (4) 404.78/291.71 Obligation: 404.78/291.71 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 404.78/291.71 404.78/291.71 404.78/291.71 The TRS R consists of the following rules: 404.78/291.71 404.78/291.71 #equal(@x, @y) -> #eq(@x, @y) [1] 404.78/291.71 and(@x, @y) -> #and(@x, @y) [1] 404.78/291.71 eq(@l1, @l2) -> eq#1(@l1, @l2) [1] 404.78/291.71 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) [1] 404.78/291.71 eq#1(nil, @l2) -> eq#2(@l2) [1] 404.78/291.71 eq#2(::(@y, @ys)) -> #false [1] 404.78/291.71 eq#2(nil) -> #true [1] 404.78/291.71 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) [1] 404.78/291.71 eq#3(nil, @x, @xs) -> #false [1] 404.78/291.71 nub(@l) -> nub#1(@l) [1] 404.78/291.71 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) [1] 404.78/291.71 nub#1(nil) -> nil [1] 404.78/291.71 remove(@x, @l) -> remove#1(@l, @x) [1] 404.78/291.71 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) [1] 404.78/291.71 remove#1(nil, @x) -> nil [1] 404.78/291.71 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) [1] 404.78/291.71 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) [1] 404.78/291.71 #and(#false, #false) -> #false [0] 404.78/291.71 #and(#false, #true) -> #false [0] 404.78/291.71 #and(#true, #false) -> #false [0] 404.78/291.71 #and(#true, #true) -> #true [0] 404.78/291.71 #eq(#0, #0) -> #true [0] 404.78/291.71 #eq(#0, #neg(@y)) -> #false [0] 404.78/291.71 #eq(#0, #pos(@y)) -> #false [0] 404.78/291.71 #eq(#0, #s(@y)) -> #false [0] 404.78/291.71 #eq(#neg(@x), #0) -> #false [0] 404.78/291.71 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(#neg(@x), #pos(@y)) -> #false [0] 404.78/291.71 #eq(#pos(@x), #0) -> #false [0] 404.78/291.71 #eq(#pos(@x), #neg(@y)) -> #false [0] 404.78/291.71 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(#s(@x), #0) -> #false [0] 404.78/291.71 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) [0] 404.78/291.71 #eq(::(@x_1, @x_2), nil) -> #false [0] 404.78/291.71 #eq(nil, ::(@y_1, @y_2)) -> #false [0] 404.78/291.71 #eq(nil, nil) -> #true [0] 404.78/291.71 404.78/291.71 Rewrite Strategy: INNERMOST 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 404.78/291.71 Infered types. 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (6) 404.78/291.71 Obligation: 404.78/291.71 Runtime Complexity Weighted TRS with Types. 404.78/291.71 The TRS R consists of the following rules: 404.78/291.71 404.78/291.71 #equal(@x, @y) -> #eq(@x, @y) [1] 404.78/291.71 and(@x, @y) -> #and(@x, @y) [1] 404.78/291.71 eq(@l1, @l2) -> eq#1(@l1, @l2) [1] 404.78/291.71 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) [1] 404.78/291.71 eq#1(nil, @l2) -> eq#2(@l2) [1] 404.78/291.71 eq#2(::(@y, @ys)) -> #false [1] 404.78/291.71 eq#2(nil) -> #true [1] 404.78/291.71 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) [1] 404.78/291.71 eq#3(nil, @x, @xs) -> #false [1] 404.78/291.71 nub(@l) -> nub#1(@l) [1] 404.78/291.71 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) [1] 404.78/291.71 nub#1(nil) -> nil [1] 404.78/291.71 remove(@x, @l) -> remove#1(@l, @x) [1] 404.78/291.71 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) [1] 404.78/291.71 remove#1(nil, @x) -> nil [1] 404.78/291.71 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) [1] 404.78/291.71 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) [1] 404.78/291.71 #and(#false, #false) -> #false [0] 404.78/291.71 #and(#false, #true) -> #false [0] 404.78/291.71 #and(#true, #false) -> #false [0] 404.78/291.71 #and(#true, #true) -> #true [0] 404.78/291.71 #eq(#0, #0) -> #true [0] 404.78/291.71 #eq(#0, #neg(@y)) -> #false [0] 404.78/291.71 #eq(#0, #pos(@y)) -> #false [0] 404.78/291.71 #eq(#0, #s(@y)) -> #false [0] 404.78/291.71 #eq(#neg(@x), #0) -> #false [0] 404.78/291.71 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(#neg(@x), #pos(@y)) -> #false [0] 404.78/291.71 #eq(#pos(@x), #0) -> #false [0] 404.78/291.71 #eq(#pos(@x), #neg(@y)) -> #false [0] 404.78/291.71 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(#s(@x), #0) -> #false [0] 404.78/291.71 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) [0] 404.78/291.71 #eq(::(@x_1, @x_2), nil) -> #false [0] 404.78/291.71 #eq(nil, ::(@y_1, @y_2)) -> #false [0] 404.78/291.71 #eq(nil, nil) -> #true [0] 404.78/291.71 404.78/291.71 The TRS has the following type information: 404.78/291.71 #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.71 #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.71 and :: #false:#true -> #false:#true -> #false:#true 404.78/291.71 #and :: #false:#true -> #false:#true -> #false:#true 404.78/291.71 eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.71 eq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.71 :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 eq#3 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.71 nil :: :::nil:#0:#neg:#pos:#s 404.78/291.71 eq#2 :: :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.71 #false :: #false:#true 404.78/291.71 #true :: #false:#true 404.78/291.71 nub :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 nub#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 remove :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 remove#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 remove#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 #0 :: :::nil:#0:#neg:#pos:#s 404.78/291.71 #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.71 404.78/291.71 Rewrite Strategy: INNERMOST 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (7) CompletionProof (UPPER BOUND(ID)) 404.78/291.71 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 404.78/291.71 404.78/291.71 #and(v0, v1) -> null_#and [0] 404.78/291.71 #eq(v0, v1) -> null_#eq [0] 404.78/291.71 eq#1(v0, v1) -> null_eq#1 [0] 404.78/291.71 eq#2(v0) -> null_eq#2 [0] 404.78/291.71 eq#3(v0, v1, v2) -> null_eq#3 [0] 404.78/291.71 nub#1(v0) -> null_nub#1 [0] 404.78/291.71 remove#1(v0, v1) -> null_remove#1 [0] 404.78/291.71 remove#2(v0, v1, v2, v3) -> null_remove#2 [0] 404.78/291.71 404.78/291.71 And the following fresh constants: null_#and, null_#eq, null_eq#1, null_eq#2, null_eq#3, null_nub#1, null_remove#1, null_remove#2 404.78/291.71 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (8) 404.78/291.71 Obligation: 404.78/291.71 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 404.78/291.71 404.78/291.71 Runtime Complexity Weighted TRS with Types. 404.78/291.71 The TRS R consists of the following rules: 404.78/291.71 404.78/291.71 #equal(@x, @y) -> #eq(@x, @y) [1] 404.78/291.71 and(@x, @y) -> #and(@x, @y) [1] 404.78/291.71 eq(@l1, @l2) -> eq#1(@l1, @l2) [1] 404.78/291.71 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) [1] 404.78/291.71 eq#1(nil, @l2) -> eq#2(@l2) [1] 404.78/291.71 eq#2(::(@y, @ys)) -> #false [1] 404.78/291.71 eq#2(nil) -> #true [1] 404.78/291.71 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) [1] 404.78/291.71 eq#3(nil, @x, @xs) -> #false [1] 404.78/291.71 nub(@l) -> nub#1(@l) [1] 404.78/291.71 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) [1] 404.78/291.71 nub#1(nil) -> nil [1] 404.78/291.71 remove(@x, @l) -> remove#1(@l, @x) [1] 404.78/291.71 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) [1] 404.78/291.71 remove#1(nil, @x) -> nil [1] 404.78/291.71 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) [1] 404.78/291.71 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) [1] 404.78/291.71 #and(#false, #false) -> #false [0] 404.78/291.71 #and(#false, #true) -> #false [0] 404.78/291.71 #and(#true, #false) -> #false [0] 404.78/291.71 #and(#true, #true) -> #true [0] 404.78/291.71 #eq(#0, #0) -> #true [0] 404.78/291.71 #eq(#0, #neg(@y)) -> #false [0] 404.78/291.71 #eq(#0, #pos(@y)) -> #false [0] 404.78/291.71 #eq(#0, #s(@y)) -> #false [0] 404.78/291.71 #eq(#neg(@x), #0) -> #false [0] 404.78/291.71 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(#neg(@x), #pos(@y)) -> #false [0] 404.78/291.71 #eq(#pos(@x), #0) -> #false [0] 404.78/291.71 #eq(#pos(@x), #neg(@y)) -> #false [0] 404.78/291.71 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(#s(@x), #0) -> #false [0] 404.78/291.71 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) [0] 404.78/291.71 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) [0] 404.78/291.71 #eq(::(@x_1, @x_2), nil) -> #false [0] 404.78/291.71 #eq(nil, ::(@y_1, @y_2)) -> #false [0] 404.78/291.71 #eq(nil, nil) -> #true [0] 404.78/291.71 #and(v0, v1) -> null_#and [0] 404.78/291.71 #eq(v0, v1) -> null_#eq [0] 404.78/291.71 eq#1(v0, v1) -> null_eq#1 [0] 404.78/291.71 eq#2(v0) -> null_eq#2 [0] 404.78/291.71 eq#3(v0, v1, v2) -> null_eq#3 [0] 404.78/291.71 nub#1(v0) -> null_nub#1 [0] 404.78/291.71 remove#1(v0, v1) -> null_remove#1 [0] 404.78/291.71 remove#2(v0, v1, v2, v3) -> null_remove#2 [0] 404.78/291.71 404.78/291.71 The TRS has the following type information: 404.78/291.71 #equal :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 #eq :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 and :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 #and :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 eq :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 eq#1 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 :: :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 eq#3 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 nil :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 eq#2 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 #false :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 #true :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 nub :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 nub#1 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 remove :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 remove#1 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 remove#2 :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 #0 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 #neg :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 #pos :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 #s :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 -> :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 null_#and :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 null_#eq :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 null_eq#1 :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 null_eq#2 :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 null_eq#3 :: #false:#true:null_#and:null_#eq:null_eq#1:null_eq#2:null_eq#3 404.78/291.71 null_nub#1 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 null_remove#1 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 null_remove#2 :: :::nil:#0:#neg:#pos:#s:null_nub#1:null_remove#1:null_remove#2 404.78/291.71 404.78/291.71 Rewrite Strategy: INNERMOST 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 404.78/291.71 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 404.78/291.71 The constant constructors are abstracted as follows: 404.78/291.71 404.78/291.71 nil => 1 404.78/291.71 #false => 1 404.78/291.71 #true => 2 404.78/291.71 #0 => 0 404.78/291.71 null_#and => 0 404.78/291.71 null_#eq => 0 404.78/291.71 null_eq#1 => 0 404.78/291.71 null_eq#2 => 0 404.78/291.71 null_eq#3 => 0 404.78/291.71 null_nub#1 => 0 404.78/291.71 null_remove#1 => 0 404.78/291.71 null_remove#2 => 0 404.78/291.71 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (10) 404.78/291.71 Obligation: 404.78/291.71 Complexity RNTS consisting of the following rules: 404.78/291.71 404.78/291.71 #and(z, z') -{ 0 }-> 2 :|: z = 2, z' = 2 404.78/291.71 #and(z, z') -{ 0 }-> 1 :|: z = 1, z' = 1 404.78/291.71 #and(z, z') -{ 0 }-> 1 :|: z' = 2, z = 1 404.78/291.71 #and(z, z') -{ 0 }-> 1 :|: z = 2, z' = 1 404.78/291.71 #and(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 404.78/291.71 #eq(z, z') -{ 0 }-> 2 :|: z = 0, z' = 0 404.78/291.71 #eq(z, z') -{ 0 }-> 2 :|: z = 1, z' = 1 404.78/291.71 #eq(z, z') -{ 0 }-> 1 :|: z = 0, z' = 1 + @y, @y >= 0 404.78/291.71 #eq(z, z') -{ 0 }-> 1 :|: @x >= 0, z = 1 + @x, z' = 0 404.78/291.71 #eq(z, z') -{ 0 }-> 1 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 404.78/291.71 #eq(z, z') -{ 0 }-> 1 :|: @x_1 >= 0, z = 1 + @x_1 + @x_2, @x_2 >= 0, z' = 1 404.78/291.71 #eq(z, z') -{ 0 }-> 1 :|: z = 1, @y_1 >= 0, @y_2 >= 0, z' = 1 + @y_1 + @y_2 404.78/291.71 #eq(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 404.78/291.71 #eq(z, z') -{ 0 }-> #eq(@x, @y) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 404.78/291.71 #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 404.78/291.71 #equal(z, z') -{ 1 }-> #eq(@x, @y) :|: z = @x, @x >= 0, z' = @y, @y >= 0 404.78/291.71 and(z, z') -{ 1 }-> #and(@x, @y) :|: z = @x, @x >= 0, z' = @y, @y >= 0 404.78/291.71 eq(z, z') -{ 1 }-> eq#1(@l1, @l2) :|: @l1 >= 0, z' = @l2, @l2 >= 0, z = @l1 404.78/291.71 eq#1(z, z') -{ 1 }-> eq#3(@l2, @x, @xs) :|: z' = @l2, @x >= 0, z = 1 + @x + @xs, @l2 >= 0, @xs >= 0 404.78/291.71 eq#1(z, z') -{ 1 }-> eq#2(@l2) :|: z' = @l2, z = 1, @l2 >= 0 404.78/291.71 eq#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 404.78/291.71 eq#2(z) -{ 1 }-> 2 :|: z = 1 404.78/291.71 eq#2(z) -{ 1 }-> 1 :|: z = 1 + @y + @ys, @y >= 0, @ys >= 0 404.78/291.71 eq#2(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 404.78/291.71 eq#3(z, z', z'') -{ 1 }-> and(#equal(@x, @y), eq(@xs, @ys)) :|: z = 1 + @y + @ys, @x >= 0, @xs >= 0, @y >= 0, z' = @x, z'' = @xs, @ys >= 0 404.78/291.71 eq#3(z, z', z'') -{ 1 }-> 1 :|: @x >= 0, z = 1, @xs >= 0, z' = @x, z'' = @xs 404.78/291.71 eq#3(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 404.78/291.71 nub(z) -{ 1 }-> nub#1(@l) :|: z = @l, @l >= 0 404.78/291.71 nub#1(z) -{ 1 }-> 1 :|: z = 1 404.78/291.71 nub#1(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 404.78/291.71 nub#1(z) -{ 1 }-> 1 + @x + nub(remove(@x, @xs)) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 404.78/291.71 remove(z, z') -{ 1 }-> remove#1(@l, @x) :|: z = @x, @l >= 0, @x >= 0, z' = @l 404.78/291.71 remove#1(z, z') -{ 1 }-> remove#2(eq(@x, @y), @x, @y, @ys) :|: z = 1 + @y + @ys, @x >= 0, @y >= 0, z' = @x, @ys >= 0 404.78/291.71 remove#1(z, z') -{ 1 }-> 1 :|: @x >= 0, z = 1, z' = @x 404.78/291.71 remove#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 404.78/291.71 remove#2(z, z', z'', z1) -{ 1 }-> remove(@x, @ys) :|: z = 2, @x >= 0, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 404.78/291.71 remove#2(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 404.78/291.71 remove#2(z, z', z'', z1) -{ 1 }-> 1 + @y + remove(@x, @ys) :|: @x >= 0, z = 1, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y 404.78/291.71 404.78/291.71 Only complete derivations are relevant for the runtime complexity. 404.78/291.71 404.78/291.71 ---------------------------------------- 404.78/291.71 404.78/291.71 (11) CompleteCoflocoProof (FINISHED) 404.78/291.71 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 404.78/291.71 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[and(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[eq(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun5(V1, Out)],[V1 >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun4(V1, V, V16, Out)],[V1 >= 0,V >= 0,V16 >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[nub(V1, Out)],[V1 >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun6(V1, Out)],[V1 >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[remove(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun7(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun8(V1, V, V16, V33, Out)],[V1 >= 0,V >= 0,V16 >= 0,V33 >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(start(V1, V, V16, V33),0,[fun1(V1, V, Out)],[V1 >= 0,V >= 0]). 404.78/291.71 eq(fun(V1, V, Out),1,[fun1(V2, V3, Ret)],[Out = Ret,V1 = V2,V2 >= 0,V = V3,V3 >= 0]). 404.78/291.71 eq(and(V1, V, Out),1,[fun2(V4, V5, Ret1)],[Out = Ret1,V1 = V4,V4 >= 0,V = V5,V5 >= 0]). 404.78/291.71 eq(eq(V1, V, Out),1,[fun3(V7, V6, Ret2)],[Out = Ret2,V7 >= 0,V = V6,V6 >= 0,V1 = V7]). 404.78/291.71 eq(fun3(V1, V, Out),1,[fun4(V9, V8, V10, Ret3)],[Out = Ret3,V = V9,V8 >= 0,V1 = 1 + V10 + V8,V9 >= 0,V10 >= 0]). 404.78/291.71 eq(fun3(V1, V, Out),1,[fun5(V11, Ret4)],[Out = Ret4,V = V11,V1 = 1,V11 >= 0]). 404.78/291.71 eq(fun5(V1, Out),1,[],[Out = 1,V1 = 1 + V12 + V13,V12 >= 0,V13 >= 0]). 404.78/291.71 eq(fun5(V1, Out),1,[],[Out = 2,V1 = 1]). 404.78/291.71 eq(fun4(V1, V, V16, Out),1,[fun(V14, V15, Ret0),eq(V17, V18, Ret11),and(Ret0, Ret11, Ret5)],[Out = Ret5,V1 = 1 + V15 + V18,V14 >= 0,V17 >= 0,V15 >= 0,V = V14,V16 = V17,V18 >= 0]). 404.78/291.71 eq(fun4(V1, V, V16, Out),1,[],[Out = 1,V19 >= 0,V1 = 1,V20 >= 0,V = V19,V16 = V20]). 404.78/291.71 eq(nub(V1, Out),1,[fun6(V21, Ret6)],[Out = Ret6,V1 = V21,V21 >= 0]). 404.78/291.71 eq(fun6(V1, Out),1,[remove(V22, V23, Ret10),nub(Ret10, Ret12)],[Out = 1 + Ret12 + V22,V22 >= 0,V1 = 1 + V22 + V23,V23 >= 0]). 404.78/291.71 eq(fun6(V1, Out),1,[],[Out = 1,V1 = 1]). 404.78/291.71 eq(remove(V1, V, Out),1,[fun7(V25, V24, Ret7)],[Out = Ret7,V1 = V24,V25 >= 0,V24 >= 0,V = V25]). 404.78/291.71 eq(fun7(V1, V, Out),1,[eq(V27, V26, Ret01),fun8(Ret01, V27, V26, V28, Ret8)],[Out = Ret8,V1 = 1 + V26 + V28,V27 >= 0,V26 >= 0,V = V27,V28 >= 0]). 404.78/291.71 eq(fun7(V1, V, Out),1,[],[Out = 1,V29 >= 0,V1 = 1,V = V29]). 404.78/291.71 eq(fun8(V1, V, V16, V33, Out),1,[remove(V32, V31, Ret13)],[Out = 1 + Ret13 + V30,V32 >= 0,V1 = 1,V33 = V31,V30 >= 0,V = V32,V31 >= 0,V16 = V30]). 404.78/291.71 eq(fun8(V1, V, V16, V33, Out),1,[remove(V36, V34, Ret9)],[Out = Ret9,V1 = 2,V36 >= 0,V33 = V34,V35 >= 0,V = V36,V34 >= 0,V16 = V35]). 404.78/291.71 eq(fun2(V1, V, Out),0,[],[Out = 1,V1 = 1,V = 1]). 404.78/291.71 eq(fun2(V1, V, Out),0,[],[Out = 1,V = 2,V1 = 1]). 404.78/291.71 eq(fun2(V1, V, Out),0,[],[Out = 1,V1 = 2,V = 1]). 404.78/291.71 eq(fun2(V1, V, Out),0,[],[Out = 2,V1 = 2,V = 2]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 2,V1 = 0,V = 0]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 1,V1 = 0,V = 1 + V37,V37 >= 0]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 1,V38 >= 0,V1 = 1 + V38,V = 0]). 404.78/291.71 eq(fun1(V1, V, Out),0,[fun1(V39, V40, Ret14)],[Out = Ret14,V39 >= 0,V1 = 1 + V39,V = 1 + V40,V40 >= 0]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 1,V41 >= 0,V1 = 1 + V41,V = 1 + V42,V42 >= 0]). 404.78/291.71 eq(fun1(V1, V, Out),0,[fun1(V46, V44, Ret02),fun1(V45, V43, Ret15),fun2(Ret02, Ret15, Ret16)],[Out = Ret16,V46 >= 0,V1 = 1 + V45 + V46,V44 >= 0,V45 >= 0,V43 >= 0,V = 1 + V43 + V44]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 1,V48 >= 0,V1 = 1 + V47 + V48,V47 >= 0,V = 1]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 1,V1 = 1,V50 >= 0,V49 >= 0,V = 1 + V49 + V50]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 2,V1 = 1,V = 1]). 404.78/291.71 eq(fun2(V1, V, Out),0,[],[Out = 0,V52 >= 0,V51 >= 0,V1 = V52,V = V51]). 404.78/291.71 eq(fun1(V1, V, Out),0,[],[Out = 0,V54 >= 0,V53 >= 0,V1 = V54,V = V53]). 404.78/291.71 eq(fun3(V1, V, Out),0,[],[Out = 0,V56 >= 0,V55 >= 0,V1 = V56,V = V55]). 404.78/291.71 eq(fun5(V1, Out),0,[],[Out = 0,V57 >= 0,V1 = V57]). 404.78/291.71 eq(fun4(V1, V, V16, Out),0,[],[Out = 0,V58 >= 0,V16 = V60,V59 >= 0,V1 = V58,V = V59,V60 >= 0]). 404.78/291.71 eq(fun6(V1, Out),0,[],[Out = 0,V61 >= 0,V1 = V61]). 404.78/291.71 eq(fun7(V1, V, Out),0,[],[Out = 0,V63 >= 0,V62 >= 0,V1 = V63,V = V62]). 404.78/291.71 eq(fun8(V1, V, V16, V33, Out),0,[],[Out = 0,V33 = V67,V64 >= 0,V16 = V66,V65 >= 0,V1 = V64,V = V65,V66 >= 0,V67 >= 0]). 404.78/291.71 input_output_vars(fun(V1,V,Out),[V1,V],[Out]). 404.78/291.71 input_output_vars(and(V1,V,Out),[V1,V],[Out]). 404.78/291.71 input_output_vars(eq(V1,V,Out),[V1,V],[Out]). 404.78/291.71 input_output_vars(fun3(V1,V,Out),[V1,V],[Out]). 404.78/291.71 input_output_vars(fun5(V1,Out),[V1],[Out]). 404.78/291.71 input_output_vars(fun4(V1,V,V16,Out),[V1,V,V16],[Out]). 404.78/291.71 input_output_vars(nub(V1,Out),[V1],[Out]). 404.78/291.71 input_output_vars(fun6(V1,Out),[V1],[Out]). 404.78/291.71 input_output_vars(remove(V1,V,Out),[V1,V],[Out]). 404.78/291.71 input_output_vars(fun7(V1,V,Out),[V1,V],[Out]). 404.78/291.71 input_output_vars(fun8(V1,V,V16,V33,Out),[V1,V,V16,V33],[Out]). 404.78/291.71 input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). 404.78/291.71 input_output_vars(fun1(V1,V,Out),[V1,V],[Out]). 404.78/291.71 404.78/291.71 404.78/291.71 CoFloCo proof output: 404.78/291.71 Preprocessing Cost Relations 404.78/291.71 ===================================== 404.78/291.71 404.78/291.71 #### Computed strongly connected components 404.78/291.71 0. non_recursive : [fun2/3] 404.78/291.71 1. non_recursive : [and/3] 404.78/291.71 2. recursive [non_tail,multiple] : [fun1/3] 404.78/291.71 3. non_recursive : [fun/3] 404.78/291.71 4. non_recursive : [fun5/2] 404.78/291.71 5. recursive [non_tail] : [eq/3,fun3/3,fun4/4] 404.78/291.71 6. recursive : [fun7/3,fun8/5,remove/3] 404.78/291.71 7. recursive : [fun6/2,nub/2] 404.78/291.71 8. non_recursive : [start/4] 404.78/291.71 404.78/291.71 #### Obtained direct recursion through partial evaluation 404.78/291.71 0. SCC is partially evaluated into fun2/3 404.78/291.71 1. SCC is completely evaluated into other SCCs 404.78/291.71 2. SCC is partially evaluated into fun1/3 404.78/291.71 3. SCC is completely evaluated into other SCCs 404.78/291.71 4. SCC is partially evaluated into fun5/2 404.78/291.71 5. SCC is partially evaluated into eq/3 404.78/291.71 6. SCC is partially evaluated into remove/3 404.78/291.71 7. SCC is partially evaluated into nub/2 404.78/291.71 8. SCC is partially evaluated into start/4 404.78/291.71 404.78/291.71 Control-Flow Refinement of Cost Relations 404.78/291.71 ===================================== 404.78/291.71 404.78/291.71 ### Specialization of cost equations fun2/3 404.78/291.71 * CE 47 is refined into CE [51] 404.78/291.71 * CE 46 is refined into CE [52] 404.78/291.71 * CE 45 is refined into CE [53] 404.78/291.71 * CE 44 is refined into CE [54] 404.78/291.71 * CE 43 is refined into CE [55] 404.78/291.71 404.78/291.71 404.78/291.71 ### Cost equations --> "Loop" of fun2/3 404.78/291.71 * CEs [51] --> Loop 31 404.78/291.71 * CEs [52] --> Loop 32 404.78/291.71 * CEs [53] --> Loop 33 404.78/291.71 * CEs [54] --> Loop 34 404.78/291.71 * CEs [55] --> Loop 35 404.78/291.71 404.78/291.71 ### Ranking functions of CR fun2(V1,V,Out) 404.78/291.71 404.78/291.71 #### Partial ranking functions of CR fun2(V1,V,Out) 404.78/291.71 404.78/291.71 404.78/291.71 ### Specialization of cost equations fun1/3 404.78/291.71 * CE 39 is refined into CE [56] 404.78/291.71 * CE 42 is refined into CE [57] 404.78/291.71 * CE 37 is refined into CE [58] 404.78/291.71 * CE 41 is refined into CE [59] 404.78/291.71 * CE 36 is refined into CE [60] 404.78/291.71 * CE 35 is refined into CE [61] 404.78/291.71 * CE 40 is refined into CE [62,63,64,65,66] 404.78/291.71 * CE 38 is refined into CE [67] 404.78/291.71 404.78/291.71 404.78/291.71 ### Cost equations --> "Loop" of fun1/3 404.78/291.71 * CEs [67] --> Loop 36 404.78/291.71 * CEs [65] --> Loop 37 404.78/291.71 * CEs [64] --> Loop 38 404.78/291.71 * CEs [63] --> Loop 39 404.78/291.71 * CEs [62] --> Loop 40 404.78/291.71 * CEs [66] --> Loop 41 404.78/291.71 * CEs [56] --> Loop 42 404.78/291.71 * CEs [57] --> Loop 43 404.78/291.71 * CEs [58] --> Loop 44 404.78/291.71 * CEs [59] --> Loop 45 404.78/291.71 * CEs [60] --> Loop 46 404.78/291.71 * CEs [61] --> Loop 47 404.78/291.71 404.78/291.71 ### Ranking functions of CR fun1(V1,V,Out) 404.78/291.71 * RF of phase [36,37,38,39,40,41]: [V,V1] 404.78/291.71 404.78/291.71 #### Partial ranking functions of CR fun1(V1,V,Out) 404.78/291.71 * Partial RF of phase [36,37,38,39,40,41]: 404.78/291.71 - RF of loop [36:1,37:1,37:2,38:1,38:2,39:1,39:2,40:1,40:2,41:1,41:2]: 404.78/291.71 V 404.78/291.71 V1 404.78/291.71 404.78/291.71 404.78/291.71 ### Specialization of cost equations fun5/2 404.78/291.71 * CE 48 is refined into CE [68] 404.78/291.71 * CE 50 is refined into CE [69] 404.78/291.71 * CE 49 is refined into CE [70] 404.78/291.71 404.78/291.71 404.78/291.71 ### Cost equations --> "Loop" of fun5/2 404.78/291.71 * CEs [68] --> Loop 48 404.78/291.71 * CEs [69] --> Loop 49 404.78/291.71 * CEs [70] --> Loop 50 404.78/291.71 404.78/291.71 ### Ranking functions of CR fun5(V1,Out) 404.78/291.71 404.78/291.71 #### Partial ranking functions of CR fun5(V1,Out) 404.78/291.71 404.78/291.71 404.78/291.71 ### Specialization of cost equations eq/3 404.78/291.71 * CE 30 is refined into CE [71] 404.78/291.71 * CE 33 is refined into CE [72] 404.78/291.71 * CE 31 is refined into CE [73] 404.78/291.71 * CE 34 is refined into CE [74,75,76] 404.78/291.71 * CE 32 is refined into CE [77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94] 404.78/291.71 404.78/291.71 404.78/291.71 ### Cost equations --> "Loop" of eq/3 404.78/291.71 * CEs [86] --> Loop 51 404.78/291.71 * CEs [78] --> Loop 52 404.78/291.71 * CEs [84,93] --> Loop 53 404.78/291.71 * CEs [89] --> Loop 54 404.78/291.71 * CEs [81] --> Loop 55 404.78/291.71 * CEs [83,85,92] --> Loop 56 404.78/291.71 * CEs [88] --> Loop 57 404.78/291.71 * CEs [80] --> Loop 58 404.78/291.71 * CEs [77] --> Loop 59 404.78/291.71 * CEs [90] --> Loop 60 404.78/291.71 * CEs [82] --> Loop 61 404.78/291.71 * CEs [79,87,91,94] --> Loop 62 404.78/291.71 * CEs [73] --> Loop 63 404.78/291.71 * CEs [76] --> Loop 64 404.78/291.71 * CEs [71,72,75] --> Loop 65 404.78/291.71 * CEs [74] --> Loop 66 404.78/291.71 404.78/291.71 ### Ranking functions of CR eq(V1,V,Out) 404.78/291.71 * RF of phase [51,52]: [V,V1] 404.78/291.71 * RF of phase [56,57,58,59]: [V,V1] 404.78/291.71 * RF of phase [60,61,62]: [V,V1] 404.78/291.71 404.78/291.71 #### Partial ranking functions of CR eq(V1,V,Out) 404.78/291.71 * Partial RF of phase [51,52]: 404.78/291.71 - RF of loop [51:1]: 404.78/291.71 V-1 404.78/291.71 V1-1 404.78/291.71 - RF of loop [52:1]: 404.78/291.71 V 404.78/291.71 V1 404.78/291.71 * Partial RF of phase [56,57,58,59]: 404.78/291.71 - RF of loop [56:1]: 404.78/291.71 V-1 404.78/291.71 V1-1 404.78/291.71 - RF of loop [57:1]: 404.78/291.71 V1/2-1/2 404.78/291.71 - RF of loop [57:1,59:1]: 404.78/291.71 V 404.78/291.71 - RF of loop [58:1]: 404.78/291.71 V/2-1/2 404.78/291.71 - RF of loop [58:1,59:1]: 404.78/291.71 V1 404.78/291.71 * Partial RF of phase [60,61,62]: 404.78/291.71 - RF of loop [60:1]: 404.78/291.71 V1/2-1/2 404.78/291.71 - RF of loop [60:1,62:1]: 404.78/291.71 V 404.78/291.71 - RF of loop [61:1]: 404.78/291.71 V/2-1/2 404.78/291.71 - RF of loop [61:1,62:1]: 404.78/291.71 V1 404.78/291.71 404.78/291.71 404.78/291.71 ### Specialization of cost equations remove/3 404.78/291.71 * CE 22 is refined into CE [95,96,97,98,99,100,101] 404.78/291.71 * CE 25 is refined into CE [102] 404.78/291.71 * CE 26 is refined into CE [103] 404.78/291.71 * CE 24 is refined into CE [104,105,106,107] 404.78/291.71 * CE 23 is refined into CE [108,109] 404.78/291.71 404.78/291.71 404.78/291.71 ### Cost equations --> "Loop" of remove/3 404.78/291.71 * CEs [109] --> Loop 67 404.78/291.71 * CEs [106] --> Loop 68 404.78/291.71 * CEs [105,107] --> Loop 69 404.78/291.71 * CEs [104] --> Loop 70 404.78/291.71 * CEs [108] --> Loop 71 404.78/291.71 * CEs [103] --> Loop 72 404.78/291.71 * CEs [95,96,97,98,99,100,101,102] --> Loop 73 404.78/291.71 404.78/291.71 ### Ranking functions of CR remove(V1,V,Out) 404.78/291.71 * RF of phase [67,68,69,70,71]: [V/2-1/2] 404.78/291.71 404.78/291.71 #### Partial ranking functions of CR remove(V1,V,Out) 404.78/291.71 * Partial RF of phase [67,68,69,70,71]: 404.78/291.71 - RF of loop [67:1,69:1]: 404.78/291.71 V/3-2/3 404.78/291.71 - RF of loop [68:1,70:1,71:1]: 404.78/291.71 V/2-1/2 404.78/291.71 404.78/291.71 404.78/291.71 ### Specialization of cost equations nub/2 404.78/291.71 * CE 29 is refined into CE [110,111,112] 404.78/291.71 * CE 27 is refined into CE [113] 404.78/291.71 * CE 28 is refined into CE [114] 404.78/291.71 404.78/291.71 404.78/291.71 ### Cost equations --> "Loop" of nub/2 404.78/291.71 * CEs [113] --> Loop 74 404.78/291.71 * CEs [114] --> Loop 75 404.78/291.71 * CEs [112] --> Loop 76 404.78/291.71 * CEs [110] --> Loop 77 404.78/291.71 * CEs [111] --> Loop 78 404.78/291.71 404.78/291.71 ### Ranking functions of CR nub(V1,Out) 404.78/291.71 * RF of phase [76]: [V1-3] 404.78/291.71 404.78/291.71 #### Partial ranking functions of CR nub(V1,Out) 404.78/291.71 * Partial RF of phase [76]: 404.78/291.71 - RF of loop [76:1]: 404.78/291.71 V1-3 404.78/291.71 404.78/291.71 404.78/291.71 ### Specialization of cost equations start/4 404.78/291.71 * CE 10 is refined into CE [115] 404.78/291.71 * CE 6 is refined into CE [116,117,118] 404.78/291.71 * CE 1 is refined into CE [119] 404.78/291.71 * CE 2 is refined into CE [120] 404.78/291.71 * CE 3 is refined into CE [121,122,123,124,125,126,127,128] 404.78/291.71 * CE 4 is refined into CE [129,130,131,132,133,134,135] 404.78/291.71 * CE 5 is refined into CE [136,137,138,139,140,141] 404.78/291.71 * CE 7 is refined into CE [142,143,144,145,146,147,148,149,150,151,152,153] 404.78/291.71 * CE 8 is refined into CE [154,155,156] 404.78/291.71 * CE 9 is refined into CE [157] 404.78/291.71 * CE 11 is refined into CE [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,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235] 404.78/291.71 * CE 12 is refined into CE [236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,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] 404.78/291.71 * CE 13 is refined into CE [314,315,316] 404.78/291.71 * CE 14 is refined into CE [317,318,319,320,321,322] 404.78/291.71 * CE 15 is refined into CE [323,324,325,326,327] 404.78/291.71 * CE 16 is refined into CE [328,329,330,331,332,333,334] 404.78/291.71 * CE 17 is refined into CE [335,336,337] 404.78/291.71 * CE 18 is refined into CE [338,339,340,341,342] 404.78/291.71 * CE 19 is refined into CE [343,344,345] 404.78/291.71 * CE 20 is refined into CE [346,347,348,349,350] 404.78/291.71 * CE 21 is refined into CE [351,352,353,354,355,356] 404.78/291.71 404.78/291.71 404.78/291.71 ### Cost equations --> "Loop" of start/4 404.78/291.71 * CEs [166,167,211,212] --> Loop 79 404.78/291.71 * CEs [164,165,203,204,209,210,332] --> Loop 80 404.78/291.71 * CEs [238,239,249,250,251,252,262,263,264,265,266,267,283,284,294,295,301,302,303,304] --> Loop 81 404.78/291.71 * CEs [151] --> Loop 82 404.78/291.71 * CEs [136,148,289,290] --> Loop 83 404.78/291.71 * CEs [244,245] --> Loop 84 404.78/291.71 * CEs [116,117,118] --> Loop 85 404.78/291.71 * CEs [281,282,287,288] --> Loop 86 404.78/291.71 * CEs [158,159,160,161,171,172,173,174,326,349] --> Loop 87 404.78/291.71 * CEs [115,129,130,137,138,142,143,144,325,331,343,348] --> Loop 88 404.78/291.71 * CEs [236,237,240,241,242,243,246,247,248,253,254,255,256,257,258,259,260,261,320,354] --> Loop 89 404.78/291.71 * CEs [120,154,155,156,314,315,316,323,324,328,329,335,346,347] --> Loop 90 404.78/291.71 * CEs [318,352] --> Loop 91 404.78/291.71 * CEs [119,121,122,123,124,125,126,127,128,131,132,133,134,135,139,140,141,145,146,147,149,150,152,153,157,162,163,168,169,170,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,205,206,207,208,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,268,269,270,271,272,273,274,275,276,277,278,279,280,285,286,291,292,293,296,297,298,299,300,305,306,307,308,309,310,311,312,313,317,319,321,322,327,330,333,334,336,337,338,339,340,341,342,344,345,350,351,353,355,356] --> Loop 92 404.78/291.71 404.78/291.71 ### Ranking functions of CR start(V1,V,V16,V33) 404.78/291.71 404.78/291.71 #### Partial ranking functions of CR start(V1,V,V16,V33) 404.78/291.71 404.78/291.71 404.78/291.71 Computing Bounds 404.78/291.71 ===================================== 404.78/291.71 404.78/291.71 #### Cost of chains of fun2(V1,V,Out): 404.78/291.71 * Chain [35]: 0 404.78/291.71 with precondition: [V1=1,V=1,Out=1] 404.78/291.71 404.78/291.71 * Chain [34]: 0 404.78/291.71 with precondition: [V1=1,V=2,Out=1] 404.78/291.71 404.78/291.71 * Chain [33]: 0 404.78/291.71 with precondition: [V1=2,V=1,Out=1] 404.78/291.71 404.78/291.71 * Chain [32]: 0 404.78/291.71 with precondition: [V1=2,V=2,Out=2] 404.78/291.71 404.78/291.71 * Chain [31]: 0 404.78/291.71 with precondition: [Out=0,V1>=0,V>=0] 404.78/291.71 404.78/291.71 404.78/291.71 #### Cost of chains of fun1(V1,V,Out): 404.78/291.71 * Chain [47]: 0 404.78/291.71 with precondition: [V1=0,V=0,Out=2] 404.78/291.71 404.78/291.71 * Chain [46]: 0 404.78/291.71 with precondition: [V1=0,Out=1,V>=1] 404.78/291.71 404.78/291.71 * Chain [45]: 0 404.78/291.71 with precondition: [V1=1,V=1,Out=2] 404.78/291.71 404.78/291.71 * Chain [44]: 0 404.78/291.71 with precondition: [V=0,Out=1,V1>=1] 404.78/291.71 404.78/291.71 * Chain [43]: 0 404.78/291.71 with precondition: [Out=0,V1>=0,V>=0] 404.78/291.71 404.78/291.71 * Chain [42]: 0 404.78/291.71 with precondition: [Out=1,V1>=1,V>=1] 404.78/291.71 404.78/291.71 * Chain [multiple([36,37,38,39,40,41],[[47],[46],[45],[44],[43],[42]])]: 0 404.78/291.71 with precondition: [2>=Out,V1>=1,V>=1,Out>=0] 404.78/291.71 404.78/291.71 404.78/291.71 #### Cost of chains of fun5(V1,Out): 404.78/291.71 * Chain [50]: 1 404.78/291.71 with precondition: [V1=1,Out=2] 404.78/291.71 404.78/291.71 * Chain [49]: 0 404.78/291.71 with precondition: [Out=0,V1>=0] 404.78/291.71 404.78/291.71 * Chain [48]: 1 404.78/291.71 with precondition: [Out=1,V1>=1] 404.78/291.71 404.78/291.71 404.78/291.71 #### Cost of chains of eq(V1,V,Out): 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],64]: 30*it(56)+5*it(60)+3 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 aux(26) =< V1 404.78/291.71 aux(27) =< V 404.78/291.71 it(56) =< aux(26) 404.78/291.71 it(56) =< aux(27) 404.78/291.71 it(60) =< aux(26) 404.78/291.71 it(60) =< aux(27) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=3,V>=3] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],63]: 35*it(56)+3 404.78/291.71 Such that:aux(30) =< V1 404.78/291.71 aux(31) =< V 404.78/291.71 it(56) =< aux(30) 404.78/291.71 it(56) =< aux(31) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=3,V>=3] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],55,[51,52],66]: 45*it(51)+8 404.78/291.71 Such that:aux(40) =< V1 404.78/291.71 aux(41) =< V 404.78/291.71 it(51) =< aux(40) 404.78/291.71 it(51) =< aux(41) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=5,V>=6] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],55,66]: 35*it(56)+8 404.78/291.71 Such that:aux(44) =< V1 404.78/291.71 aux(45) =< V 404.78/291.71 it(56) =< aux(44) 404.78/291.71 it(56) =< aux(45) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=4,V>=5] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],54,[51,52],66]: 45*it(51)+8 404.78/291.71 Such that:aux(48) =< V1 404.78/291.71 aux(49) =< V 404.78/291.71 it(51) =< aux(48) 404.78/291.71 it(51) =< aux(49) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=6,V>=5] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],54,66]: 35*it(56)+8 404.78/291.71 Such that:aux(52) =< V1 404.78/291.71 aux(53) =< V 404.78/291.71 it(56) =< aux(52) 404.78/291.71 it(56) =< aux(53) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=5,V>=4] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],53,[51,52],66]: 45*it(51)+8 404.78/291.71 Such that:aux(56) =< V1 404.78/291.71 aux(57) =< V 404.78/291.71 it(51) =< aux(56) 404.78/291.71 it(51) =< aux(57) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=6,V>=6] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[56,57,58,59],53,66]: 35*it(56)+8 404.78/291.71 Such that:aux(60) =< V1 404.78/291.71 aux(61) =< V 404.78/291.71 it(56) =< aux(60) 404.78/291.71 it(56) =< aux(61) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=5,V>=5] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],[51,52],66]: 25*it(51)+3 404.78/291.71 Such that:aux(62) =< V1 404.78/291.71 aux(63) =< V 404.78/291.71 it(51) =< aux(62) 404.78/291.71 it(51) =< aux(63) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=3,V>=3] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],66]: 5*it(60)+5*it(61)+5*it(62)+3 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 it(61) =< V/2 404.78/291.71 aux(64) =< V1 404.78/291.71 aux(65) =< V 404.78/291.71 it(60) =< aux(64) 404.78/291.71 it(61) =< aux(64) 404.78/291.71 it(62) =< aux(64) 404.78/291.71 it(60) =< aux(65) 404.78/291.71 it(61) =< aux(65) 404.78/291.71 it(62) =< aux(65) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=2,V>=2] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],65]: 5*it(60)+5*it(61)+5*it(62)+2 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 it(61) =< V/2 404.78/291.71 aux(66) =< V1 404.78/291.71 aux(67) =< V 404.78/291.71 it(60) =< aux(66) 404.78/291.71 it(61) =< aux(66) 404.78/291.71 it(62) =< aux(66) 404.78/291.71 it(60) =< aux(67) 404.78/291.71 it(61) =< aux(67) 404.78/291.71 it(62) =< aux(67) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=1,V>=1] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],64]: 5*it(60)+5*it(61)+5*it(62)+3 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 it(61) =< V/2 404.78/291.71 aux(68) =< V1 404.78/291.71 aux(69) =< V 404.78/291.71 it(60) =< aux(68) 404.78/291.71 it(61) =< aux(68) 404.78/291.71 it(62) =< aux(68) 404.78/291.71 it(60) =< aux(69) 404.78/291.71 it(61) =< aux(69) 404.78/291.71 it(62) =< aux(69) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=2,V>=2] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],63]: 5*it(60)+5*it(61)+5*it(62)+3 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 it(61) =< V/2 404.78/291.71 aux(70) =< V1 404.78/291.71 aux(71) =< V 404.78/291.71 it(60) =< aux(70) 404.78/291.71 it(61) =< aux(70) 404.78/291.71 it(62) =< aux(70) 404.78/291.71 it(60) =< aux(71) 404.78/291.71 it(61) =< aux(71) 404.78/291.71 it(62) =< aux(71) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=2,V>=2] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],55,[51,52],66]: 25*it(51)+8 404.78/291.71 Such that:aux(72) =< V1 404.78/291.71 aux(73) =< V 404.78/291.71 it(51) =< aux(72) 404.78/291.71 it(51) =< aux(73) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=4,V>=5] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],55,66]: 5*it(60)+5*it(61)+5*it(62)+8 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 it(61) =< V/2 404.78/291.71 aux(74) =< V1 404.78/291.71 aux(75) =< V 404.78/291.71 it(60) =< aux(74) 404.78/291.71 it(61) =< aux(74) 404.78/291.71 it(62) =< aux(74) 404.78/291.71 it(60) =< aux(75) 404.78/291.71 it(61) =< aux(75) 404.78/291.71 it(62) =< aux(75) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=3,V>=4] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],54,[51,52],66]: 25*it(51)+8 404.78/291.71 Such that:aux(76) =< V1 404.78/291.71 aux(77) =< V 404.78/291.71 it(51) =< aux(76) 404.78/291.71 it(51) =< aux(77) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=5,V>=4] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],54,66]: 5*it(60)+5*it(61)+5*it(62)+8 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 it(61) =< V/2 404.78/291.71 aux(78) =< V1 404.78/291.71 aux(79) =< V 404.78/291.71 it(60) =< aux(78) 404.78/291.71 it(61) =< aux(78) 404.78/291.71 it(62) =< aux(78) 404.78/291.71 it(60) =< aux(79) 404.78/291.71 it(61) =< aux(79) 404.78/291.71 it(62) =< aux(79) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=4,V>=3] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],53,[51,52],66]: 25*it(51)+8 404.78/291.71 Such that:aux(80) =< V1 404.78/291.71 aux(81) =< V 404.78/291.71 it(51) =< aux(80) 404.78/291.71 it(51) =< aux(81) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=5,V>=5] 404.78/291.71 404.78/291.71 * Chain [[60,61,62],53,66]: 5*it(60)+5*it(61)+5*it(62)+8 404.78/291.71 Such that:it(60) =< V1/2 404.78/291.71 it(61) =< V/2 404.78/291.71 aux(82) =< V1 404.78/291.71 aux(83) =< V 404.78/291.71 it(60) =< aux(82) 404.78/291.71 it(61) =< aux(82) 404.78/291.71 it(62) =< aux(82) 404.78/291.71 it(60) =< aux(83) 404.78/291.71 it(61) =< aux(83) 404.78/291.71 it(62) =< aux(83) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=4,V>=4] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],64]: 10*it(56)+5*it(57)+5*it(58)+3 404.78/291.71 Such that:it(57) =< V1/2 404.78/291.71 it(58) =< V/2 404.78/291.71 aux(20) =< V1 404.78/291.71 aux(21) =< V 404.78/291.71 it(56) =< aux(20) 404.78/291.71 it(57) =< aux(20) 404.78/291.71 it(58) =< aux(20) 404.78/291.71 it(56) =< aux(21) 404.78/291.71 it(57) =< aux(21) 404.78/291.71 it(58) =< aux(21) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=2,V>=2] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],63]: 10*it(56)+5*it(57)+5*it(58)+3 404.78/291.71 Such that:it(57) =< V1/2 404.78/291.71 it(58) =< V/2 404.78/291.71 aux(28) =< V1 404.78/291.71 aux(29) =< V 404.78/291.71 it(56) =< aux(28) 404.78/291.71 it(57) =< aux(28) 404.78/291.71 it(58) =< aux(28) 404.78/291.71 it(56) =< aux(29) 404.78/291.71 it(57) =< aux(29) 404.78/291.71 it(58) =< aux(29) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=2,V>=2] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],55,[51,52],66]: 30*it(51)+8 404.78/291.71 Such that:aux(38) =< V1 404.78/291.71 aux(39) =< V 404.78/291.71 it(51) =< aux(38) 404.78/291.71 it(51) =< aux(39) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=4,V>=5] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],55,66]: 10*it(56)+5*it(57)+5*it(58)+8 404.78/291.71 Such that:it(57) =< V1/2 404.78/291.71 it(58) =< V/2 404.78/291.71 aux(42) =< V1 404.78/291.71 aux(43) =< V 404.78/291.71 it(56) =< aux(42) 404.78/291.71 it(57) =< aux(42) 404.78/291.71 it(58) =< aux(42) 404.78/291.71 it(56) =< aux(43) 404.78/291.71 it(57) =< aux(43) 404.78/291.71 it(58) =< aux(43) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=3,V>=4] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],54,[51,52],66]: 30*it(51)+8 404.78/291.71 Such that:aux(46) =< V1 404.78/291.71 aux(47) =< V 404.78/291.71 it(51) =< aux(46) 404.78/291.71 it(51) =< aux(47) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=5,V>=4] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],54,66]: 10*it(56)+5*it(57)+5*it(58)+8 404.78/291.71 Such that:it(57) =< V1/2 404.78/291.71 it(58) =< V/2 404.78/291.71 aux(50) =< V1 404.78/291.71 aux(51) =< V 404.78/291.71 it(56) =< aux(50) 404.78/291.71 it(57) =< aux(50) 404.78/291.71 it(58) =< aux(50) 404.78/291.71 it(56) =< aux(51) 404.78/291.71 it(57) =< aux(51) 404.78/291.71 it(58) =< aux(51) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=4,V>=3] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],53,[51,52],66]: 30*it(51)+8 404.78/291.71 Such that:aux(54) =< V1 404.78/291.71 aux(55) =< V 404.78/291.71 it(51) =< aux(54) 404.78/291.71 it(51) =< aux(55) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=5,V>=5] 404.78/291.71 404.78/291.71 * Chain [[56,57,58,59],53,66]: 10*it(56)+5*it(57)+5*it(58)+8 404.78/291.71 Such that:it(57) =< V1/2 404.78/291.71 it(58) =< V/2 404.78/291.71 aux(58) =< V1 404.78/291.71 aux(59) =< V 404.78/291.71 it(56) =< aux(58) 404.78/291.71 it(57) =< aux(58) 404.78/291.71 it(58) =< aux(58) 404.78/291.71 it(56) =< aux(59) 404.78/291.71 it(57) =< aux(59) 404.78/291.71 it(58) =< aux(59) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=4,V>=4] 404.78/291.71 404.78/291.71 * Chain [[51,52],66]: 10*it(51)+3 404.78/291.71 Such that:aux(36) =< V1 404.78/291.71 aux(37) =< V 404.78/291.71 it(51) =< aux(36) 404.78/291.71 it(51) =< aux(37) 404.78/291.71 404.78/291.71 with precondition: [Out=2,V1>=2,V>=2] 404.78/291.71 404.78/291.71 * Chain [66]: 3 404.78/291.71 with precondition: [V1=1,V=1,Out=2] 404.78/291.71 404.78/291.71 * Chain [65]: 2 404.78/291.71 with precondition: [Out=0,V1>=0,V>=0] 404.78/291.71 404.78/291.71 * Chain [64]: 3 404.78/291.71 with precondition: [V1=1,Out=1,V>=1] 404.78/291.71 404.78/291.71 * Chain [63]: 3 404.78/291.71 with precondition: [V=1,Out=1,V1>=1] 404.78/291.71 404.78/291.71 * Chain [55,[51,52],66]: 10*it(51)+8 404.78/291.71 Such that:aux(36) =< V1 404.78/291.71 aux(37) =< V 404.78/291.71 it(51) =< aux(36) 404.78/291.71 it(51) =< aux(37) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=3,V>=4] 404.78/291.71 404.78/291.71 * Chain [55,66]: 8 404.78/291.71 with precondition: [V1=2,Out=1,V>=3] 404.78/291.71 404.78/291.71 * Chain [54,[51,52],66]: 10*it(51)+8 404.78/291.71 Such that:aux(36) =< V1 404.78/291.71 aux(37) =< V 404.78/291.71 it(51) =< aux(36) 404.78/291.71 it(51) =< aux(37) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=4,V>=3] 404.78/291.71 404.78/291.71 * Chain [54,66]: 8 404.78/291.71 with precondition: [V=2,Out=1,V1>=3] 404.78/291.71 404.78/291.71 * Chain [53,[51,52],66]: 10*it(51)+8 404.78/291.71 Such that:aux(36) =< V1 404.78/291.71 aux(37) =< V 404.78/291.71 it(51) =< aux(36) 404.78/291.71 it(51) =< aux(37) 404.78/291.71 404.78/291.71 with precondition: [Out=1,V1>=4,V>=4] 404.78/291.71 404.78/291.71 * Chain [53,66]: 8 404.78/291.71 with precondition: [Out=1,V1>=3,V>=3] 404.78/291.71 404.78/291.71 404.78/291.71 #### Cost of chains of remove(V1,V,Out): 404.78/291.71 * Chain [[67,68,69,70,71],73]: 17*it(67)+18*it(68)+65*s(120)+680*s(121)+10*s(153)+25*s(156)+25*s(157)+170*s(158)+10 404.78/291.71 Such that:aux(93) =< V1/2 404.78/291.71 aux(104) =< V/3 404.78/291.71 aux(106) =< V1 404.78/291.71 aux(107) =< V 404.78/291.71 aux(108) =< V/2 404.78/291.71 s(120) =< aux(93) 404.78/291.71 s(121) =< aux(107) 404.78/291.71 s(121) =< aux(106) 404.78/291.71 s(120) =< aux(106) 404.78/291.71 s(120) =< aux(107) 404.78/291.71 it(68) =< aux(107) 404.78/291.71 it(67) =< aux(107) 404.78/291.71 it(67) =< aux(108) 404.78/291.71 it(68) =< aux(108) 404.78/291.71 it(67) =< aux(104) 404.78/291.71 aux(97) =< aux(106) 404.78/291.71 s(161) =< aux(107)*(1/2) 404.78/291.71 s(155) =< it(67)*aux(106) 404.78/291.71 aux(98) =< it(67)*aux(97) 404.78/291.71 s(162) =< aux(98)*(1/2) 404.78/291.71 s(156) =< s(162) 404.78/291.71 s(157) =< s(161) 404.78/291.71 s(158) =< aux(98) 404.78/291.71 s(158) =< aux(107) 404.78/291.71 s(156) =< aux(98) 404.78/291.71 s(157) =< aux(98) 404.78/291.71 s(156) =< aux(107) 404.78/291.71 s(157) =< aux(107) 404.78/291.71 s(153) =< s(155) 404.78/291.71 s(153) =< aux(107) 404.78/291.71 404.78/291.71 with precondition: [V1>=1,V>=2,Out>=0,V>=Out] 404.78/291.71 404.78/291.71 * Chain [[67,68,69,70,71],72]: 6*it(67)+18*it(68)+11*it(69)+10*s(153)+25*s(156)+25*s(157)+170*s(158)+2 404.78/291.71 Such that:aux(96) =< V1 404.78/291.71 aux(109) =< V 404.78/291.71 aux(110) =< V/2 404.78/291.71 aux(111) =< V/3 404.78/291.71 it(68) =< aux(109) 404.78/291.71 it(69) =< aux(109) 404.78/291.71 it(67) =< aux(110) 404.78/291.71 it(68) =< aux(110) 404.78/291.71 it(69) =< aux(110) 404.78/291.71 it(67) =< aux(111) 404.78/291.71 it(69) =< aux(111) 404.78/291.71 aux(97) =< aux(96) 404.78/291.71 s(161) =< aux(109)*(1/2) 404.78/291.71 s(155) =< it(67)*aux(96) 404.78/291.71 aux(98) =< it(69)*aux(97) 404.78/291.71 s(162) =< aux(98)*(1/2) 404.78/291.71 s(156) =< s(162) 404.78/291.71 s(157) =< s(161) 404.78/291.71 s(158) =< aux(98) 404.78/291.71 s(158) =< aux(109) 404.78/291.71 s(156) =< aux(98) 404.78/291.71 s(157) =< aux(98) 404.78/291.71 s(156) =< aux(109) 404.78/291.71 s(157) =< aux(109) 404.78/291.71 s(153) =< s(155) 404.78/291.71 s(153) =< aux(109) 404.78/291.71 404.78/291.71 with precondition: [V1>=1,V>=3,Out>=1,V>=Out] 404.78/291.71 404.78/291.71 * Chain [73]: 65*s(120)+60*s(121)+620*s(122)+10 404.78/291.71 Such that:aux(92) =< V1 404.78/291.71 aux(93) =< V1/2 404.78/291.71 aux(94) =< V 404.78/291.71 aux(95) =< V/2 404.78/291.71 s(120) =< aux(93) 404.78/291.71 s(121) =< aux(95) 404.78/291.71 s(122) =< aux(92) 404.78/291.71 s(122) =< aux(94) 404.78/291.71 s(120) =< aux(92) 404.78/291.71 s(121) =< aux(92) 404.78/291.71 s(120) =< aux(94) 404.78/291.71 s(121) =< aux(94) 404.78/291.71 404.78/291.71 with precondition: [Out=0,V1>=0,V>=0] 404.78/291.71 404.78/291.71 * Chain [72]: 2 404.78/291.71 with precondition: [V=1,Out=1,V1>=0] 404.78/291.71 404.78/291.71 404.78/291.71 #### Cost of chains of nub(V1,Out): 404.78/291.71 * Chain [[76],78,74]: 757*it(76)+815*s(236)+50*s(237)+50*s(238)+340*s(239)+20*s(240)+13 404.78/291.71 Such that:aux(120) =< V1 404.78/291.71 it(76) =< aux(120) 404.78/291.71 aux(118) =< aux(120) 404.78/291.71 s(241) =< it(76)*aux(118) 404.78/291.71 s(236) =< s(241) 404.78/291.71 s(244) =< s(241)*(1/2) 404.78/291.71 s(242) =< s(236)*aux(120) 404.78/291.71 s(243) =< s(236)*aux(118) 404.78/291.71 s(245) =< s(243)*(1/2) 404.78/291.71 s(237) =< s(245) 404.78/291.71 s(238) =< s(244) 404.78/291.71 s(239) =< s(243) 404.78/291.71 s(239) =< s(241) 404.78/291.71 s(237) =< s(243) 404.78/291.71 s(238) =< s(243) 404.78/291.71 s(237) =< s(241) 404.78/291.71 s(238) =< s(241) 404.78/291.71 s(240) =< s(242) 404.78/291.71 s(240) =< s(241) 404.78/291.71 404.78/291.71 with precondition: [V1>=4,Out>=3,V1>=Out] 404.78/291.71 404.78/291.71 * Chain [[76],77,78,74]: 12*it(76)+745*s(201)+815*s(236)+50*s(237)+50*s(238)+340*s(239)+20*s(240)+17 404.78/291.72 Such that:aux(116) =< 1 404.78/291.72 aux(121) =< V1 404.78/291.72 it(76) =< aux(121) 404.78/291.72 s(201) =< aux(116) 404.78/291.72 aux(118) =< aux(121) 404.78/291.72 s(241) =< it(76)*aux(118) 404.78/291.72 s(236) =< s(241) 404.78/291.72 s(244) =< s(241)*(1/2) 404.78/291.72 s(242) =< s(236)*aux(121) 404.78/291.72 s(243) =< s(236)*aux(118) 404.78/291.72 s(245) =< s(243)*(1/2) 404.78/291.72 s(237) =< s(245) 404.78/291.72 s(238) =< s(244) 404.78/291.72 s(239) =< s(243) 404.78/291.72 s(239) =< s(241) 404.78/291.72 s(237) =< s(243) 404.78/291.72 s(238) =< s(243) 404.78/291.72 s(237) =< s(241) 404.78/291.72 s(238) =< s(241) 404.78/291.72 s(240) =< s(242) 404.78/291.72 s(240) =< s(241) 404.78/291.72 404.78/291.72 with precondition: [Out>=4,V1>=Out] 404.78/291.72 404.78/291.72 * Chain [[76],77,75]: 12*it(76)+815*s(236)+50*s(237)+50*s(238)+340*s(239)+20*s(240)+6 404.78/291.72 Such that:aux(122) =< V1 404.78/291.72 it(76) =< aux(122) 404.78/291.72 aux(118) =< aux(122) 404.78/291.72 s(241) =< it(76)*aux(118) 404.78/291.72 s(236) =< s(241) 404.78/291.72 s(244) =< s(241)*(1/2) 404.78/291.72 s(242) =< s(236)*aux(122) 404.78/291.72 s(243) =< s(236)*aux(118) 404.78/291.72 s(245) =< s(243)*(1/2) 404.78/291.72 s(237) =< s(245) 404.78/291.72 s(238) =< s(244) 404.78/291.72 s(239) =< s(243) 404.78/291.72 s(239) =< s(241) 404.78/291.72 s(237) =< s(243) 404.78/291.72 s(238) =< s(243) 404.78/291.72 s(237) =< s(241) 404.78/291.72 s(238) =< s(241) 404.78/291.72 s(240) =< s(242) 404.78/291.72 s(240) =< s(241) 404.78/291.72 404.78/291.72 with precondition: [Out>=4,V1>=Out] 404.78/291.72 404.78/291.72 * Chain [[76],77,74]: 12*it(76)+815*s(236)+50*s(237)+50*s(238)+340*s(239)+20*s(240)+5 404.78/291.72 Such that:aux(123) =< V1 404.78/291.72 it(76) =< aux(123) 404.78/291.72 aux(118) =< aux(123) 404.78/291.72 s(241) =< it(76)*aux(118) 404.78/291.72 s(236) =< s(241) 404.78/291.72 s(244) =< s(241)*(1/2) 404.78/291.72 s(242) =< s(236)*aux(123) 404.78/291.72 s(243) =< s(236)*aux(118) 404.78/291.72 s(245) =< s(243)*(1/2) 404.78/291.72 s(237) =< s(245) 404.78/291.72 s(238) =< s(244) 404.78/291.72 s(239) =< s(243) 404.78/291.72 s(239) =< s(241) 404.78/291.72 s(237) =< s(243) 404.78/291.72 s(238) =< s(243) 404.78/291.72 s(237) =< s(241) 404.78/291.72 s(238) =< s(241) 404.78/291.72 s(240) =< s(242) 404.78/291.72 s(240) =< s(241) 404.78/291.72 404.78/291.72 with precondition: [Out>=3,V1>=Out+1] 404.78/291.72 404.78/291.72 * Chain [[76],75]: 12*it(76)+815*s(236)+50*s(237)+50*s(238)+340*s(239)+20*s(240)+2 404.78/291.72 Such that:aux(124) =< V1 404.78/291.72 it(76) =< aux(124) 404.78/291.72 aux(118) =< aux(124) 404.78/291.72 s(241) =< it(76)*aux(118) 404.78/291.72 s(236) =< s(241) 404.78/291.72 s(244) =< s(241)*(1/2) 404.78/291.72 s(242) =< s(236)*aux(124) 404.78/291.72 s(243) =< s(236)*aux(118) 404.78/291.72 s(245) =< s(243)*(1/2) 404.78/291.72 s(237) =< s(245) 404.78/291.72 s(238) =< s(244) 404.78/291.72 s(239) =< s(243) 404.78/291.72 s(239) =< s(241) 404.78/291.72 s(237) =< s(243) 404.78/291.72 s(238) =< s(243) 404.78/291.72 s(237) =< s(241) 404.78/291.72 s(238) =< s(241) 404.78/291.72 s(240) =< s(242) 404.78/291.72 s(240) =< s(241) 404.78/291.72 404.78/291.72 with precondition: [Out>=3,V1>=Out+1] 404.78/291.72 404.78/291.72 * Chain [[76],74]: 12*it(76)+815*s(236)+50*s(237)+50*s(238)+340*s(239)+20*s(240)+1 404.78/291.72 Such that:aux(125) =< V1 404.78/291.72 it(76) =< aux(125) 404.78/291.72 aux(118) =< aux(125) 404.78/291.72 s(241) =< it(76)*aux(118) 404.78/291.72 s(236) =< s(241) 404.78/291.72 s(244) =< s(241)*(1/2) 404.78/291.72 s(242) =< s(236)*aux(125) 404.78/291.72 s(243) =< s(236)*aux(118) 404.78/291.72 s(245) =< s(243)*(1/2) 404.78/291.72 s(237) =< s(245) 404.78/291.72 s(238) =< s(244) 404.78/291.72 s(239) =< s(243) 404.78/291.72 s(239) =< s(241) 404.78/291.72 s(237) =< s(243) 404.78/291.72 s(238) =< s(243) 404.78/291.72 s(237) =< s(241) 404.78/291.72 s(238) =< s(241) 404.78/291.72 s(240) =< s(242) 404.78/291.72 s(240) =< s(241) 404.78/291.72 404.78/291.72 with precondition: [Out>=2,V1>=Out+2] 404.78/291.72 404.78/291.72 * Chain [78,74]: 745*s(201)+13 404.78/291.72 Such that:aux(116) =< V1 404.78/291.72 s(201) =< aux(116) 404.78/291.72 404.78/291.72 with precondition: [Out>=1,V1>=Out] 404.78/291.72 404.78/291.72 * Chain [77,78,74]: 745*s(201)+17 404.78/291.72 Such that:aux(116) =< 1 404.78/291.72 s(201) =< aux(116) 404.78/291.72 404.78/291.72 with precondition: [V1=Out,V1>=2] 404.78/291.72 404.78/291.72 * Chain [77,75]: 6 404.78/291.72 with precondition: [V1=Out,V1>=2] 404.78/291.72 404.78/291.72 * Chain [77,74]: 5 404.78/291.72 with precondition: [V1=Out+1,V1>=2] 404.78/291.72 404.78/291.72 * Chain [75]: 2 404.78/291.72 with precondition: [V1=1,Out=1] 404.78/291.72 404.78/291.72 * Chain [74]: 1 404.78/291.72 with precondition: [Out=0,V1>=0] 404.78/291.72 404.78/291.72 404.78/291.72 #### Cost of chains of start(V1,V,V16,V33): 404.78/291.72 * Chain [92]: 3040*s(319)+4075*s(323)+250*s(328)+250*s(329)+1700*s(330)+100*s(331)+7804*s(336)+352*s(344)+200*s(352)+200*s(353)+1360*s(354)+80*s(355)+9780*s(366)+600*s(371)+600*s(372)+4080*s(373)+240*s(374)+50*s(451)+50*s(452)+340*s(453)+20*s(454)+1290*s(476)+965*s(477)+13225*s(478)+100*s(518)+100*s(519)+680*s(520)+40*s(521)+56*s(588)+12*s(589)+100*s(595)+100*s(596)+680*s(597)+20*s(598)+20*s(602)+360*s(797)+340*s(798)+3200*s(799)+36*s(958)+28*s(959)+6*s(960)+50*s(966)+50*s(967)+340*s(968)+10*s(969)+10*s(973)+773 404.78/291.72 Such that:s(957) =< V/3 404.78/291.72 aux(144) =< 1 404.78/291.72 aux(145) =< V1 404.78/291.72 aux(146) =< V1/2 404.78/291.72 aux(147) =< V1/3 404.78/291.72 aux(148) =< V 404.78/291.72 aux(149) =< V/2 404.78/291.72 aux(150) =< V16 404.78/291.72 aux(151) =< V16/2 404.78/291.72 s(319) =< aux(144) 404.78/291.72 s(321) =< aux(144) 404.78/291.72 s(322) =< s(319)*s(321) 404.78/291.72 s(323) =< s(322) 404.78/291.72 s(324) =< s(322)*(1/2) 404.78/291.72 s(325) =< s(323)*aux(144) 404.78/291.72 s(326) =< s(323)*s(321) 404.78/291.72 s(327) =< s(326)*(1/2) 404.78/291.72 s(328) =< s(327) 404.78/291.72 s(329) =< s(324) 404.78/291.72 s(330) =< s(326) 404.78/291.72 s(330) =< s(322) 404.78/291.72 s(328) =< s(326) 404.78/291.72 s(329) =< s(326) 404.78/291.72 s(328) =< s(322) 404.78/291.72 s(329) =< s(322) 404.78/291.72 s(331) =< s(325) 404.78/291.72 s(331) =< s(322) 404.78/291.72 s(336) =< aux(145) 404.78/291.72 s(347) =< aux(145) 404.78/291.72 s(365) =< s(336)*s(347) 404.78/291.72 s(366) =< s(365) 404.78/291.72 s(367) =< s(365)*(1/2) 404.78/291.72 s(368) =< s(366)*aux(145) 404.78/291.72 s(369) =< s(366)*s(347) 404.78/291.72 s(370) =< s(369)*(1/2) 404.78/291.72 s(371) =< s(370) 404.78/291.72 s(372) =< s(367) 404.78/291.72 s(373) =< s(369) 404.78/291.72 s(373) =< s(365) 404.78/291.72 s(371) =< s(369) 404.78/291.72 s(372) =< s(369) 404.78/291.72 s(371) =< s(365) 404.78/291.72 s(372) =< s(365) 404.78/291.72 s(374) =< s(368) 404.78/291.72 s(374) =< s(365) 404.78/291.72 s(344) =< aux(145) 404.78/291.72 s(344) =< aux(146) 404.78/291.72 s(348) =< aux(145)*(1/2) 404.78/291.72 s(349) =< s(344)*aux(145) 404.78/291.72 s(350) =< s(344)*s(347) 404.78/291.72 s(351) =< s(350)*(1/2) 404.78/291.72 s(352) =< s(351) 404.78/291.72 s(353) =< s(348) 404.78/291.72 s(354) =< s(350) 404.78/291.72 s(354) =< aux(145) 404.78/291.72 s(352) =< s(350) 404.78/291.72 s(353) =< s(350) 404.78/291.72 s(352) =< aux(145) 404.78/291.72 s(353) =< aux(145) 404.78/291.72 s(355) =< s(349) 404.78/291.72 s(355) =< aux(145) 404.78/291.72 s(448) =< s(336)*aux(145) 404.78/291.72 s(451) =< s(367) 404.78/291.72 s(452) =< s(348) 404.78/291.72 s(453) =< s(365) 404.78/291.72 s(453) =< aux(145) 404.78/291.72 s(451) =< s(365) 404.78/291.72 s(452) =< s(365) 404.78/291.72 s(451) =< aux(145) 404.78/291.72 s(452) =< aux(145) 404.78/291.72 s(454) =< s(448) 404.78/291.72 s(454) =< aux(145) 404.78/291.72 s(513) =< aux(148) 404.78/291.72 s(515) =< s(336)*aux(148) 404.78/291.72 s(516) =< s(336)*s(513) 404.78/291.72 s(517) =< s(516)*(1/2) 404.78/291.72 s(518) =< s(517) 404.78/291.72 s(519) =< s(348) 404.78/291.72 s(520) =< s(516) 404.78/291.72 s(520) =< aux(145) 404.78/291.72 s(518) =< s(516) 404.78/291.72 s(519) =< s(516) 404.78/291.72 s(518) =< aux(145) 404.78/291.72 s(519) =< aux(145) 404.78/291.72 s(521) =< s(515) 404.78/291.72 s(521) =< aux(145) 404.78/291.72 s(476) =< aux(149) 404.78/291.72 s(478) =< aux(145) 404.78/291.72 s(478) =< aux(148) 404.78/291.72 s(476) =< aux(148) 404.78/291.72 s(476) =< aux(145) 404.78/291.72 s(477) =< aux(146) 404.78/291.72 s(477) =< aux(148) 404.78/291.72 s(477) =< aux(145) 404.78/291.72 s(588) =< aux(145) 404.78/291.72 s(589) =< aux(146) 404.78/291.72 s(588) =< aux(146) 404.78/291.72 s(589) =< aux(147) 404.78/291.72 s(588) =< aux(147) 404.78/291.72 s(592) =< s(589)*aux(148) 404.78/291.72 s(593) =< s(588)*s(513) 404.78/291.72 s(594) =< s(593)*(1/2) 404.78/291.72 s(595) =< s(594) 404.78/291.72 s(596) =< s(348) 404.78/291.72 s(597) =< s(593) 404.78/291.72 s(597) =< aux(145) 404.78/291.72 s(595) =< s(593) 404.78/291.72 s(596) =< s(593) 404.78/291.72 s(595) =< aux(145) 404.78/291.72 s(596) =< aux(145) 404.78/291.72 s(598) =< s(592) 404.78/291.72 s(598) =< aux(145) 404.78/291.72 s(601) =< s(588)*aux(148) 404.78/291.72 s(602) =< s(601) 404.78/291.72 s(602) =< aux(145) 404.78/291.72 s(797) =< aux(151) 404.78/291.72 s(798) =< aux(146) 404.78/291.72 s(799) =< aux(150) 404.78/291.72 s(799) =< aux(145) 404.78/291.72 s(797) =< aux(150) 404.78/291.72 s(798) =< aux(150) 404.78/291.72 s(797) =< aux(145) 404.78/291.72 s(798) =< aux(145) 404.78/291.72 s(958) =< aux(148) 404.78/291.72 s(959) =< aux(148) 404.78/291.72 s(960) =< aux(149) 404.78/291.72 s(958) =< aux(149) 404.78/291.72 s(959) =< aux(149) 404.78/291.72 s(960) =< s(957) 404.78/291.72 s(959) =< s(957) 404.78/291.72 s(962) =< aux(148)*(1/2) 404.78/291.72 s(963) =< s(960)*aux(145) 404.78/291.72 s(964) =< s(959)*s(347) 404.78/291.72 s(965) =< s(964)*(1/2) 404.78/291.72 s(966) =< s(965) 404.78/291.72 s(967) =< s(962) 404.78/291.72 s(968) =< s(964) 404.78/291.72 s(968) =< aux(148) 404.78/291.72 s(966) =< s(964) 404.78/291.72 s(967) =< s(964) 404.78/291.72 s(966) =< aux(148) 404.78/291.72 s(967) =< aux(148) 404.78/291.72 s(969) =< s(963) 404.78/291.72 s(969) =< aux(148) 404.78/291.72 s(972) =< s(959)*aux(145) 404.78/291.72 s(973) =< s(972) 404.78/291.72 s(973) =< aux(148) 404.78/291.72 404.78/291.72 with precondition: [V1>=0] 404.78/291.72 404.78/291.72 * Chain [91]: 1 404.78/291.72 with precondition: [V1=0,V>=1] 404.78/291.72 404.78/291.72 * Chain [90]: 130*s(978)+60*s(979)+1300*s(980)+36*s(986)+28*s(987)+6*s(988)+50*s(994)+50*s(995)+340*s(996)+10*s(997)+10*s(1001)+11 404.78/291.72 Such that:s(985) =< V33/3 404.78/291.72 aux(152) =< V 404.78/291.72 aux(153) =< V/2 404.78/291.72 aux(154) =< V33 404.78/291.72 aux(155) =< V33/2 404.78/291.72 s(978) =< aux(153) 404.78/291.72 s(979) =< aux(155) 404.78/291.72 s(980) =< aux(152) 404.78/291.72 s(980) =< aux(154) 404.78/291.72 s(978) =< aux(152) 404.78/291.72 s(979) =< aux(152) 404.78/291.72 s(978) =< aux(154) 404.78/291.72 s(979) =< aux(154) 404.78/291.72 s(986) =< aux(154) 404.78/291.72 s(987) =< aux(154) 404.78/291.72 s(988) =< aux(155) 404.78/291.72 s(986) =< aux(155) 404.78/291.72 s(987) =< aux(155) 404.78/291.72 s(988) =< s(985) 404.78/291.72 s(987) =< s(985) 404.78/291.72 s(989) =< aux(152) 404.78/291.72 s(990) =< aux(154)*(1/2) 404.78/291.72 s(991) =< s(988)*aux(152) 404.78/291.72 s(992) =< s(987)*s(989) 404.78/291.72 s(993) =< s(992)*(1/2) 404.78/291.72 s(994) =< s(993) 404.78/291.72 s(995) =< s(990) 404.78/291.72 s(996) =< s(992) 404.78/291.72 s(996) =< aux(154) 404.78/291.72 s(994) =< s(992) 404.78/291.72 s(995) =< s(992) 404.78/291.72 s(994) =< aux(154) 404.78/291.72 s(995) =< aux(154) 404.78/291.72 s(997) =< s(991) 404.78/291.72 s(997) =< aux(154) 404.78/291.72 s(1000) =< s(987)*aux(152) 404.78/291.72 s(1001) =< s(1000) 404.78/291.72 s(1001) =< aux(154) 404.78/291.72 404.78/291.72 with precondition: [V1=1] 404.78/291.72 404.78/291.72 * Chain [89]: 180*s(1006)+170*s(1007)+1600*s(1008)+11 404.78/291.72 Such that:aux(156) =< V1 404.78/291.72 aux(157) =< V1/2 404.78/291.72 aux(158) =< V16 404.78/291.72 aux(159) =< V16/2 404.78/291.72 s(1006) =< aux(159) 404.78/291.72 s(1007) =< aux(157) 404.78/291.72 s(1008) =< aux(158) 404.78/291.72 s(1008) =< aux(156) 404.78/291.72 s(1006) =< aux(158) 404.78/291.72 s(1007) =< aux(158) 404.78/291.72 s(1006) =< aux(156) 404.78/291.72 s(1007) =< aux(156) 404.78/291.72 404.78/291.72 with precondition: [V=0,V1>=1] 404.78/291.72 404.78/291.72 * Chain [88]: 260*s(1060)+120*s(1061)+2600*s(1062)+72*s(1068)+56*s(1069)+12*s(1070)+100*s(1076)+100*s(1077)+680*s(1078)+20*s(1079)+20*s(1083)+15 404.78/291.72 Such that:aux(160) =< 1 404.78/291.72 aux(161) =< 1/2 404.78/291.72 aux(162) =< V1 404.78/291.72 aux(163) =< V1/2 404.78/291.72 aux(164) =< V1/3 404.78/291.72 s(1060) =< aux(161) 404.78/291.72 s(1061) =< aux(163) 404.78/291.72 s(1062) =< aux(160) 404.78/291.72 s(1062) =< aux(162) 404.78/291.72 s(1060) =< aux(160) 404.78/291.72 s(1061) =< aux(160) 404.78/291.72 s(1060) =< aux(162) 404.78/291.72 s(1061) =< aux(162) 404.78/291.72 s(1068) =< aux(162) 404.78/291.72 s(1069) =< aux(162) 404.78/291.72 s(1070) =< aux(163) 404.78/291.72 s(1068) =< aux(163) 404.78/291.72 s(1069) =< aux(163) 404.78/291.72 s(1070) =< aux(164) 404.78/291.72 s(1069) =< aux(164) 404.78/291.72 s(1071) =< aux(160) 404.78/291.72 s(1072) =< aux(162)*(1/2) 404.78/291.72 s(1073) =< s(1070)*aux(160) 404.78/291.72 s(1074) =< s(1069)*s(1071) 404.78/291.72 s(1075) =< s(1074)*(1/2) 404.78/291.72 s(1076) =< s(1075) 404.78/291.72 s(1077) =< s(1072) 404.78/291.72 s(1078) =< s(1074) 404.78/291.72 s(1078) =< aux(162) 404.78/291.72 s(1076) =< s(1074) 404.78/291.72 s(1077) =< s(1074) 404.78/291.72 s(1076) =< aux(162) 404.78/291.72 s(1077) =< aux(162) 404.78/291.72 s(1079) =< s(1073) 404.78/291.72 s(1079) =< aux(162) 404.78/291.72 s(1082) =< s(1069)*aux(160) 404.78/291.72 s(1083) =< s(1082) 404.78/291.72 s(1083) =< aux(162) 404.78/291.72 404.78/291.72 with precondition: [V=1,V1>=0] 404.78/291.72 404.78/291.72 * Chain [87]: 7 404.78/291.72 with precondition: [V1=2,V>=2] 404.78/291.72 404.78/291.72 * Chain [86]: 6 404.78/291.72 with precondition: [V1=2,V>=1,V16>=1] 404.78/291.72 404.78/291.72 * Chain [85]: 130*s(1116)+60*s(1117)+1300*s(1118)+36*s(1124)+28*s(1125)+6*s(1126)+50*s(1132)+50*s(1133)+340*s(1134)+10*s(1135)+10*s(1139)+11 404.78/291.72 Such that:s(1123) =< V33/3 404.78/291.72 aux(165) =< V 404.78/291.72 aux(166) =< V/2 404.78/291.72 aux(167) =< V33 404.78/291.72 aux(168) =< V33/2 404.78/291.72 s(1116) =< aux(166) 404.78/291.72 s(1117) =< aux(168) 404.78/291.72 s(1118) =< aux(165) 404.78/291.72 s(1118) =< aux(167) 404.78/291.72 s(1116) =< aux(165) 404.78/291.72 s(1117) =< aux(165) 404.78/291.72 s(1116) =< aux(167) 404.78/291.72 s(1117) =< aux(167) 404.78/291.72 s(1124) =< aux(167) 404.78/291.72 s(1125) =< aux(167) 404.78/291.72 s(1126) =< aux(168) 404.78/291.72 s(1124) =< aux(168) 404.78/291.72 s(1125) =< aux(168) 404.78/291.72 s(1126) =< s(1123) 404.78/291.72 s(1125) =< s(1123) 404.78/291.72 s(1127) =< aux(165) 404.78/291.72 s(1128) =< aux(167)*(1/2) 404.78/291.72 s(1129) =< s(1126)*aux(165) 404.78/291.72 s(1130) =< s(1125)*s(1127) 404.78/291.72 s(1131) =< s(1130)*(1/2) 404.78/291.72 s(1132) =< s(1131) 404.78/291.72 s(1133) =< s(1128) 404.78/291.72 s(1134) =< s(1130) 404.78/291.72 s(1134) =< aux(167) 404.78/291.72 s(1132) =< s(1130) 404.78/291.72 s(1133) =< s(1130) 404.78/291.72 s(1132) =< aux(167) 404.78/291.72 s(1133) =< aux(167) 404.78/291.72 s(1135) =< s(1129) 404.78/291.72 s(1135) =< aux(167) 404.78/291.72 s(1138) =< s(1125)*aux(165) 404.78/291.72 s(1139) =< s(1138) 404.78/291.72 s(1139) =< aux(167) 404.78/291.72 404.78/291.72 with precondition: [V1=2,V>=0,V16>=0,V33>=0] 404.78/291.72 404.78/291.72 * Chain [84]: 11 404.78/291.72 with precondition: [V1=3,V=0,V16>=3] 404.78/291.72 404.78/291.72 * Chain [83]: 11 404.78/291.72 with precondition: [V1=3,V>=1] 404.78/291.72 404.78/291.72 * Chain [82]: 12 404.78/291.72 with precondition: [V1=4,V>=3] 404.78/291.72 404.78/291.72 * Chain [81]: 6 404.78/291.72 with precondition: [V16=1,V1>=2,V>=0] 404.78/291.72 404.78/291.72 * Chain [80]: 8 404.78/291.72 with precondition: [V=2,V1>=2] 404.78/291.72 404.78/291.72 * Chain [79]: 12 404.78/291.72 with precondition: [V=3,V1>=4] 404.78/291.72 404.78/291.72 404.78/291.72 Closed-form bounds of start(V1,V,V16,V33): 404.78/291.72 ------------------------------------- 404.78/291.72 * Chain [92] with precondition: [V1>=0] 404.78/291.72 - Upper bound: 25352*V1+9938+15000*V1*V1+nat(V)*499+nat(V16)*3200+1317/2*V1+nat(V/2)*1296+nat(V16/2)*360 404.78/291.72 - Complexity: n^2 404.78/291.72 * Chain [91] with precondition: [V1=0,V>=1] 404.78/291.72 - Upper bound: 1 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [90] with precondition: [V1=1] 404.78/291.72 - Upper bound: nat(V)*1300+11+nat(V33)*499+nat(V/2)*130+nat(V33/2)*66 404.78/291.72 - Complexity: n 404.78/291.72 * Chain [89] with precondition: [V=0,V1>=1] 404.78/291.72 - Upper bound: nat(V16)*1600+11+85*V1+nat(V16/2)*180 404.78/291.72 - Complexity: n 404.78/291.72 * Chain [88] with precondition: [V=1,V1>=0] 404.78/291.72 - Upper bound: 944*V1+2865 404.78/291.72 - Complexity: n 404.78/291.72 * Chain [87] with precondition: [V1=2,V>=2] 404.78/291.72 - Upper bound: 7 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [86] with precondition: [V1=2,V>=1,V16>=1] 404.78/291.72 - Upper bound: 6 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [85] with precondition: [V1=2,V>=0,V16>=0,V33>=0] 404.78/291.72 - Upper bound: 1365*V+532*V33+11 404.78/291.72 - Complexity: n 404.78/291.72 * Chain [84] with precondition: [V1=3,V=0,V16>=3] 404.78/291.72 - Upper bound: 11 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [83] with precondition: [V1=3,V>=1] 404.78/291.72 - Upper bound: 11 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [82] with precondition: [V1=4,V>=3] 404.78/291.72 - Upper bound: 12 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [81] with precondition: [V16=1,V1>=2,V>=0] 404.78/291.72 - Upper bound: 6 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [80] with precondition: [V=2,V1>=2] 404.78/291.72 - Upper bound: 8 404.78/291.72 - Complexity: constant 404.78/291.72 * Chain [79] with precondition: [V=3,V1>=4] 404.78/291.72 - Upper bound: 12 404.78/291.72 - Complexity: constant 404.78/291.72 404.78/291.72 ### Maximum cost of start(V1,V,V16,V33): max([max([11,nat(V)*1300+10+nat(V33)*499+nat(V/2)*130+nat(V33/2)*66]),16*V1+10+max([nat(V16)*1600+69*V1+nat(V16/2)*180,24424*V1+7073+15000*V1*V1+nat(V)*499+nat(V16)*3200+1285/2*V1+nat(V/2)*1296+nat(V16/2)*360+(928*V1+2854)])])+1 404.78/291.72 Asymptotic class: n^2 404.78/291.72 * Total analysis performed in 3459 ms. 404.78/291.72 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (12) 404.78/291.72 BOUNDS(1, n^2) 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (13) RenamingProof (BOTH BOUNDS(ID, ID)) 404.78/291.72 Renamed function symbols to avoid clashes with predefined symbol. 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (14) 404.78/291.72 Obligation: 404.78/291.72 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 404.78/291.72 404.78/291.72 404.78/291.72 The TRS R consists of the following rules: 404.78/291.72 404.78/291.72 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.72 and(@x, @y) -> #and(@x, @y) 404.78/291.72 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.72 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.72 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.72 eq#2(::(@y, @ys)) -> #false 404.78/291.72 eq#2(nil) -> #true 404.78/291.72 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.72 eq#3(nil, @x, @xs) -> #false 404.78/291.72 nub(@l) -> nub#1(@l) 404.78/291.72 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.72 nub#1(nil) -> nil 404.78/291.72 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.72 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.72 remove#1(nil, @x) -> nil 404.78/291.72 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.72 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.72 404.78/291.72 The (relative) TRS S consists of the following rules: 404.78/291.72 404.78/291.72 #and(#false, #false) -> #false 404.78/291.72 #and(#false, #true) -> #false 404.78/291.72 #and(#true, #false) -> #false 404.78/291.72 #and(#true, #true) -> #true 404.78/291.72 #eq(#0, #0) -> #true 404.78/291.72 #eq(#0, #neg(@y)) -> #false 404.78/291.72 #eq(#0, #pos(@y)) -> #false 404.78/291.72 #eq(#0, #s(@y)) -> #false 404.78/291.72 #eq(#neg(@x), #0) -> #false 404.78/291.72 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #0) -> #false 404.78/291.72 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#s(@x), #0) -> #false 404.78/291.72 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.72 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.72 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.72 #eq(nil, nil) -> #true 404.78/291.72 404.78/291.72 Rewrite Strategy: INNERMOST 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 404.78/291.72 Infered types. 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (16) 404.78/291.72 Obligation: 404.78/291.72 Innermost TRS: 404.78/291.72 Rules: 404.78/291.72 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.72 and(@x, @y) -> #and(@x, @y) 404.78/291.72 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.72 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.72 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.72 eq#2(::(@y, @ys)) -> #false 404.78/291.72 eq#2(nil) -> #true 404.78/291.72 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.72 eq#3(nil, @x, @xs) -> #false 404.78/291.72 nub(@l) -> nub#1(@l) 404.78/291.72 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.72 nub#1(nil) -> nil 404.78/291.72 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.72 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.72 remove#1(nil, @x) -> nil 404.78/291.72 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.72 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.72 #and(#false, #false) -> #false 404.78/291.72 #and(#false, #true) -> #false 404.78/291.72 #and(#true, #false) -> #false 404.78/291.72 #and(#true, #true) -> #true 404.78/291.72 #eq(#0, #0) -> #true 404.78/291.72 #eq(#0, #neg(@y)) -> #false 404.78/291.72 #eq(#0, #pos(@y)) -> #false 404.78/291.72 #eq(#0, #s(@y)) -> #false 404.78/291.72 #eq(#neg(@x), #0) -> #false 404.78/291.72 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #0) -> #false 404.78/291.72 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#s(@x), #0) -> #false 404.78/291.72 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.72 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.72 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.72 #eq(nil, nil) -> #true 404.78/291.72 404.78/291.72 Types: 404.78/291.72 #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 #and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 eq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#3 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 nil :: :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#2 :: :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #false :: #false:#true 404.78/291.72 #true :: #false:#true 404.78/291.72 nub :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 nub#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #0 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 hole_#false:#true1_4 :: #false:#true 404.78/291.72 hole_:::nil:#0:#neg:#pos:#s2_4 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4 :: Nat -> :::nil:#0:#neg:#pos:#s 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (17) OrderProof (LOWER BOUND(ID)) 404.78/291.72 Heuristically decided to analyse the following defined symbols: 404.78/291.72 #eq, eq, eq#1, nub, nub#1, remove, remove#1 404.78/291.72 404.78/291.72 They will be analysed ascendingly in the following order: 404.78/291.72 eq = eq#1 404.78/291.72 eq < remove#1 404.78/291.72 nub = nub#1 404.78/291.72 remove < nub#1 404.78/291.72 remove = remove#1 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (18) 404.78/291.72 Obligation: 404.78/291.72 Innermost TRS: 404.78/291.72 Rules: 404.78/291.72 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.72 and(@x, @y) -> #and(@x, @y) 404.78/291.72 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.72 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.72 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.72 eq#2(::(@y, @ys)) -> #false 404.78/291.72 eq#2(nil) -> #true 404.78/291.72 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.72 eq#3(nil, @x, @xs) -> #false 404.78/291.72 nub(@l) -> nub#1(@l) 404.78/291.72 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.72 nub#1(nil) -> nil 404.78/291.72 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.72 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.72 remove#1(nil, @x) -> nil 404.78/291.72 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.72 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.72 #and(#false, #false) -> #false 404.78/291.72 #and(#false, #true) -> #false 404.78/291.72 #and(#true, #false) -> #false 404.78/291.72 #and(#true, #true) -> #true 404.78/291.72 #eq(#0, #0) -> #true 404.78/291.72 #eq(#0, #neg(@y)) -> #false 404.78/291.72 #eq(#0, #pos(@y)) -> #false 404.78/291.72 #eq(#0, #s(@y)) -> #false 404.78/291.72 #eq(#neg(@x), #0) -> #false 404.78/291.72 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #0) -> #false 404.78/291.72 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#s(@x), #0) -> #false 404.78/291.72 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.72 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.72 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.72 #eq(nil, nil) -> #true 404.78/291.72 404.78/291.72 Types: 404.78/291.72 #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 #and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 eq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#3 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 nil :: :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#2 :: :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #false :: #false:#true 404.78/291.72 #true :: #false:#true 404.78/291.72 nub :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 nub#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #0 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 hole_#false:#true1_4 :: #false:#true 404.78/291.72 hole_:::nil:#0:#neg:#pos:#s2_4 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4 :: Nat -> :::nil:#0:#neg:#pos:#s 404.78/291.72 404.78/291.72 404.78/291.72 Generator Equations: 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(0) <=> nil 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#neg:#pos:#s3_4(x)) 404.78/291.72 404.78/291.72 404.78/291.72 The following defined symbols remain to be analysed: 404.78/291.72 #eq, eq, eq#1, nub, nub#1, remove, remove#1 404.78/291.72 404.78/291.72 They will be analysed ascendingly in the following order: 404.78/291.72 eq = eq#1 404.78/291.72 eq < remove#1 404.78/291.72 nub = nub#1 404.78/291.72 remove < nub#1 404.78/291.72 remove = remove#1 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (19) RewriteLemmaProof (LOWER BOUND(ID)) 404.78/291.72 Proved the following rewrite lemma: 404.78/291.72 #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n5_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n5_4)) -> #false, rt in Omega(0) 404.78/291.72 404.78/291.72 Induction Base: 404.78/291.72 #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, 0)), gen_:::nil:#0:#neg:#pos:#s3_4(0)) ->_R^Omega(0) 404.78/291.72 #false 404.78/291.72 404.78/291.72 Induction Step: 404.78/291.72 #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, +(n5_4, 1))), gen_:::nil:#0:#neg:#pos:#s3_4(+(n5_4, 1))) ->_R^Omega(0) 404.78/291.72 #and(#eq(nil, nil), #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n5_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n5_4))) ->_R^Omega(0) 404.78/291.72 #and(#true, #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n5_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n5_4))) ->_IH 404.78/291.72 #and(#true, #false) ->_R^Omega(0) 404.78/291.72 #false 404.78/291.72 404.78/291.72 We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (20) 404.78/291.72 Obligation: 404.78/291.72 Innermost TRS: 404.78/291.72 Rules: 404.78/291.72 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.72 and(@x, @y) -> #and(@x, @y) 404.78/291.72 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.72 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.72 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.72 eq#2(::(@y, @ys)) -> #false 404.78/291.72 eq#2(nil) -> #true 404.78/291.72 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.72 eq#3(nil, @x, @xs) -> #false 404.78/291.72 nub(@l) -> nub#1(@l) 404.78/291.72 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.72 nub#1(nil) -> nil 404.78/291.72 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.72 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.72 remove#1(nil, @x) -> nil 404.78/291.72 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.72 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.72 #and(#false, #false) -> #false 404.78/291.72 #and(#false, #true) -> #false 404.78/291.72 #and(#true, #false) -> #false 404.78/291.72 #and(#true, #true) -> #true 404.78/291.72 #eq(#0, #0) -> #true 404.78/291.72 #eq(#0, #neg(@y)) -> #false 404.78/291.72 #eq(#0, #pos(@y)) -> #false 404.78/291.72 #eq(#0, #s(@y)) -> #false 404.78/291.72 #eq(#neg(@x), #0) -> #false 404.78/291.72 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #0) -> #false 404.78/291.72 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#s(@x), #0) -> #false 404.78/291.72 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.72 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.72 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.72 #eq(nil, nil) -> #true 404.78/291.72 404.78/291.72 Types: 404.78/291.72 #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 #and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 eq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#3 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 nil :: :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#2 :: :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #false :: #false:#true 404.78/291.72 #true :: #false:#true 404.78/291.72 nub :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 nub#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #0 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 hole_#false:#true1_4 :: #false:#true 404.78/291.72 hole_:::nil:#0:#neg:#pos:#s2_4 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4 :: Nat -> :::nil:#0:#neg:#pos:#s 404.78/291.72 404.78/291.72 404.78/291.72 Lemmas: 404.78/291.72 #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n5_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n5_4)) -> #false, rt in Omega(0) 404.78/291.72 404.78/291.72 404.78/291.72 Generator Equations: 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(0) <=> nil 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#neg:#pos:#s3_4(x)) 404.78/291.72 404.78/291.72 404.78/291.72 The following defined symbols remain to be analysed: 404.78/291.72 eq#1, eq, nub, nub#1, remove, remove#1 404.78/291.72 404.78/291.72 They will be analysed ascendingly in the following order: 404.78/291.72 eq = eq#1 404.78/291.72 eq < remove#1 404.78/291.72 nub = nub#1 404.78/291.72 remove < nub#1 404.78/291.72 remove = remove#1 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (21) RewriteLemmaProof (LOWER BOUND(ID)) 404.78/291.72 Proved the following rewrite lemma: 404.78/291.72 eq#1(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n6574117_4)) -> #false, rt in Omega(1 + n6574117_4) 404.78/291.72 404.78/291.72 Induction Base: 404.78/291.72 eq#1(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, 0)), gen_:::nil:#0:#neg:#pos:#s3_4(0)) ->_R^Omega(1) 404.78/291.72 eq#3(gen_:::nil:#0:#neg:#pos:#s3_4(0), nil, gen_:::nil:#0:#neg:#pos:#s3_4(0)) ->_R^Omega(1) 404.78/291.72 #false 404.78/291.72 404.78/291.72 Induction Step: 404.78/291.72 eq#1(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, +(n6574117_4, 1))), gen_:::nil:#0:#neg:#pos:#s3_4(+(n6574117_4, 1))) ->_R^Omega(1) 404.78/291.72 eq#3(gen_:::nil:#0:#neg:#pos:#s3_4(+(n6574117_4, 1)), nil, gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4))) ->_R^Omega(1) 404.78/291.72 and(#equal(nil, nil), eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n6574117_4))) ->_R^Omega(1) 404.78/291.72 and(#eq(nil, nil), eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n6574117_4))) ->_R^Omega(0) 404.78/291.72 and(#true, eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n6574117_4))) ->_R^Omega(1) 404.78/291.72 and(#true, eq#1(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n6574117_4))) ->_IH 404.78/291.72 and(#true, #false) ->_R^Omega(1) 404.78/291.72 #and(#true, #false) ->_R^Omega(0) 404.78/291.72 #false 404.78/291.72 404.78/291.72 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (22) 404.78/291.72 Complex Obligation (BEST) 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (23) 404.78/291.72 Obligation: 404.78/291.72 Proved the lower bound n^1 for the following obligation: 404.78/291.72 404.78/291.72 Innermost TRS: 404.78/291.72 Rules: 404.78/291.72 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.72 and(@x, @y) -> #and(@x, @y) 404.78/291.72 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.72 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.72 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.72 eq#2(::(@y, @ys)) -> #false 404.78/291.72 eq#2(nil) -> #true 404.78/291.72 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.72 eq#3(nil, @x, @xs) -> #false 404.78/291.72 nub(@l) -> nub#1(@l) 404.78/291.72 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.72 nub#1(nil) -> nil 404.78/291.72 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.72 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.72 remove#1(nil, @x) -> nil 404.78/291.72 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.72 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.72 #and(#false, #false) -> #false 404.78/291.72 #and(#false, #true) -> #false 404.78/291.72 #and(#true, #false) -> #false 404.78/291.72 #and(#true, #true) -> #true 404.78/291.72 #eq(#0, #0) -> #true 404.78/291.72 #eq(#0, #neg(@y)) -> #false 404.78/291.72 #eq(#0, #pos(@y)) -> #false 404.78/291.72 #eq(#0, #s(@y)) -> #false 404.78/291.72 #eq(#neg(@x), #0) -> #false 404.78/291.72 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #0) -> #false 404.78/291.72 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#s(@x), #0) -> #false 404.78/291.72 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.72 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.72 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.72 #eq(nil, nil) -> #true 404.78/291.72 404.78/291.72 Types: 404.78/291.72 #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 #and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 eq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#3 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 nil :: :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#2 :: :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #false :: #false:#true 404.78/291.72 #true :: #false:#true 404.78/291.72 nub :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 nub#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #0 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 hole_#false:#true1_4 :: #false:#true 404.78/291.72 hole_:::nil:#0:#neg:#pos:#s2_4 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4 :: Nat -> :::nil:#0:#neg:#pos:#s 404.78/291.72 404.78/291.72 404.78/291.72 Lemmas: 404.78/291.72 #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n5_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n5_4)) -> #false, rt in Omega(0) 404.78/291.72 404.78/291.72 404.78/291.72 Generator Equations: 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(0) <=> nil 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#neg:#pos:#s3_4(x)) 404.78/291.72 404.78/291.72 404.78/291.72 The following defined symbols remain to be analysed: 404.78/291.72 eq#1, eq, nub, nub#1, remove, remove#1 404.78/291.72 404.78/291.72 They will be analysed ascendingly in the following order: 404.78/291.72 eq = eq#1 404.78/291.72 eq < remove#1 404.78/291.72 nub = nub#1 404.78/291.72 remove < nub#1 404.78/291.72 remove = remove#1 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (24) LowerBoundPropagationProof (FINISHED) 404.78/291.72 Propagated lower bound. 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (25) 404.78/291.72 BOUNDS(n^1, INF) 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (26) 404.78/291.72 Obligation: 404.78/291.72 Innermost TRS: 404.78/291.72 Rules: 404.78/291.72 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.72 and(@x, @y) -> #and(@x, @y) 404.78/291.72 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.72 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.72 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.72 eq#2(::(@y, @ys)) -> #false 404.78/291.72 eq#2(nil) -> #true 404.78/291.72 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.72 eq#3(nil, @x, @xs) -> #false 404.78/291.72 nub(@l) -> nub#1(@l) 404.78/291.72 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.72 nub#1(nil) -> nil 404.78/291.72 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.72 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.72 remove#1(nil, @x) -> nil 404.78/291.72 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.72 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.72 #and(#false, #false) -> #false 404.78/291.72 #and(#false, #true) -> #false 404.78/291.72 #and(#true, #false) -> #false 404.78/291.72 #and(#true, #true) -> #true 404.78/291.72 #eq(#0, #0) -> #true 404.78/291.72 #eq(#0, #neg(@y)) -> #false 404.78/291.72 #eq(#0, #pos(@y)) -> #false 404.78/291.72 #eq(#0, #s(@y)) -> #false 404.78/291.72 #eq(#neg(@x), #0) -> #false 404.78/291.72 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #0) -> #false 404.78/291.72 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#s(@x), #0) -> #false 404.78/291.72 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.72 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.72 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.72 #eq(nil, nil) -> #true 404.78/291.72 404.78/291.72 Types: 404.78/291.72 #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 #and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 eq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#3 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 nil :: :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#2 :: :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #false :: #false:#true 404.78/291.72 #true :: #false:#true 404.78/291.72 nub :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 nub#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #0 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 hole_#false:#true1_4 :: #false:#true 404.78/291.72 hole_:::nil:#0:#neg:#pos:#s2_4 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4 :: Nat -> :::nil:#0:#neg:#pos:#s 404.78/291.72 404.78/291.72 404.78/291.72 Lemmas: 404.78/291.72 #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n5_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n5_4)) -> #false, rt in Omega(0) 404.78/291.72 eq#1(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n6574117_4)) -> #false, rt in Omega(1 + n6574117_4) 404.78/291.72 404.78/291.72 404.78/291.72 Generator Equations: 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(0) <=> nil 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#neg:#pos:#s3_4(x)) 404.78/291.72 404.78/291.72 404.78/291.72 The following defined symbols remain to be analysed: 404.78/291.72 eq, nub, nub#1, remove, remove#1 404.78/291.72 404.78/291.72 They will be analysed ascendingly in the following order: 404.78/291.72 eq = eq#1 404.78/291.72 eq < remove#1 404.78/291.72 nub = nub#1 404.78/291.72 remove < nub#1 404.78/291.72 remove = remove#1 404.78/291.72 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (27) RewriteLemmaProof (LOWER BOUND(ID)) 404.78/291.72 Proved the following rewrite lemma: 404.78/291.72 remove#1(gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4), gen_:::nil:#0:#neg:#pos:#s3_4(1)) -> gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4), rt in Omega(1 + n6575220_4) 404.78/291.72 404.78/291.72 Induction Base: 404.78/291.72 remove#1(gen_:::nil:#0:#neg:#pos:#s3_4(0), gen_:::nil:#0:#neg:#pos:#s3_4(1)) ->_R^Omega(1) 404.78/291.72 nil 404.78/291.72 404.78/291.72 Induction Step: 404.78/291.72 remove#1(gen_:::nil:#0:#neg:#pos:#s3_4(+(n6575220_4, 1)), gen_:::nil:#0:#neg:#pos:#s3_4(1)) ->_R^Omega(1) 404.78/291.72 remove#2(eq(gen_:::nil:#0:#neg:#pos:#s3_4(1), nil), gen_:::nil:#0:#neg:#pos:#s3_4(1), nil, gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4)) ->_R^Omega(1) 404.78/291.72 remove#2(eq#1(gen_:::nil:#0:#neg:#pos:#s3_4(1), nil), gen_:::nil:#0:#neg:#pos:#s3_4(1), nil, gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4)) ->_L^Omega(1) 404.78/291.72 remove#2(#false, gen_:::nil:#0:#neg:#pos:#s3_4(1), nil, gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4)) ->_R^Omega(1) 404.78/291.72 ::(nil, remove(gen_:::nil:#0:#neg:#pos:#s3_4(1), gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4))) ->_R^Omega(1) 404.78/291.72 ::(nil, remove#1(gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4), gen_:::nil:#0:#neg:#pos:#s3_4(1))) ->_IH 404.78/291.72 ::(nil, gen_:::nil:#0:#neg:#pos:#s3_4(c6575221_4)) 404.78/291.72 404.78/291.72 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 404.78/291.72 ---------------------------------------- 404.78/291.72 404.78/291.72 (28) 404.78/291.72 Obligation: 404.78/291.72 Innermost TRS: 404.78/291.72 Rules: 404.78/291.72 #equal(@x, @y) -> #eq(@x, @y) 404.78/291.72 and(@x, @y) -> #and(@x, @y) 404.78/291.72 eq(@l1, @l2) -> eq#1(@l1, @l2) 404.78/291.72 eq#1(::(@x, @xs), @l2) -> eq#3(@l2, @x, @xs) 404.78/291.72 eq#1(nil, @l2) -> eq#2(@l2) 404.78/291.72 eq#2(::(@y, @ys)) -> #false 404.78/291.72 eq#2(nil) -> #true 404.78/291.72 eq#3(::(@y, @ys), @x, @xs) -> and(#equal(@x, @y), eq(@xs, @ys)) 404.78/291.72 eq#3(nil, @x, @xs) -> #false 404.78/291.72 nub(@l) -> nub#1(@l) 404.78/291.72 nub#1(::(@x, @xs)) -> ::(@x, nub(remove(@x, @xs))) 404.78/291.72 nub#1(nil) -> nil 404.78/291.72 remove(@x, @l) -> remove#1(@l, @x) 404.78/291.72 remove#1(::(@y, @ys), @x) -> remove#2(eq(@x, @y), @x, @y, @ys) 404.78/291.72 remove#1(nil, @x) -> nil 404.78/291.72 remove#2(#false, @x, @y, @ys) -> ::(@y, remove(@x, @ys)) 404.78/291.72 remove#2(#true, @x, @y, @ys) -> remove(@x, @ys) 404.78/291.72 #and(#false, #false) -> #false 404.78/291.72 #and(#false, #true) -> #false 404.78/291.72 #and(#true, #false) -> #false 404.78/291.72 #and(#true, #true) -> #true 404.78/291.72 #eq(#0, #0) -> #true 404.78/291.72 #eq(#0, #neg(@y)) -> #false 404.78/291.72 #eq(#0, #pos(@y)) -> #false 404.78/291.72 #eq(#0, #s(@y)) -> #false 404.78/291.72 #eq(#neg(@x), #0) -> #false 404.78/291.72 #eq(#neg(@x), #neg(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#neg(@x), #pos(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #0) -> #false 404.78/291.72 #eq(#pos(@x), #neg(@y)) -> #false 404.78/291.72 #eq(#pos(@x), #pos(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(#s(@x), #0) -> #false 404.78/291.72 #eq(#s(@x), #s(@y)) -> #eq(@x, @y) 404.78/291.72 #eq(::(@x_1, @x_2), ::(@y_1, @y_2)) -> #and(#eq(@x_1, @y_1), #eq(@x_2, @y_2)) 404.78/291.72 #eq(::(@x_1, @x_2), nil) -> #false 404.78/291.72 #eq(nil, ::(@y_1, @y_2)) -> #false 404.78/291.72 #eq(nil, nil) -> #true 404.78/291.72 404.78/291.72 Types: 404.78/291.72 #equal :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 #and :: #false:#true -> #false:#true -> #false:#true 404.78/291.72 eq :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 eq#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 :: :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#3 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 nil :: :::nil:#0:#neg:#pos:#s 404.78/291.72 eq#2 :: :::nil:#0:#neg:#pos:#s -> #false:#true 404.78/291.72 #false :: #false:#true 404.78/291.72 #true :: #false:#true 404.78/291.72 nub :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 nub#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#1 :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 remove#2 :: #false:#true -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #0 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 #neg :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #pos :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 #s :: :::nil:#0:#neg:#pos:#s -> :::nil:#0:#neg:#pos:#s 404.78/291.72 hole_#false:#true1_4 :: #false:#true 404.78/291.72 hole_:::nil:#0:#neg:#pos:#s2_4 :: :::nil:#0:#neg:#pos:#s 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4 :: Nat -> :::nil:#0:#neg:#pos:#s 404.78/291.72 404.78/291.72 404.78/291.72 Lemmas: 404.78/291.72 #eq(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n5_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n5_4)) -> #false, rt in Omega(0) 404.78/291.72 eq#1(gen_:::nil:#0:#neg:#pos:#s3_4(+(1, n6574117_4)), gen_:::nil:#0:#neg:#pos:#s3_4(n6574117_4)) -> #false, rt in Omega(1 + n6574117_4) 404.78/291.72 remove#1(gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4), gen_:::nil:#0:#neg:#pos:#s3_4(1)) -> gen_:::nil:#0:#neg:#pos:#s3_4(n6575220_4), rt in Omega(1 + n6575220_4) 404.78/291.72 404.78/291.72 404.78/291.72 Generator Equations: 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(0) <=> nil 404.78/291.72 gen_:::nil:#0:#neg:#pos:#s3_4(+(x, 1)) <=> ::(nil, gen_:::nil:#0:#neg:#pos:#s3_4(x)) 404.78/291.72 404.78/291.72 404.78/291.72 The following defined symbols remain to be analysed: 404.78/291.72 remove, nub, nub#1 404.78/291.72 404.78/291.72 They will be analysed ascendingly in the following order: 404.78/291.72 nub = nub#1 404.78/291.72 remove < nub#1 404.78/291.72 remove = remove#1 404.91/291.77 EOF