/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^3), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^3, INF). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 305 ms] (4) CpxRelTRS (5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxRelTRS (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) typed CpxTrs (9) OrderProof [LOWER BOUND(ID), 0 ms] (10) typed CpxTrs (11) RewriteLemmaProof [LOWER BOUND(ID), 265 ms] (12) BEST (13) proven lower bound (14) LowerBoundPropagationProof [FINISHED, 0 ms] (15) BOUNDS(n^1, INF) (16) typed CpxTrs (17) RewriteLemmaProof [LOWER BOUND(ID), 9 ms] (18) BEST (19) proven lower bound (20) LowerBoundPropagationProof [FINISHED, 0 ms] (21) BOUNDS(n^2, INF) (22) typed CpxTrs (23) RewriteLemmaProof [LOWER BOUND(ID), 1022 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^3, INF) (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 1492 ms] (30) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^3, INF). The TRS R consists of the following rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^3, INF). The TRS R consists of the following rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) The (relative) TRS S consists of the following rules: encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^3, INF). The TRS R consists of the following rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) The (relative) TRS S consists of the following rules: encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^3, INF). The TRS R consists of the following rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) The (relative) TRS S consists of the following rules: encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if ---------------------------------------- (9) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: app, reverse, shuff, if, encArg They will be analysed ascendingly in the following order: app < reverse app < shuff app < encArg reverse < if reverse < encArg shuff = if shuff < encArg if < encArg ---------------------------------------- (10) Obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if Generator Equations: gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0) <=> nil gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(x, 1)) <=> add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(x)) The following defined symbols remain to be analysed: app, reverse, shuff, if, encArg They will be analysed ascendingly in the following order: app < reverse app < shuff app < encArg reverse < if reverse < encArg shuff = if shuff < encArg if < encArg ---------------------------------------- (11) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n4_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n4_0, b)), rt in Omega(1 + n4_0) Induction Base: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) ->_R^Omega(1) gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b) Induction Step: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n4_0, 1)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) ->_R^Omega(1) add(nil, app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n4_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b))) ->_IH add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(b, c5_0))) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (12) Complex Obligation (BEST) ---------------------------------------- (13) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if Generator Equations: gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0) <=> nil gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(x, 1)) <=> add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(x)) The following defined symbols remain to be analysed: app, reverse, shuff, if, encArg They will be analysed ascendingly in the following order: app < reverse app < shuff app < encArg reverse < if reverse < encArg shuff = if shuff < encArg if < encArg ---------------------------------------- (14) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (15) BOUNDS(n^1, INF) ---------------------------------------- (16) Obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if Lemmas: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n4_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n4_0, b)), rt in Omega(1 + n4_0) Generator Equations: gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0) <=> nil gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(x, 1)) <=> add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(x)) The following defined symbols remain to be analysed: reverse, shuff, if, encArg They will be analysed ascendingly in the following order: reverse < if reverse < encArg shuff = if shuff < encArg if < encArg ---------------------------------------- (17) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0), rt in Omega(1 + n1311_0 + n1311_0^2) Induction Base: reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0)) ->_R^Omega(1) nil Induction Step: reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n1311_0, 1))) ->_R^Omega(1) app(reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0)), add(nil, nil)) ->_IH app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(c1312_0), add(nil, nil)) ->_L^Omega(1 + n1311_0) gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n1311_0, +(0, 1))) We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). ---------------------------------------- (18) Complex Obligation (BEST) ---------------------------------------- (19) Obligation: Proved the lower bound n^2 for the following obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if Lemmas: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n4_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n4_0, b)), rt in Omega(1 + n4_0) Generator Equations: gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0) <=> nil gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(x, 1)) <=> add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(x)) The following defined symbols remain to be analysed: reverse, shuff, if, encArg They will be analysed ascendingly in the following order: reverse < if reverse < encArg shuff = if shuff < encArg if < encArg ---------------------------------------- (20) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (21) BOUNDS(n^2, INF) ---------------------------------------- (22) Obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if Lemmas: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n4_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n4_0, b)), rt in Omega(1 + n4_0) reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0), rt in Omega(1 + n1311_0 + n1311_0^2) Generator Equations: gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0) <=> nil gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(x, 1)) <=> add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(x)) The following defined symbols remain to be analysed: if, shuff, encArg They will be analysed ascendingly in the following order: shuff = if shuff < encArg if < encArg ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: shuff(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1866_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> *3_0, rt in Omega(b*n1866_0 + n1866_0 + n1866_0^2 + n1866_0^3) Induction Base: shuff(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) Induction Step: shuff(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n1866_0, 1)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) ->_R^Omega(1) if(null(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n1866_0, 1))), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n1866_0, 1)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b), app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b), add(head(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n1866_0, 1))), nil))) ->_R^Omega(1) if(false, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, n1866_0)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b), app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b), add(head(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, n1866_0))), nil))) ->_R^Omega(1) if(false, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, n1866_0)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b), app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b), add(nil, nil))) ->_L^Omega(1 + b) if(false, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, n1866_0)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(0, 1)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(b, +(0, 1)))) ->_R^Omega(1) shuff(reverse(tail(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, n1866_0)))), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, b))) ->_R^Omega(1) shuff(reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1866_0)), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, b))) ->_L^Omega(1 + n1866_0 + n1866_0^2) shuff(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1866_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(1, b))) ->_IH *3_0 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) Obligation: Proved the lower bound n^3 for the following obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if Lemmas: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n4_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n4_0, b)), rt in Omega(1 + n4_0) reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0), rt in Omega(1 + n1311_0 + n1311_0^2) Generator Equations: gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0) <=> nil gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(x, 1)) <=> add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(x)) The following defined symbols remain to be analysed: shuff, encArg They will be analysed ascendingly in the following order: shuff = if shuff < encArg if < encArg ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^3, INF) ---------------------------------------- (28) Obligation: Innermost TRS: Rules: null(nil) -> true null(add(n, x)) -> false tail(add(n, x)) -> x tail(nil) -> nil head(add(n, x)) -> n app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) reverse(nil) -> nil reverse(add(n, x)) -> app(reverse(x), add(n, nil)) shuffle(x) -> shuff(x, nil) shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) if(true, x, y, z) -> y if(false, x, y, z) -> shuff(reverse(tail(x)), z) encArg(nil) -> nil encArg(true) -> true encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(false) -> false encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_app(x_1, x_2)) -> app(encArg(x_1), encArg(x_2)) encArg(cons_reverse(x_1)) -> reverse(encArg(x_1)) encArg(cons_shuffle(x_1)) -> shuffle(encArg(x_1)) encArg(cons_shuff(x_1, x_2)) -> shuff(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3, x_4)) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) encode_null(x_1) -> null(encArg(x_1)) encode_nil -> nil encode_true -> true encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_false -> false encode_tail(x_1) -> tail(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_app(x_1, x_2) -> app(encArg(x_1), encArg(x_2)) encode_reverse(x_1) -> reverse(encArg(x_1)) encode_shuffle(x_1) -> shuffle(encArg(x_1)) encode_shuff(x_1, x_2) -> shuff(encArg(x_1), encArg(x_2)) encode_if(x_1, x_2, x_3, x_4) -> if(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4)) Types: null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encArg :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if cons_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_null :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_nil :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_true :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_add :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_false :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_tail :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_head :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_app :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_reverse :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuffle :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_shuff :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if encode_if :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if hole_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if1_0 :: nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0 :: Nat -> nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if Lemmas: app(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n4_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n4_0, b)), rt in Omega(1 + n4_0) reverse(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1311_0), rt in Omega(1 + n1311_0 + n1311_0^2) shuff(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n1866_0), gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(b)) -> *3_0, rt in Omega(b*n1866_0 + n1866_0 + n1866_0^2 + n1866_0^3) Generator Equations: gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0) <=> nil gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(x, 1)) <=> add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(x)) The following defined symbols remain to be analysed: if, encArg They will be analysed ascendingly in the following order: shuff = if shuff < encArg if < encArg ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n16297_0)) -> gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n16297_0), rt in Omega(0) Induction Base: encArg(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(0)) ->_R^Omega(0) nil Induction Step: encArg(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(+(n16297_0, 1))) ->_R^Omega(0) add(encArg(nil), encArg(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n16297_0))) ->_R^Omega(0) add(nil, encArg(gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(n16297_0))) ->_IH add(nil, gen_nil:true:add:false:cons_null:cons_tail:cons_head:cons_app:cons_reverse:cons_shuffle:cons_shuff:cons_if2_0(c16298_0)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (30) BOUNDS(1, INF)