/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^3)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^2, n^3). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 226 ms] (4) CpxRelTRS (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxRelTRS (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxWeightedTrs (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CpxTypedWeightedTrs (11) CompletionProof [UPPER BOUND(ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 5 ms] (14) CpxRNTS (15) CompleteCoflocoProof [FINISHED, 2443 ms] (16) BOUNDS(1, n^3) (17) RenamingProof [BOTH BOUNDS(ID, ID), 1 ms] (18) CpxRelTRS (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (20) typed CpxTrs (21) OrderProof [LOWER BOUND(ID), 0 ms] (22) typed CpxTrs (23) RewriteLemmaProof [LOWER BOUND(ID), 268 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^1, INF) (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 9 ms] (30) BEST (31) proven lower bound (32) LowerBoundPropagationProof [FINISHED, 0 ms] (33) BOUNDS(n^2, INF) (34) typed CpxTrs (35) RewriteLemmaProof [LOWER BOUND(ID), 220 ms] (36) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^2, n^3). The TRS R consists of the following rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (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(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^2, n^3). The TRS R consists of the following rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) The (relative) TRS S consists of the following rules: encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Rewrite Strategy: FULL ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^2, n^3). The TRS R consists of the following rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) The (relative) TRS S consists of the following rules: encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Rewrite Strategy: FULL ---------------------------------------- (5) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. As the TRS is a non-duplicating overlay system, we have rc = irc. ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^3). The TRS R consists of the following rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) The (relative) TRS S consists of the following rules: encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Rewrite Strategy: INNERMOST ---------------------------------------- (7) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (8) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). The TRS R consists of the following rules: rev(nil) -> nil [1] rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1] car(.(x, y)) -> x [1] cdr(.(x, y)) -> y [1] null(nil) -> true [1] null(.(x, y)) -> false [1] ++(nil, y) -> y [1] ++(.(x, y), z) -> .(x, ++(y, z)) [1] encArg(nil) -> nil [0] encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encArg(true) -> true [0] encArg(false) -> false [0] encArg(cons_rev(x_1)) -> rev(encArg(x_1)) [0] encArg(cons_car(x_1)) -> car(encArg(x_1)) [0] encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) [0] encArg(cons_null(x_1)) -> null(encArg(x_1)) [0] encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0] encode_rev(x_1) -> rev(encArg(x_1)) [0] encode_nil -> nil [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0] encode_car(x_1) -> car(encArg(x_1)) [0] encode_cdr(x_1) -> cdr(encArg(x_1)) [0] encode_null(x_1) -> null(encArg(x_1)) [0] encode_true -> true [0] encode_false -> false [0] Rewrite Strategy: INNERMOST ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: rev(nil) -> nil [1] rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1] car(.(x, y)) -> x [1] cdr(.(x, y)) -> y [1] null(nil) -> true [1] null(.(x, y)) -> false [1] ++(nil, y) -> y [1] ++(.(x, y), z) -> .(x, ++(y, z)) [1] encArg(nil) -> nil [0] encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encArg(true) -> true [0] encArg(false) -> false [0] encArg(cons_rev(x_1)) -> rev(encArg(x_1)) [0] encArg(cons_car(x_1)) -> car(encArg(x_1)) [0] encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) [0] encArg(cons_null(x_1)) -> null(encArg(x_1)) [0] encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0] encode_rev(x_1) -> rev(encArg(x_1)) [0] encode_nil -> nil [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0] encode_car(x_1) -> car(encArg(x_1)) [0] encode_cdr(x_1) -> cdr(encArg(x_1)) [0] encode_null(x_1) -> null(encArg(x_1)) [0] encode_true -> true [0] encode_false -> false [0] The TRS has the following type information: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ Rewrite Strategy: INNERMOST ---------------------------------------- (11) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: encArg(v0) -> null_encArg [0] encode_rev(v0) -> null_encode_rev [0] encode_nil -> null_encode_nil [0] encode_.(v0, v1) -> null_encode_. [0] encode_++(v0, v1) -> null_encode_++ [0] encode_car(v0) -> null_encode_car [0] encode_cdr(v0) -> null_encode_cdr [0] encode_null(v0) -> null_encode_null [0] encode_true -> null_encode_true [0] encode_false -> null_encode_false [0] rev(v0) -> null_rev [0] car(v0) -> null_car [0] cdr(v0) -> null_cdr [0] null(v0) -> null_null [0] ++(v0, v1) -> null_++ [0] And the following fresh constants: null_encArg, null_encode_rev, null_encode_nil, null_encode_., null_encode_++, null_encode_car, null_encode_cdr, null_encode_null, null_encode_true, null_encode_false, null_rev, null_car, null_cdr, null_null, null_++ ---------------------------------------- (12) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: rev(nil) -> nil [1] rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1] car(.(x, y)) -> x [1] cdr(.(x, y)) -> y [1] null(nil) -> true [1] null(.(x, y)) -> false [1] ++(nil, y) -> y [1] ++(.(x, y), z) -> .(x, ++(y, z)) [1] encArg(nil) -> nil [0] encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encArg(true) -> true [0] encArg(false) -> false [0] encArg(cons_rev(x_1)) -> rev(encArg(x_1)) [0] encArg(cons_car(x_1)) -> car(encArg(x_1)) [0] encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) [0] encArg(cons_null(x_1)) -> null(encArg(x_1)) [0] encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0] encode_rev(x_1) -> rev(encArg(x_1)) [0] encode_nil -> nil [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0] encode_car(x_1) -> car(encArg(x_1)) [0] encode_cdr(x_1) -> cdr(encArg(x_1)) [0] encode_null(x_1) -> null(encArg(x_1)) [0] encode_true -> true [0] encode_false -> false [0] encArg(v0) -> null_encArg [0] encode_rev(v0) -> null_encode_rev [0] encode_nil -> null_encode_nil [0] encode_.(v0, v1) -> null_encode_. [0] encode_++(v0, v1) -> null_encode_++ [0] encode_car(v0) -> null_encode_car [0] encode_cdr(v0) -> null_encode_cdr [0] encode_null(v0) -> null_encode_null [0] encode_true -> null_encode_true [0] encode_false -> null_encode_false [0] rev(v0) -> null_rev [0] car(v0) -> null_car [0] cdr(v0) -> null_cdr [0] null(v0) -> null_null [0] ++(v0, v1) -> null_++ [0] The TRS has the following type information: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ null_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++:null_encArg:null_encode_rev:null_encode_nil:null_encode_.:null_encode_++:null_encode_car:null_encode_cdr:null_encode_null:null_encode_true:null_encode_false:null_rev:null_car:null_cdr:null_null:null_++ Rewrite Strategy: INNERMOST ---------------------------------------- (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: nil => 1 true => 2 false => 0 null_encArg => 0 null_encode_rev => 0 null_encode_nil => 0 null_encode_. => 0 null_encode_++ => 0 null_encode_car => 0 null_encode_cdr => 0 null_encode_null => 0 null_encode_true => 0 null_encode_false => 0 null_rev => 0 null_car => 0 null_cdr => 0 null_null => 0 null_++ => 0 ---------------------------------------- (14) Obligation: Complexity RNTS consisting of the following rules: ++(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 1 ++(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 ++(z', z'') -{ 1 }-> 1 + x + ++(y, z) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0 car(z') -{ 1 }-> x :|: z' = 1 + x + y, x >= 0, y >= 0 car(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 cdr(z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0 cdr(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encArg(z') -{ 0 }-> rev(encArg(x_1)) :|: x_1 >= 0, z' = 1 + x_1 encArg(z') -{ 0 }-> null(encArg(x_1)) :|: x_1 >= 0, z' = 1 + x_1 encArg(z') -{ 0 }-> cdr(encArg(x_1)) :|: x_1 >= 0, z' = 1 + x_1 encArg(z') -{ 0 }-> car(encArg(x_1)) :|: x_1 >= 0, z' = 1 + x_1 encArg(z') -{ 0 }-> 2 :|: z' = 2 encArg(z') -{ 0 }-> 1 :|: z' = 1 encArg(z') -{ 0 }-> 0 :|: z' = 0 encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encArg(z') -{ 0 }-> ++(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2 encArg(z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2 encode_++(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 encode_++(z', z'') -{ 0 }-> ++(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2 encode_.(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 encode_.(z', z'') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2 encode_car(z') -{ 0 }-> car(encArg(x_1)) :|: x_1 >= 0, z' = x_1 encode_car(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encode_cdr(z') -{ 0 }-> cdr(encArg(x_1)) :|: x_1 >= 0, z' = x_1 encode_cdr(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encode_false -{ 0 }-> 0 :|: encode_nil -{ 0 }-> 1 :|: encode_nil -{ 0 }-> 0 :|: encode_null(z') -{ 0 }-> null(encArg(x_1)) :|: x_1 >= 0, z' = x_1 encode_null(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encode_rev(z') -{ 0 }-> rev(encArg(x_1)) :|: x_1 >= 0, z' = x_1 encode_rev(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encode_true -{ 0 }-> 2 :|: encode_true -{ 0 }-> 0 :|: null(z') -{ 1 }-> 2 :|: z' = 1 null(z') -{ 1 }-> 0 :|: z' = 1 + x + y, x >= 0, y >= 0 null(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 rev(z') -{ 1 }-> 1 :|: z' = 1 rev(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 rev(z') -{ 1 }-> ++(rev(y), 1 + x + 1) :|: z' = 1 + x + y, x >= 0, y >= 0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (15) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V, V10),0,[rev(V, Out)],[V >= 0]). eq(start(V, V10),0,[car(V, Out)],[V >= 0]). eq(start(V, V10),0,[cdr(V, Out)],[V >= 0]). eq(start(V, V10),0,[null(V, Out)],[V >= 0]). eq(start(V, V10),0,[fun(V, V10, Out)],[V >= 0,V10 >= 0]). eq(start(V, V10),0,[encArg(V, Out)],[V >= 0]). eq(start(V, V10),0,[fun1(V, Out)],[V >= 0]). eq(start(V, V10),0,[fun2(Out)],[]). eq(start(V, V10),0,[fun3(V, V10, Out)],[V >= 0,V10 >= 0]). eq(start(V, V10),0,[fun4(V, V10, Out)],[V >= 0,V10 >= 0]). eq(start(V, V10),0,[fun5(V, Out)],[V >= 0]). eq(start(V, V10),0,[fun6(V, Out)],[V >= 0]). eq(start(V, V10),0,[fun7(V, Out)],[V >= 0]). eq(start(V, V10),0,[fun8(Out)],[]). eq(start(V, V10),0,[fun9(Out)],[]). eq(rev(V, Out),1,[],[Out = 1,V = 1]). eq(rev(V, Out),1,[rev(V1, Ret0),fun(Ret0, 1 + V2 + 1, Ret)],[Out = Ret,V = 1 + V1 + V2,V2 >= 0,V1 >= 0]). eq(car(V, Out),1,[],[Out = V3,V = 1 + V3 + V4,V3 >= 0,V4 >= 0]). eq(cdr(V, Out),1,[],[Out = V5,V = 1 + V5 + V6,V6 >= 0,V5 >= 0]). eq(null(V, Out),1,[],[Out = 2,V = 1]). eq(null(V, Out),1,[],[Out = 0,V = 1 + V7 + V8,V7 >= 0,V8 >= 0]). eq(fun(V, V10, Out),1,[],[Out = V9,V10 = V9,V9 >= 0,V = 1]). eq(fun(V, V10, Out),1,[fun(V12, V13, Ret1)],[Out = 1 + Ret1 + V11,V10 = V13,V13 >= 0,V = 1 + V11 + V12,V11 >= 0,V12 >= 0]). eq(encArg(V, Out),0,[],[Out = 1,V = 1]). eq(encArg(V, Out),0,[encArg(V15, Ret01),encArg(V14, Ret11)],[Out = 1 + Ret01 + Ret11,V15 >= 0,V14 >= 0,V = 1 + V14 + V15]). eq(encArg(V, Out),0,[],[Out = 2,V = 2]). eq(encArg(V, Out),0,[],[Out = 0,V = 0]). eq(encArg(V, Out),0,[encArg(V16, Ret02),rev(Ret02, Ret2)],[Out = Ret2,V16 >= 0,V = 1 + V16]). eq(encArg(V, Out),0,[encArg(V17, Ret03),car(Ret03, Ret3)],[Out = Ret3,V17 >= 0,V = 1 + V17]). eq(encArg(V, Out),0,[encArg(V18, Ret04),cdr(Ret04, Ret4)],[Out = Ret4,V18 >= 0,V = 1 + V18]). eq(encArg(V, Out),0,[encArg(V19, Ret05),null(Ret05, Ret5)],[Out = Ret5,V19 >= 0,V = 1 + V19]). eq(encArg(V, Out),0,[encArg(V21, Ret06),encArg(V20, Ret12),fun(Ret06, Ret12, Ret6)],[Out = Ret6,V21 >= 0,V20 >= 0,V = 1 + V20 + V21]). eq(fun1(V, Out),0,[encArg(V22, Ret07),rev(Ret07, Ret7)],[Out = Ret7,V22 >= 0,V = V22]). eq(fun2(Out),0,[],[Out = 1]). eq(fun3(V, V10, Out),0,[encArg(V24, Ret011),encArg(V23, Ret13)],[Out = 1 + Ret011 + Ret13,V24 >= 0,V = V24,V23 >= 0,V10 = V23]). eq(fun4(V, V10, Out),0,[encArg(V26, Ret08),encArg(V25, Ret14),fun(Ret08, Ret14, Ret8)],[Out = Ret8,V26 >= 0,V = V26,V25 >= 0,V10 = V25]). eq(fun5(V, Out),0,[encArg(V27, Ret09),car(Ret09, Ret9)],[Out = Ret9,V27 >= 0,V = V27]). eq(fun6(V, Out),0,[encArg(V28, Ret010),cdr(Ret010, Ret10)],[Out = Ret10,V28 >= 0,V = V28]). eq(fun7(V, Out),0,[encArg(V29, Ret012),null(Ret012, Ret15)],[Out = Ret15,V29 >= 0,V = V29]). eq(fun8(Out),0,[],[Out = 2]). eq(fun9(Out),0,[],[Out = 0]). eq(encArg(V, Out),0,[],[Out = 0,V30 >= 0,V = V30]). eq(fun1(V, Out),0,[],[Out = 0,V31 >= 0,V = V31]). eq(fun2(Out),0,[],[Out = 0]). eq(fun3(V, V10, Out),0,[],[Out = 0,V33 >= 0,V32 >= 0,V10 = V32,V = V33]). eq(fun4(V, V10, Out),0,[],[Out = 0,V34 >= 0,V35 >= 0,V10 = V35,V = V34]). eq(fun5(V, Out),0,[],[Out = 0,V36 >= 0,V = V36]). eq(fun6(V, Out),0,[],[Out = 0,V37 >= 0,V = V37]). eq(fun7(V, Out),0,[],[Out = 0,V38 >= 0,V = V38]). eq(fun8(Out),0,[],[Out = 0]). eq(rev(V, Out),0,[],[Out = 0,V39 >= 0,V = V39]). eq(car(V, Out),0,[],[Out = 0,V40 >= 0,V = V40]). eq(cdr(V, Out),0,[],[Out = 0,V41 >= 0,V = V41]). eq(null(V, Out),0,[],[Out = 0,V42 >= 0,V = V42]). eq(fun(V, V10, Out),0,[],[Out = 0,V43 >= 0,V44 >= 0,V10 = V44,V = V43]). input_output_vars(rev(V,Out),[V],[Out]). input_output_vars(car(V,Out),[V],[Out]). input_output_vars(cdr(V,Out),[V],[Out]). input_output_vars(null(V,Out),[V],[Out]). input_output_vars(fun(V,V10,Out),[V,V10],[Out]). input_output_vars(encArg(V,Out),[V],[Out]). input_output_vars(fun1(V,Out),[V],[Out]). input_output_vars(fun2(Out),[],[Out]). input_output_vars(fun3(V,V10,Out),[V,V10],[Out]). input_output_vars(fun4(V,V10,Out),[V,V10],[Out]). input_output_vars(fun5(V,Out),[V],[Out]). input_output_vars(fun6(V,Out),[V],[Out]). input_output_vars(fun7(V,Out),[V],[Out]). input_output_vars(fun8(Out),[],[Out]). input_output_vars(fun9(Out),[],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [car/2] 1. non_recursive : [cdr/2] 2. recursive : [fun/3] 3. non_recursive : [null/2] 4. recursive [non_tail] : [rev/2] 5. recursive [non_tail,multiple] : [encArg/2] 6. non_recursive : [fun1/2] 7. non_recursive : [fun2/1] 8. non_recursive : [fun3/3] 9. non_recursive : [fun4/3] 10. non_recursive : [fun5/2] 11. non_recursive : [fun6/2] 12. non_recursive : [fun7/2] 13. non_recursive : [fun8/1] 14. non_recursive : [fun9/1] 15. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into car/2 1. SCC is partially evaluated into cdr/2 2. SCC is partially evaluated into fun/3 3. SCC is partially evaluated into null/2 4. SCC is partially evaluated into rev/2 5. SCC is partially evaluated into encArg/2 6. SCC is partially evaluated into fun1/2 7. SCC is partially evaluated into fun2/1 8. SCC is partially evaluated into fun3/3 9. SCC is partially evaluated into fun4/3 10. SCC is partially evaluated into fun5/2 11. SCC is partially evaluated into fun6/2 12. SCC is partially evaluated into fun7/2 13. SCC is partially evaluated into fun8/1 14. SCC is completely evaluated into other SCCs 15. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations car/2 * CE 19 is refined into CE [54] * CE 20 is refined into CE [55] ### Cost equations --> "Loop" of car/2 * CEs [54] --> Loop 29 * CEs [55] --> Loop 30 ### Ranking functions of CR car(V,Out) #### Partial ranking functions of CR car(V,Out) ### Specialization of cost equations cdr/2 * CE 21 is refined into CE [56] * CE 22 is refined into CE [57] ### Cost equations --> "Loop" of cdr/2 * CEs [56] --> Loop 31 * CEs [57] --> Loop 32 ### Ranking functions of CR cdr(V,Out) #### Partial ranking functions of CR cdr(V,Out) ### Specialization of cost equations fun/3 * CE 28 is refined into CE [58] * CE 26 is refined into CE [59] * CE 27 is refined into CE [60] ### Cost equations --> "Loop" of fun/3 * CEs [60] --> Loop 33 * CEs [58] --> Loop 34 * CEs [59] --> Loop 35 ### Ranking functions of CR fun(V,V10,Out) * RF of phase [33]: [V] #### Partial ranking functions of CR fun(V,V10,Out) * Partial RF of phase [33]: - RF of loop [33:1]: V ### Specialization of cost equations null/2 * CE 24 is refined into CE [61] * CE 25 is refined into CE [62] * CE 23 is refined into CE [63] ### Cost equations --> "Loop" of null/2 * CEs [61,62] --> Loop 36 * CEs [63] --> Loop 37 ### Ranking functions of CR null(V,Out) #### Partial ranking functions of CR null(V,Out) ### Specialization of cost equations rev/2 * CE 18 is refined into CE [64] * CE 16 is refined into CE [65] * CE 17 is refined into CE [66,67,68,69] ### Cost equations --> "Loop" of rev/2 * CEs [69] --> Loop 38 * CEs [68] --> Loop 39 * CEs [66] --> Loop 40 * CEs [67] --> Loop 41 * CEs [64] --> Loop 42 * CEs [65] --> Loop 43 ### Ranking functions of CR rev(V,Out) * RF of phase [38,39,40]: [V] * RF of phase [41]: [V] #### Partial ranking functions of CR rev(V,Out) * Partial RF of phase [38,39,40]: - RF of loop [38:1,39:1,40:1]: V * Partial RF of phase [41]: - RF of loop [41:1]: V ### Specialization of cost equations encArg/2 * CE 32 is refined into CE [70] * CE 31 is refined into CE [71] * CE 29 is refined into CE [72] * CE 30 is refined into CE [73] * CE 37 is refined into CE [74,75,76,77] * CE 33 is refined into CE [78,79,80] * CE 34 is refined into CE [81,82] * CE 35 is refined into CE [83,84] * CE 36 is refined into CE [85,86] ### Cost equations --> "Loop" of encArg/2 * CEs [80] --> Loop 44 * CEs [82,84] --> Loop 45 * CEs [85] --> Loop 46 * CEs [78] --> Loop 47 * CEs [79,81,83,86] --> Loop 48 * CEs [77] --> Loop 49 * CEs [73] --> Loop 50 * CEs [76] --> Loop 51 * CEs [74] --> Loop 52 * CEs [75] --> Loop 53 * CEs [70] --> Loop 54 * CEs [71] --> Loop 55 * CEs [72] --> Loop 56 ### Ranking functions of CR encArg(V,Out) * RF of phase [44,45,46,47,48,49,50,51,52,53]: [V] #### Partial ranking functions of CR encArg(V,Out) * Partial RF of phase [44,45,46,47,48,49,50,51,52,53]: - RF of loop [44:1,45:1,46:1,47:1,48:1,49:1,49:2,50:1,50:2,51:1,51:2,52:1,52:2,53:1,53:2]: V ### Specialization of cost equations fun1/2 * CE 38 is refined into CE [87,88,89,90,91,92] * CE 39 is refined into CE [93] ### Cost equations --> "Loop" of fun1/2 * CEs [87] --> Loop 57 * CEs [89,91] --> Loop 58 * CEs [88,90,92,93] --> Loop 59 ### Ranking functions of CR fun1(V,Out) #### Partial ranking functions of CR fun1(V,Out) ### Specialization of cost equations fun2/1 * CE 40 is refined into CE [94] * CE 41 is refined into CE [95] ### Cost equations --> "Loop" of fun2/1 * CEs [94] --> Loop 60 * CEs [95] --> Loop 61 ### Ranking functions of CR fun2(Out) #### Partial ranking functions of CR fun2(Out) ### Specialization of cost equations fun3/3 * CE 42 is refined into CE [96,97,98,99,100,101,102,103,104] * CE 43 is refined into CE [105] ### Cost equations --> "Loop" of fun3/3 * CEs [104] --> Loop 62 * CEs [105] --> Loop 63 * CEs [97] --> Loop 64 * CEs [102,103] --> Loop 65 * CEs [98,101] --> Loop 66 * CEs [96,99,100] --> Loop 67 ### Ranking functions of CR fun3(V,V10,Out) #### Partial ranking functions of CR fun3(V,V10,Out) ### Specialization of cost equations fun4/3 * CE 44 is refined into CE [106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129] * CE 45 is refined into CE [130] ### Cost equations --> "Loop" of fun4/3 * CEs [112] --> Loop 68 * CEs [113] --> Loop 69 * CEs [106,110] --> Loop 70 * CEs [111,128] --> Loop 71 * CEs [125] --> Loop 72 * CEs [109,116,117,120,123,126] --> Loop 73 * CEs [108,119,122] --> Loop 74 * CEs [107,114,115,118,121,124,127,129,130] --> Loop 75 ### Ranking functions of CR fun4(V,V10,Out) #### Partial ranking functions of CR fun4(V,V10,Out) ### Specialization of cost equations fun5/2 * CE 46 is refined into CE [131,132,133,134,135] * CE 47 is refined into CE [136] ### Cost equations --> "Loop" of fun5/2 * CEs [131,135,136] --> Loop 76 * CEs [132,133,134] --> Loop 77 ### Ranking functions of CR fun5(V,Out) #### Partial ranking functions of CR fun5(V,Out) ### Specialization of cost equations fun6/2 * CE 48 is refined into CE [137,138,139,140,141] * CE 49 is refined into CE [142] ### Cost equations --> "Loop" of fun6/2 * CEs [137,141,142] --> Loop 78 * CEs [138,139,140] --> Loop 79 ### Ranking functions of CR fun6(V,Out) #### Partial ranking functions of CR fun6(V,Out) ### Specialization of cost equations fun7/2 * CE 50 is refined into CE [143,144,145,146] * CE 51 is refined into CE [147] ### Cost equations --> "Loop" of fun7/2 * CEs [143] --> Loop 80 * CEs [144,145,146,147] --> Loop 81 ### Ranking functions of CR fun7(V,Out) #### Partial ranking functions of CR fun7(V,Out) ### Specialization of cost equations fun8/1 * CE 52 is refined into CE [148] * CE 53 is refined into CE [149] ### Cost equations --> "Loop" of fun8/1 * CEs [148] --> Loop 82 * CEs [149] --> Loop 83 ### Ranking functions of CR fun8(Out) #### Partial ranking functions of CR fun8(Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [150,151,152] * CE 2 is refined into CE [153,154] * CE 3 is refined into CE [155,156] * CE 4 is refined into CE [157,158] * CE 5 is refined into CE [159,160,161,162] * CE 6 is refined into CE [163,164,165] * CE 7 is refined into CE [166,167,168] * CE 8 is refined into CE [169,170] * CE 9 is refined into CE [171,172,173,174,175] * CE 10 is refined into CE [176,177,178,179,180] * CE 11 is refined into CE [181,182] * CE 12 is refined into CE [183,184] * CE 13 is refined into CE [185,186] * CE 14 is refined into CE [187,188] * CE 15 is refined into CE [189] ### Cost equations --> "Loop" of start/2 * CEs [150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189] --> Loop 84 ### Ranking functions of CR start(V,V10) #### Partial ranking functions of CR start(V,V10) Computing Bounds ===================================== #### Cost of chains of car(V,Out): * Chain [30]: 0 with precondition: [Out=0,V>=0] * Chain [29]: 1 with precondition: [Out>=0,V>=Out+1] #### Cost of chains of cdr(V,Out): * Chain [32]: 0 with precondition: [Out=0,V>=0] * Chain [31]: 1 with precondition: [Out>=0,V>=Out+1] #### Cost of chains of fun(V,V10,Out): * Chain [[33],35]: 1*it(33)+1 Such that:it(33) =< -V10+Out with precondition: [V+V10=Out+1,V>=2,V10>=0] * Chain [[33],34]: 1*it(33)+0 Such that:it(33) =< Out with precondition: [V10>=0,Out>=1,V>=Out] * Chain [35]: 1 with precondition: [V=1,V10=Out,V10>=0] * Chain [34]: 0 with precondition: [Out=0,V>=0,V10>=0] #### Cost of chains of null(V,Out): * Chain [37]: 1 with precondition: [V=1,Out=2] * Chain [36]: 1 with precondition: [Out=0,V>=0] #### Cost of chains of rev(V,Out): * Chain [[41],[38,39,40],43]: 6*it(38)+1*s(5)+1*s(6)+1 Such that:aux(6) =< V it(38) =< aux(6) aux(2) =< aux(6) s(5) =< it(38)*aux(6) s(6) =< it(38)*aux(2) with precondition: [Out=0,V>=3] * Chain [[41],43]: 1*it(41)+1 Such that:it(41) =< V with precondition: [Out=0,V>=2] * Chain [[41],42]: 1*it(41)+0 Such that:it(41) =< V with precondition: [Out=0,V>=1] * Chain [[38,39,40],43]: 5*it(38)+1*s(5)+1*s(6)+1 Such that:aux(5) =< V it(38) =< aux(5) aux(2) =< aux(5) s(5) =< it(38)*aux(5) s(6) =< it(38)*aux(2) with precondition: [V>=2,Out>=1,V>=Out] * Chain [43]: 1 with precondition: [V=1,Out=1] * Chain [42]: 0 with precondition: [Out=0,V>=0] #### Cost of chains of encArg(V,Out): * Chain [56]: 0 with precondition: [V=1,Out=1] * Chain [55]: 0 with precondition: [V=2,Out=2] * Chain [54]: 0 with precondition: [Out=0,V>=0] * Chain [multiple([44,45,46,47,48,49,50,51,52,53],[[56],[55],[54]])]: 5*it(44)+1*it(51)+1*it(52)+5*s(38)+1*s(39)+1*s(40)+8*s(42)+1*s(43)+1*s(44)+1*s(46)+1*s(47)+0 Such that:aux(22) =< V aux(23) =< V/2 aux(24) =< 2/3*V it(44) =< aux(22) it(49) =< aux(22) it(51) =< aux(22) it(52) =< aux(22) it(51) =< aux(23) it(49) =< aux(24) it(51) =< aux(24) it(52) =< aux(24) aux(8) =< aux(22) aux(9) =< aux(22)+1 s(45) =< it(44)*aux(9) s(41) =< it(44)*aux(8) s(47) =< it(51)*aux(8) s(46) =< it(49)*aux(8) s(42) =< s(45) s(31) =< aux(9) s(43) =< s(42)*aux(9) s(44) =< s(42)*s(31) s(38) =< s(41) s(39) =< s(38)*aux(22) s(40) =< s(38)*aux(8) with precondition: [V>=1,Out>=0,V>=Out] #### Cost of chains of fun1(V,Out): * Chain [59]: 13*s(71)+1*s(73)+1*s(74)+1*s(79)+1*s(80)+8*s(81)+1*s(83)+1*s(84)+5*s(85)+1*s(86)+1*s(87)+1*s(91)+1*s(92)+8*s(94)+1*s(96)+1*s(97)+1 Such that:s(93) =< 2 aux(25) =< V s(69) =< V/2 s(70) =< 2/3*V s(94) =< s(93) s(95) =< s(93) s(96) =< s(94)*s(93) s(97) =< s(94)*s(95) s(71) =< aux(25) s(75) =< aux(25) s(91) =< s(71)*aux(25) s(92) =< s(71)*s(75) s(72) =< aux(25) s(73) =< aux(25) s(74) =< aux(25) s(73) =< s(69) s(72) =< s(70) s(73) =< s(70) s(74) =< s(70) s(76) =< aux(25)+1 s(77) =< s(71)*s(76) s(78) =< s(71)*s(75) s(79) =< s(73)*s(75) s(80) =< s(72)*s(75) s(81) =< s(77) s(82) =< s(76) s(83) =< s(81)*s(76) s(84) =< s(81)*s(82) s(85) =< s(78) s(86) =< s(85)*aux(25) s(87) =< s(85)*s(75) with precondition: [Out=0,V>=0] * Chain [58]: 10*s(106)+1*s(108)+1*s(109)+1*s(114)+1*s(115)+8*s(116)+1*s(118)+1*s(119)+5*s(120)+1*s(121)+1*s(122)+1*s(126)+1*s(127)+5*s(129)+1*s(131)+1*s(132)+1 Such that:s(128) =< 2 aux(26) =< V s(104) =< V/2 s(105) =< 2/3*V s(129) =< s(128) s(130) =< s(128) s(131) =< s(129)*s(128) s(132) =< s(129)*s(130) s(106) =< aux(26) s(110) =< aux(26) s(126) =< s(106)*aux(26) s(127) =< s(106)*s(110) s(107) =< aux(26) s(108) =< aux(26) s(109) =< aux(26) s(108) =< s(104) s(107) =< s(105) s(108) =< s(105) s(109) =< s(105) s(111) =< aux(26)+1 s(112) =< s(106)*s(111) s(113) =< s(106)*s(110) s(114) =< s(108)*s(110) s(115) =< s(107)*s(110) s(116) =< s(112) s(117) =< s(111) s(118) =< s(116)*s(111) s(119) =< s(116)*s(117) s(120) =< s(113) s(121) =< s(120)*aux(26) s(122) =< s(120)*s(110) with precondition: [V>=2,Out>=1,V>=Out] * Chain [57]: 5*s(136)+1*s(138)+1*s(139)+1*s(144)+1*s(145)+8*s(146)+1*s(148)+1*s(149)+5*s(150)+1*s(151)+1*s(152)+1 Such that:s(133) =< V s(134) =< V/2 s(135) =< 2/3*V s(136) =< s(133) s(137) =< s(133) s(138) =< s(133) s(139) =< s(133) s(138) =< s(134) s(137) =< s(135) s(138) =< s(135) s(139) =< s(135) s(140) =< s(133) s(141) =< s(133)+1 s(142) =< s(136)*s(141) s(143) =< s(136)*s(140) s(144) =< s(138)*s(140) s(145) =< s(137)*s(140) s(146) =< s(142) s(147) =< s(141) s(148) =< s(146)*s(141) s(149) =< s(146)*s(147) s(150) =< s(143) s(151) =< s(150)*s(133) s(152) =< s(150)*s(140) with precondition: [Out=1,V>=1] #### Cost of chains of fun2(Out): * Chain [61]: 0 with precondition: [Out=0] * Chain [60]: 0 with precondition: [Out=1] #### Cost of chains of fun3(V,V10,Out): * Chain [67]: 5*s(156)+1*s(158)+1*s(159)+1*s(164)+1*s(165)+8*s(166)+1*s(168)+1*s(169)+5*s(170)+1*s(171)+1*s(172)+10*s(176)+2*s(178)+2*s(179)+2*s(184)+2*s(185)+16*s(186)+2*s(188)+2*s(189)+10*s(190)+2*s(191)+2*s(192)+0 Such that:s(153) =< V s(154) =< V/2 s(155) =< 2/3*V aux(27) =< V10 aux(28) =< V10/2 aux(29) =< 2/3*V10 s(176) =< aux(27) s(177) =< aux(27) s(178) =< aux(27) s(179) =< aux(27) s(178) =< aux(28) s(177) =< aux(29) s(178) =< aux(29) s(179) =< aux(29) s(180) =< aux(27) s(181) =< aux(27)+1 s(182) =< s(176)*s(181) s(183) =< s(176)*s(180) s(184) =< s(178)*s(180) s(185) =< s(177)*s(180) s(186) =< s(182) s(187) =< s(181) s(188) =< s(186)*s(181) s(189) =< s(186)*s(187) s(190) =< s(183) s(191) =< s(190)*aux(27) s(192) =< s(190)*s(180) s(156) =< s(153) s(157) =< s(153) s(158) =< s(153) s(159) =< s(153) s(158) =< s(154) s(157) =< s(155) s(158) =< s(155) s(159) =< s(155) s(160) =< s(153) s(161) =< s(153)+1 s(162) =< s(156)*s(161) s(163) =< s(156)*s(160) s(164) =< s(158)*s(160) s(165) =< s(157)*s(160) s(166) =< s(162) s(167) =< s(161) s(168) =< s(166)*s(161) s(169) =< s(166)*s(167) s(170) =< s(163) s(171) =< s(170)*s(153) s(172) =< s(170)*s(160) with precondition: [V>=1,V10>=1,Out>=1,V+V10+1>=Out] * Chain [66]: 5*s(216)+1*s(218)+1*s(219)+1*s(224)+1*s(225)+8*s(226)+1*s(228)+1*s(229)+5*s(230)+1*s(231)+1*s(232)+0 Such that:s(213) =< V s(214) =< V/2 s(215) =< 2/3*V s(216) =< s(213) s(217) =< s(213) s(218) =< s(213) s(219) =< s(213) s(218) =< s(214) s(217) =< s(215) s(218) =< s(215) s(219) =< s(215) s(220) =< s(213) s(221) =< s(213)+1 s(222) =< s(216)*s(221) s(223) =< s(216)*s(220) s(224) =< s(218)*s(220) s(225) =< s(217)*s(220) s(226) =< s(222) s(227) =< s(221) s(228) =< s(226)*s(221) s(229) =< s(226)*s(227) s(230) =< s(223) s(231) =< s(230)*s(213) s(232) =< s(230)*s(220) with precondition: [V>=1,V10>=0,Out>=1,V+1>=Out] * Chain [65]: 5*s(236)+1*s(238)+1*s(239)+1*s(244)+1*s(245)+8*s(246)+1*s(248)+1*s(249)+5*s(250)+1*s(251)+1*s(252)+0 Such that:s(233) =< V10 s(234) =< V10/2 s(235) =< 2/3*V10 s(236) =< s(233) s(237) =< s(233) s(238) =< s(233) s(239) =< s(233) s(238) =< s(234) s(237) =< s(235) s(238) =< s(235) s(239) =< s(235) s(240) =< s(233) s(241) =< s(233)+1 s(242) =< s(236)*s(241) s(243) =< s(236)*s(240) s(244) =< s(238)*s(240) s(245) =< s(237)*s(240) s(246) =< s(242) s(247) =< s(241) s(248) =< s(246)*s(241) s(249) =< s(246)*s(247) s(250) =< s(243) s(251) =< s(250)*s(233) s(252) =< s(250)*s(240) with precondition: [V>=0,V10>=1,Out>=1,V10+1>=Out] * Chain [64]: 5*s(256)+1*s(258)+1*s(259)+1*s(264)+1*s(265)+8*s(266)+1*s(268)+1*s(269)+5*s(270)+1*s(271)+1*s(272)+0 Such that:s(253) =< V s(254) =< V/2 s(255) =< 2/3*V s(256) =< s(253) s(257) =< s(253) s(258) =< s(253) s(259) =< s(253) s(258) =< s(254) s(257) =< s(255) s(258) =< s(255) s(259) =< s(255) s(260) =< s(253) s(261) =< s(253)+1 s(262) =< s(256)*s(261) s(263) =< s(256)*s(260) s(264) =< s(258)*s(260) s(265) =< s(257)*s(260) s(266) =< s(262) s(267) =< s(261) s(268) =< s(266)*s(261) s(269) =< s(266)*s(267) s(270) =< s(263) s(271) =< s(270)*s(253) s(272) =< s(270)*s(260) with precondition: [V10=2,V>=1,Out>=3,V+3>=Out] * Chain [63]: 0 with precondition: [Out=0,V>=0,V10>=0] * Chain [62]: 0 with precondition: [Out=1,V>=0,V10>=0] #### Cost of chains of fun4(V,V10,Out): * Chain [75]: 15*s(336)+3*s(338)+3*s(339)+3*s(344)+3*s(345)+24*s(346)+3*s(348)+3*s(349)+15*s(350)+3*s(351)+3*s(352)+15*s(356)+3*s(358)+3*s(359)+3*s(364)+3*s(365)+24*s(366)+3*s(368)+3*s(369)+15*s(370)+3*s(371)+3*s(372)+1 Such that:aux(33) =< V aux(34) =< V/2 aux(35) =< 2/3*V aux(36) =< V10 aux(37) =< V10/2 aux(38) =< 2/3*V10 s(356) =< aux(36) s(357) =< aux(36) s(358) =< aux(36) s(359) =< aux(36) s(358) =< aux(37) s(357) =< aux(38) s(358) =< aux(38) s(359) =< aux(38) s(360) =< aux(36) s(361) =< aux(36)+1 s(362) =< s(356)*s(361) s(363) =< s(356)*s(360) s(364) =< s(358)*s(360) s(365) =< s(357)*s(360) s(366) =< s(362) s(367) =< s(361) s(368) =< s(366)*s(361) s(369) =< s(366)*s(367) s(370) =< s(363) s(371) =< s(370)*aux(36) s(372) =< s(370)*s(360) s(336) =< aux(33) s(337) =< aux(33) s(338) =< aux(33) s(339) =< aux(33) s(338) =< aux(34) s(337) =< aux(35) s(338) =< aux(35) s(339) =< aux(35) s(340) =< aux(33) s(341) =< aux(33)+1 s(342) =< s(336)*s(341) s(343) =< s(336)*s(340) s(344) =< s(338)*s(340) s(345) =< s(337)*s(340) s(346) =< s(342) s(347) =< s(341) s(348) =< s(346)*s(341) s(349) =< s(346)*s(347) s(350) =< s(343) s(351) =< s(350)*aux(33) s(352) =< s(350)*s(340) with precondition: [Out=0,V>=0,V10>=0] * Chain [74]: 6*s(456)+1*s(458)+1*s(459)+1*s(464)+1*s(465)+8*s(466)+1*s(468)+1*s(469)+5*s(470)+1*s(471)+1*s(472)+10*s(476)+2*s(478)+2*s(479)+2*s(484)+2*s(485)+16*s(486)+2*s(488)+2*s(489)+10*s(490)+2*s(491)+2*s(492)+2*s(514)+1 Such that:aux(39) =< V s(454) =< V/2 s(455) =< 2/3*V aux(40) =< 1 aux(41) =< V10 aux(42) =< V10/2 aux(43) =< 2/3*V10 s(514) =< aux(40) s(476) =< aux(41) s(477) =< aux(41) s(478) =< aux(41) s(479) =< aux(41) s(478) =< aux(42) s(477) =< aux(43) s(478) =< aux(43) s(479) =< aux(43) s(480) =< aux(41) s(481) =< aux(41)+1 s(482) =< s(476)*s(481) s(483) =< s(476)*s(480) s(484) =< s(478)*s(480) s(485) =< s(477)*s(480) s(486) =< s(482) s(487) =< s(481) s(488) =< s(486)*s(481) s(489) =< s(486)*s(487) s(490) =< s(483) s(491) =< s(490)*aux(41) s(492) =< s(490)*s(480) s(456) =< aux(39) s(457) =< aux(39) s(458) =< aux(39) s(459) =< aux(39) s(458) =< s(454) s(457) =< s(455) s(458) =< s(455) s(459) =< s(455) s(460) =< aux(39) s(461) =< aux(39)+1 s(462) =< s(456)*s(461) s(463) =< s(456)*s(460) s(464) =< s(458)*s(460) s(465) =< s(457)*s(460) s(466) =< s(462) s(467) =< s(461) s(468) =< s(466)*s(461) s(469) =< s(466)*s(467) s(470) =< s(463) s(471) =< s(470)*aux(39) s(472) =< s(470)*s(460) with precondition: [V>=2,V10>=1,Out>=1,V+V10>=Out+1] * Chain [73]: 18*s(519)+3*s(521)+3*s(522)+3*s(527)+3*s(528)+24*s(529)+3*s(531)+3*s(532)+15*s(533)+3*s(534)+3*s(535)+10*s(539)+2*s(541)+2*s(542)+2*s(547)+2*s(548)+16*s(549)+2*s(551)+2*s(552)+10*s(553)+2*s(554)+2*s(555)+3*s(619)+1 Such that:aux(47) =< 2 aux(48) =< V aux(49) =< V/2 aux(50) =< 2/3*V aux(51) =< V10 aux(52) =< V10/2 aux(53) =< 2/3*V10 s(619) =< aux(47) s(539) =< aux(51) s(540) =< aux(51) s(541) =< aux(51) s(542) =< aux(51) s(541) =< aux(52) s(540) =< aux(53) s(541) =< aux(53) s(542) =< aux(53) s(543) =< aux(51) s(544) =< aux(51)+1 s(545) =< s(539)*s(544) s(546) =< s(539)*s(543) s(547) =< s(541)*s(543) s(548) =< s(540)*s(543) s(549) =< s(545) s(550) =< s(544) s(551) =< s(549)*s(544) s(552) =< s(549)*s(550) s(553) =< s(546) s(554) =< s(553)*aux(51) s(555) =< s(553)*s(543) s(519) =< aux(48) s(520) =< aux(48) s(521) =< aux(48) s(522) =< aux(48) s(521) =< aux(49) s(520) =< aux(50) s(521) =< aux(50) s(522) =< aux(50) s(523) =< aux(48) s(524) =< aux(48)+1 s(525) =< s(519)*s(524) s(526) =< s(519)*s(523) s(527) =< s(521)*s(523) s(528) =< s(520)*s(523) s(529) =< s(525) s(530) =< s(524) s(531) =< s(529)*s(524) s(532) =< s(529)*s(530) s(533) =< s(526) s(534) =< s(533)*aux(48) s(535) =< s(533)*s(523) with precondition: [V10>=0,Out>=1,V>=Out] * Chain [72]: 1*s(622)+1 Such that:s(622) =< 1 with precondition: [V=2,Out=1,V10>=0] * Chain [71]: 5*s(626)+1*s(628)+1*s(629)+1*s(634)+1*s(635)+8*s(636)+1*s(638)+1*s(639)+5*s(640)+1*s(641)+1*s(642)+0 Such that:s(623) =< V s(624) =< V/2 s(625) =< 2/3*V s(626) =< s(623) s(627) =< s(623) s(628) =< s(623) s(629) =< s(623) s(628) =< s(624) s(627) =< s(625) s(628) =< s(625) s(629) =< s(625) s(630) =< s(623) s(631) =< s(623)+1 s(632) =< s(626)*s(631) s(633) =< s(626)*s(630) s(634) =< s(628)*s(630) s(635) =< s(627)*s(630) s(636) =< s(632) s(637) =< s(631) s(638) =< s(636)*s(631) s(639) =< s(636)*s(637) s(640) =< s(633) s(641) =< s(640)*s(623) s(642) =< s(640)*s(630) with precondition: [V10=2,Out=0,V>=0] * Chain [70]: 10*s(646)+2*s(648)+2*s(649)+2*s(654)+2*s(655)+16*s(656)+2*s(658)+2*s(659)+10*s(660)+2*s(661)+2*s(662)+5*s(666)+1*s(668)+1*s(669)+1*s(674)+1*s(675)+8*s(676)+1*s(678)+1*s(679)+5*s(680)+1*s(681)+1*s(682)+1 Such that:s(663) =< V10 s(664) =< V10/2 s(665) =< 2/3*V10 aux(54) =< V aux(55) =< V/2 aux(56) =< 2/3*V s(666) =< s(663) s(667) =< s(663) s(668) =< s(663) s(669) =< s(663) s(668) =< s(664) s(667) =< s(665) s(668) =< s(665) s(669) =< s(665) s(670) =< s(663) s(671) =< s(663)+1 s(672) =< s(666)*s(671) s(673) =< s(666)*s(670) s(674) =< s(668)*s(670) s(675) =< s(667)*s(670) s(676) =< s(672) s(677) =< s(671) s(678) =< s(676)*s(671) s(679) =< s(676)*s(677) s(680) =< s(673) s(681) =< s(680)*s(663) s(682) =< s(680)*s(670) s(646) =< aux(54) s(647) =< aux(54) s(648) =< aux(54) s(649) =< aux(54) s(648) =< aux(55) s(647) =< aux(56) s(648) =< aux(56) s(649) =< aux(56) s(650) =< aux(54) s(651) =< aux(54)+1 s(652) =< s(646)*s(651) s(653) =< s(646)*s(650) s(654) =< s(648)*s(650) s(655) =< s(647)*s(650) s(656) =< s(652) s(657) =< s(651) s(658) =< s(656)*s(651) s(659) =< s(656)*s(657) s(660) =< s(653) s(661) =< s(660)*aux(54) s(662) =< s(660)*s(650) with precondition: [V>=1,V10>=1,Out>=0,V10>=Out] * Chain [69]: 6*s(706)+1*s(708)+1*s(709)+1*s(714)+1*s(715)+8*s(716)+1*s(718)+1*s(719)+5*s(720)+1*s(721)+1*s(722)+0 Such that:s(704) =< V/2 s(705) =< 2/3*V aux(57) =< V s(706) =< aux(57) s(707) =< aux(57) s(708) =< aux(57) s(709) =< aux(57) s(708) =< s(704) s(707) =< s(705) s(708) =< s(705) s(709) =< s(705) s(710) =< aux(57) s(711) =< aux(57)+1 s(712) =< s(706)*s(711) s(713) =< s(706)*s(710) s(714) =< s(708)*s(710) s(715) =< s(707)*s(710) s(716) =< s(712) s(717) =< s(711) s(718) =< s(716)*s(711) s(719) =< s(716)*s(717) s(720) =< s(713) s(721) =< s(720)*aux(57) s(722) =< s(720)*s(710) with precondition: [V10=2,Out>=1,V>=Out] * Chain [68]: 6*s(727)+1*s(729)+1*s(730)+1*s(735)+1*s(736)+8*s(737)+1*s(739)+1*s(740)+5*s(741)+1*s(742)+1*s(743)+1 Such that:s(725) =< V/2 s(726) =< 2/3*V aux(58) =< V s(727) =< aux(58) s(728) =< aux(58) s(729) =< aux(58) s(730) =< aux(58) s(729) =< s(725) s(728) =< s(726) s(729) =< s(726) s(730) =< s(726) s(731) =< aux(58) s(732) =< aux(58)+1 s(733) =< s(727)*s(732) s(734) =< s(727)*s(731) s(735) =< s(729)*s(731) s(736) =< s(728)*s(731) s(737) =< s(733) s(738) =< s(732) s(739) =< s(737)*s(732) s(740) =< s(737)*s(738) s(741) =< s(734) s(742) =< s(741)*aux(58) s(743) =< s(741)*s(731) with precondition: [V10=2,Out>=3,V+1>=Out] #### Cost of chains of fun5(V,Out): * Chain [77]: 5*s(913)+1*s(915)+1*s(916)+1*s(921)+1*s(922)+8*s(923)+1*s(925)+1*s(926)+5*s(927)+1*s(928)+1*s(929)+1 Such that:s(910) =< V s(911) =< V/2 s(912) =< 2/3*V s(913) =< s(910) s(914) =< s(910) s(915) =< s(910) s(916) =< s(910) s(915) =< s(911) s(914) =< s(912) s(915) =< s(912) s(916) =< s(912) s(917) =< s(910) s(918) =< s(910)+1 s(919) =< s(913)*s(918) s(920) =< s(913)*s(917) s(921) =< s(915)*s(917) s(922) =< s(914)*s(917) s(923) =< s(919) s(924) =< s(918) s(925) =< s(923)*s(918) s(926) =< s(923)*s(924) s(927) =< s(920) s(928) =< s(927)*s(910) s(929) =< s(927)*s(917) with precondition: [Out>=0,V>=Out+1] * Chain [76]: 5*s(933)+1*s(935)+1*s(936)+1*s(941)+1*s(942)+8*s(943)+1*s(945)+1*s(946)+5*s(947)+1*s(948)+1*s(949)+0 Such that:s(930) =< V s(931) =< V/2 s(932) =< 2/3*V s(933) =< s(930) s(934) =< s(930) s(935) =< s(930) s(936) =< s(930) s(935) =< s(931) s(934) =< s(932) s(935) =< s(932) s(936) =< s(932) s(937) =< s(930) s(938) =< s(930)+1 s(939) =< s(933)*s(938) s(940) =< s(933)*s(937) s(941) =< s(935)*s(937) s(942) =< s(934)*s(937) s(943) =< s(939) s(944) =< s(938) s(945) =< s(943)*s(938) s(946) =< s(943)*s(944) s(947) =< s(940) s(948) =< s(947)*s(930) s(949) =< s(947)*s(937) with precondition: [Out=0,V>=0] #### Cost of chains of fun6(V,Out): * Chain [79]: 5*s(953)+1*s(955)+1*s(956)+1*s(961)+1*s(962)+8*s(963)+1*s(965)+1*s(966)+5*s(967)+1*s(968)+1*s(969)+1 Such that:s(950) =< V s(951) =< V/2 s(952) =< 2/3*V s(953) =< s(950) s(954) =< s(950) s(955) =< s(950) s(956) =< s(950) s(955) =< s(951) s(954) =< s(952) s(955) =< s(952) s(956) =< s(952) s(957) =< s(950) s(958) =< s(950)+1 s(959) =< s(953)*s(958) s(960) =< s(953)*s(957) s(961) =< s(955)*s(957) s(962) =< s(954)*s(957) s(963) =< s(959) s(964) =< s(958) s(965) =< s(963)*s(958) s(966) =< s(963)*s(964) s(967) =< s(960) s(968) =< s(967)*s(950) s(969) =< s(967)*s(957) with precondition: [Out>=0,V>=Out+1] * Chain [78]: 5*s(973)+1*s(975)+1*s(976)+1*s(981)+1*s(982)+8*s(983)+1*s(985)+1*s(986)+5*s(987)+1*s(988)+1*s(989)+0 Such that:s(970) =< V s(971) =< V/2 s(972) =< 2/3*V s(973) =< s(970) s(974) =< s(970) s(975) =< s(970) s(976) =< s(970) s(975) =< s(971) s(974) =< s(972) s(975) =< s(972) s(976) =< s(972) s(977) =< s(970) s(978) =< s(970)+1 s(979) =< s(973)*s(978) s(980) =< s(973)*s(977) s(981) =< s(975)*s(977) s(982) =< s(974)*s(977) s(983) =< s(979) s(984) =< s(978) s(985) =< s(983)*s(978) s(986) =< s(983)*s(984) s(987) =< s(980) s(988) =< s(987)*s(970) s(989) =< s(987)*s(977) with precondition: [Out=0,V>=0] #### Cost of chains of fun7(V,Out): * Chain [81]: 5*s(993)+1*s(995)+1*s(996)+1*s(1001)+1*s(1002)+8*s(1003)+1*s(1005)+1*s(1006)+5*s(1007)+1*s(1008)+1*s(1009)+1 Such that:s(990) =< V s(991) =< V/2 s(992) =< 2/3*V s(993) =< s(990) s(994) =< s(990) s(995) =< s(990) s(996) =< s(990) s(995) =< s(991) s(994) =< s(992) s(995) =< s(992) s(996) =< s(992) s(997) =< s(990) s(998) =< s(990)+1 s(999) =< s(993)*s(998) s(1000) =< s(993)*s(997) s(1001) =< s(995)*s(997) s(1002) =< s(994)*s(997) s(1003) =< s(999) s(1004) =< s(998) s(1005) =< s(1003)*s(998) s(1006) =< s(1003)*s(1004) s(1007) =< s(1000) s(1008) =< s(1007)*s(990) s(1009) =< s(1007)*s(997) with precondition: [Out=0,V>=0] * Chain [80]: 5*s(1013)+1*s(1015)+1*s(1016)+1*s(1021)+1*s(1022)+8*s(1023)+1*s(1025)+1*s(1026)+5*s(1027)+1*s(1028)+1*s(1029)+1 Such that:s(1010) =< V s(1011) =< V/2 s(1012) =< 2/3*V s(1013) =< s(1010) s(1014) =< s(1010) s(1015) =< s(1010) s(1016) =< s(1010) s(1015) =< s(1011) s(1014) =< s(1012) s(1015) =< s(1012) s(1016) =< s(1012) s(1017) =< s(1010) s(1018) =< s(1010)+1 s(1019) =< s(1013)*s(1018) s(1020) =< s(1013)*s(1017) s(1021) =< s(1015)*s(1017) s(1022) =< s(1014)*s(1017) s(1023) =< s(1019) s(1024) =< s(1018) s(1025) =< s(1023)*s(1018) s(1026) =< s(1023)*s(1024) s(1027) =< s(1020) s(1028) =< s(1027)*s(1010) s(1029) =< s(1027)*s(1017) with precondition: [Out=2,V>=1] #### Cost of chains of fun8(Out): * Chain [83]: 0 with precondition: [Out=0] * Chain [82]: 0 with precondition: [Out=2] #### Cost of chains of start(V,V10): * Chain [84]: 159*s(1031)+4*s(1033)+4*s(1034)+25*s(1047)+25*s(1048)+25*s(1053)+25*s(1054)+200*s(1055)+25*s(1057)+25*s(1058)+125*s(1059)+25*s(1060)+25*s(1061)+16*s(1066)+2*s(1068)+2*s(1069)+55*s(1159)+11*s(1161)+11*s(1162)+11*s(1167)+11*s(1168)+88*s(1169)+11*s(1171)+11*s(1172)+55*s(1173)+11*s(1174)+11*s(1175)+3*s(1216)+1 Such that:aux(65) =< 1 aux(66) =< 2 aux(67) =< V aux(68) =< V/2 aux(69) =< 2/3*V aux(70) =< V10 aux(71) =< V10/2 aux(72) =< 2/3*V10 s(1216) =< aux(65) s(1031) =< aux(67) s(1066) =< aux(66) s(1159) =< aux(70) s(1160) =< aux(70) s(1161) =< aux(70) s(1162) =< aux(70) s(1161) =< aux(71) s(1160) =< aux(72) s(1161) =< aux(72) s(1162) =< aux(72) s(1163) =< aux(70) s(1164) =< aux(70)+1 s(1165) =< s(1159)*s(1164) s(1166) =< s(1159)*s(1163) s(1167) =< s(1161)*s(1163) s(1168) =< s(1160)*s(1163) s(1169) =< s(1165) s(1170) =< s(1164) s(1171) =< s(1169)*s(1164) s(1172) =< s(1169)*s(1170) s(1173) =< s(1166) s(1174) =< s(1173)*aux(70) s(1175) =< s(1173)*s(1163) s(1046) =< aux(67) s(1047) =< aux(67) s(1048) =< aux(67) s(1047) =< aux(68) s(1046) =< aux(69) s(1047) =< aux(69) s(1048) =< aux(69) s(1032) =< aux(67) s(1050) =< aux(67)+1 s(1051) =< s(1031)*s(1050) s(1052) =< s(1031)*s(1032) s(1053) =< s(1047)*s(1032) s(1054) =< s(1046)*s(1032) s(1055) =< s(1051) s(1056) =< s(1050) s(1057) =< s(1055)*s(1050) s(1058) =< s(1055)*s(1056) s(1059) =< s(1052) s(1060) =< s(1059)*aux(67) s(1061) =< s(1059)*s(1032) s(1067) =< aux(66) s(1068) =< s(1066)*aux(66) s(1069) =< s(1066)*s(1067) s(1033) =< s(1031)*aux(67) s(1034) =< s(1031)*s(1032) with precondition: [] Closed-form bounds of start(V,V10): ------------------------------------- * Chain [84] with precondition: [] - Upper bound: nat(V)*459+52+nat(V)*483*nat(V)+nat(V)*100*nat(V)*nat(V)+nat(V10)*187+nat(V10)*209*nat(V10)+nat(V10)*44*nat(V10)*nat(V10) - Complexity: n^3 ### Maximum cost of start(V,V10): nat(V)*459+52+nat(V)*483*nat(V)+nat(V)*100*nat(V)*nat(V)+nat(V10)*187+nat(V10)*209*nat(V10)+nat(V10)*44*nat(V10)*nat(V10) Asymptotic class: n^3 * Total analysis performed in 2080 ms. ---------------------------------------- (16) BOUNDS(1, n^3) ---------------------------------------- (17) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (18) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^2, INF). The TRS R consists of the following rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) The (relative) TRS S consists of the following rules: encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Rewrite Strategy: FULL ---------------------------------------- (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (20) Obligation: TRS: Rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Types: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ hole_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++1_0 :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0 :: Nat -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ---------------------------------------- (21) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: rev, ++, encArg They will be analysed ascendingly in the following order: ++ < rev rev < encArg ++ < encArg ---------------------------------------- (22) Obligation: TRS: Rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Types: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ hole_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++1_0 :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0 :: Nat -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ Generator Equations: gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0) <=> nil gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(x)) The following defined symbols remain to be analysed: ++, rev, encArg They will be analysed ascendingly in the following order: ++ < rev rev < encArg ++ < encArg ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n4_0), gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b)) -> gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n4_0, b)), rt in Omega(1 + n4_0) Induction Base: ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0), gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b)) ->_R^Omega(1) gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b) Induction Step: ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n4_0, 1)), gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b)) ->_R^Omega(1) .(nil, ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n4_0), gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b))) ->_IH .(nil, gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(b, c5_0))) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Types: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ hole_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++1_0 :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0 :: Nat -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ Generator Equations: gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0) <=> nil gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(x)) The following defined symbols remain to be analysed: ++, rev, encArg They will be analysed ascendingly in the following order: ++ < rev rev < encArg ++ < encArg ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^1, INF) ---------------------------------------- (28) Obligation: TRS: Rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Types: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ hole_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++1_0 :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0 :: Nat -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ Lemmas: ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n4_0), gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b)) -> gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n4_0, b)), rt in Omega(1 + n4_0) Generator Equations: gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0) <=> nil gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(x)) The following defined symbols remain to be analysed: rev, encArg They will be analysed ascendingly in the following order: rev < encArg ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: rev(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n817_0)) -> gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n817_0), rt in Omega(1 + n817_0 + n817_0^2) Induction Base: rev(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0)) ->_R^Omega(1) nil Induction Step: rev(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n817_0, 1))) ->_R^Omega(1) ++(rev(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n817_0)), .(nil, nil)) ->_IH ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(c818_0), .(nil, nil)) ->_L^Omega(1 + n817_0) gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n817_0, +(0, 1))) We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). ---------------------------------------- (30) Complex Obligation (BEST) ---------------------------------------- (31) Obligation: Proved the lower bound n^2 for the following obligation: TRS: Rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Types: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ hole_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++1_0 :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0 :: Nat -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ Lemmas: ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n4_0), gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b)) -> gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n4_0, b)), rt in Omega(1 + n4_0) Generator Equations: gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0) <=> nil gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(x)) The following defined symbols remain to be analysed: rev, encArg They will be analysed ascendingly in the following order: rev < encArg ---------------------------------------- (32) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (33) BOUNDS(n^2, INF) ---------------------------------------- (34) Obligation: TRS: Rules: rev(nil) -> nil rev(.(x, y)) -> ++(rev(y), .(x, nil)) car(.(x, y)) -> x cdr(.(x, y)) -> y null(nil) -> true null(.(x, y)) -> false ++(nil, y) -> y ++(.(x, y), z) -> .(x, ++(y, z)) encArg(nil) -> nil encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encArg(true) -> true encArg(false) -> false encArg(cons_rev(x_1)) -> rev(encArg(x_1)) encArg(cons_car(x_1)) -> car(encArg(x_1)) encArg(cons_cdr(x_1)) -> cdr(encArg(x_1)) encArg(cons_null(x_1)) -> null(encArg(x_1)) encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) encode_rev(x_1) -> rev(encArg(x_1)) encode_nil -> nil encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) encode_car(x_1) -> car(encArg(x_1)) encode_cdr(x_1) -> cdr(encArg(x_1)) encode_null(x_1) -> null(encArg(x_1)) encode_true -> true encode_false -> false Types: rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ . :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ ++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encArg :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ cons_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_rev :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_nil :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_. :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_++ :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_car :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_cdr :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_null :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_true :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ encode_false :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ hole_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++1_0 :: nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0 :: Nat -> nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++ Lemmas: ++(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n4_0), gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(b)) -> gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n4_0, b)), rt in Omega(1 + n4_0) rev(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n817_0)) -> gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n817_0), rt in Omega(1 + n817_0 + n817_0^2) Generator Equations: gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0) <=> nil gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(x)) The following defined symbols remain to be analysed: encArg ---------------------------------------- (35) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n1119_0)) -> gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n1119_0), rt in Omega(0) Induction Base: encArg(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(0)) ->_R^Omega(0) nil Induction Step: encArg(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(+(n1119_0, 1))) ->_R^Omega(0) .(encArg(nil), encArg(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n1119_0))) ->_R^Omega(0) .(nil, encArg(gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(n1119_0))) ->_IH .(nil, gen_nil:.:true:false:cons_rev:cons_car:cons_cdr:cons_null:cons_++2_0(c1120_0)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (36) BOUNDS(1, INF)