/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 195 ms] (4) CpxRelTRS (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 3189 ms] (14) BOUNDS(1, n^2) (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CpxRelTRS (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (18) typed CpxTrs (19) OrderProof [LOWER BOUND(ID), 0 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 480 ms] (22) BEST (23) proven lower bound (24) LowerBoundPropagationProof [FINISHED, 0 ms] (25) BOUNDS(n^1, INF) (26) typed CpxTrs (27) RewriteLemmaProof [LOWER BOUND(ID), 53 ms] (28) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(true) -> true encArg(0) -> 0 encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_false -> false encode_s(x_1) -> s(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(0) -> 0 encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_false -> false encode_s(x_1) -> s(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(0) -> 0 encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_false -> false encode_s(x_1) -> s(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: cond(true, x, y) -> cond(gr(x, y), y, x) [1] gr(0, x) -> false [1] gr(s(x), 0) -> true [1] gr(s(x), s(y)) -> gr(x, y) [1] encArg(true) -> true [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) [0] encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_true -> true [0] encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_false -> false [0] encode_s(x_1) -> s(encArg(x_1)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: cond(true, x, y) -> cond(gr(x, y), y, x) [1] gr(0, x) -> false [1] gr(s(x), 0) -> true [1] gr(s(x), s(y)) -> gr(x, y) [1] encArg(true) -> true [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) [0] encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_true -> true [0] encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_false -> false [0] encode_s(x_1) -> s(encArg(x_1)) [0] The TRS has the following type information: cond :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr true :: true:0:false:s:cons_cond:cons_gr gr :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr 0 :: true:0:false:s:cons_cond:cons_gr false :: true:0:false:s:cons_cond:cons_gr s :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr encArg :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr cons_cond :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr cons_gr :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr encode_cond :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr encode_true :: true:0:false:s:cons_cond:cons_gr encode_gr :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr encode_0 :: true:0:false:s:cons_cond:cons_gr encode_false :: true:0:false:s:cons_cond:cons_gr encode_s :: true:0:false:s:cons_cond:cons_gr -> true:0:false:s:cons_cond:cons_gr Rewrite Strategy: INNERMOST ---------------------------------------- (9) 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_cond(v0, v1, v2) -> null_encode_cond [0] encode_true -> null_encode_true [0] encode_gr(v0, v1) -> null_encode_gr [0] encode_0 -> null_encode_0 [0] encode_false -> null_encode_false [0] encode_s(v0) -> null_encode_s [0] cond(v0, v1, v2) -> null_cond [0] gr(v0, v1) -> null_gr [0] And the following fresh constants: null_encArg, null_encode_cond, null_encode_true, null_encode_gr, null_encode_0, null_encode_false, null_encode_s, null_cond, null_gr ---------------------------------------- (10) 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: cond(true, x, y) -> cond(gr(x, y), y, x) [1] gr(0, x) -> false [1] gr(s(x), 0) -> true [1] gr(s(x), s(y)) -> gr(x, y) [1] encArg(true) -> true [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) [0] encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_true -> true [0] encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_false -> false [0] encode_s(x_1) -> s(encArg(x_1)) [0] encArg(v0) -> null_encArg [0] encode_cond(v0, v1, v2) -> null_encode_cond [0] encode_true -> null_encode_true [0] encode_gr(v0, v1) -> null_encode_gr [0] encode_0 -> null_encode_0 [0] encode_false -> null_encode_false [0] encode_s(v0) -> null_encode_s [0] cond(v0, v1, v2) -> null_cond [0] gr(v0, v1) -> null_gr [0] The TRS has the following type information: cond :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr true :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr gr :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr 0 :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr false :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr s :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr encArg :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr cons_cond :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr cons_gr :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr encode_cond :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr encode_true :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr encode_gr :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr encode_0 :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr encode_false :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr encode_s :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr -> true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_encArg :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_encode_cond :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_encode_true :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_encode_gr :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_encode_0 :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_encode_false :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_encode_s :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_cond :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr null_gr :: true:0:false:s:cons_cond:cons_gr:null_encArg:null_encode_cond:null_encode_true:null_encode_gr:null_encode_0:null_encode_false:null_encode_s:null_cond:null_gr Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: true => 2 0 => 0 false => 1 null_encArg => 0 null_encode_cond => 0 null_encode_true => 0 null_encode_gr => 0 null_encode_0 => 0 null_encode_false => 0 null_encode_s => 0 null_cond => 0 null_gr => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: cond(z, z', z'') -{ 1 }-> cond(gr(x, y), y, x) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 cond(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 encArg(z) -{ 0 }-> gr(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> cond(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 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 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_0 -{ 0 }-> 0 :|: encode_cond(z, z', z'') -{ 0 }-> cond(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3 encode_cond(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 encode_false -{ 0 }-> 1 :|: encode_false -{ 0 }-> 0 :|: encode_gr(z, z') -{ 0 }-> gr(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_gr(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 encode_true -{ 0 }-> 2 :|: encode_true -{ 0 }-> 0 :|: gr(z, z') -{ 1 }-> gr(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x gr(z, z') -{ 1 }-> 2 :|: x >= 0, z = 1 + x, z' = 0 gr(z, z') -{ 1 }-> 1 :|: z' = x, x >= 0, z = 0 gr(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V, V2),0,[cond(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). eq(start(V1, V, V2),0,[gr(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V2),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V, V2),0,[fun(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). eq(start(V1, V, V2),0,[fun1(Out)],[]). eq(start(V1, V, V2),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V2),0,[fun3(Out)],[]). eq(start(V1, V, V2),0,[fun4(Out)],[]). eq(start(V1, V, V2),0,[fun5(V1, Out)],[V1 >= 0]). eq(cond(V1, V, V2, Out),1,[gr(V4, V3, Ret0),cond(Ret0, V3, V4, Ret)],[Out = Ret,V1 = 2,V = V4,V2 = V3,V4 >= 0,V3 >= 0]). eq(gr(V1, V, Out),1,[],[Out = 1,V = V5,V5 >= 0,V1 = 0]). eq(gr(V1, V, Out),1,[],[Out = 2,V6 >= 0,V1 = 1 + V6,V = 0]). eq(gr(V1, V, Out),1,[gr(V7, V8, Ret1)],[Out = Ret1,V = 1 + V8,V7 >= 0,V8 >= 0,V1 = 1 + V7]). eq(encArg(V1, Out),0,[],[Out = 2,V1 = 2]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]). eq(encArg(V1, Out),0,[encArg(V9, Ret11)],[Out = 1 + Ret11,V1 = 1 + V9,V9 >= 0]). eq(encArg(V1, Out),0,[encArg(V11, Ret01),encArg(V12, Ret12),encArg(V10, Ret2),cond(Ret01, Ret12, Ret2, Ret3)],[Out = Ret3,V11 >= 0,V1 = 1 + V10 + V11 + V12,V10 >= 0,V12 >= 0]). eq(encArg(V1, Out),0,[encArg(V13, Ret02),encArg(V14, Ret13),gr(Ret02, Ret13, Ret4)],[Out = Ret4,V13 >= 0,V1 = 1 + V13 + V14,V14 >= 0]). eq(fun(V1, V, V2, Out),0,[encArg(V17, Ret03),encArg(V15, Ret14),encArg(V16, Ret21),cond(Ret03, Ret14, Ret21, Ret5)],[Out = Ret5,V17 >= 0,V16 >= 0,V15 >= 0,V1 = V17,V = V15,V2 = V16]). eq(fun1(Out),0,[],[Out = 2]). eq(fun2(V1, V, Out),0,[encArg(V19, Ret04),encArg(V18, Ret15),gr(Ret04, Ret15, Ret6)],[Out = Ret6,V19 >= 0,V18 >= 0,V1 = V19,V = V18]). eq(fun3(Out),0,[],[Out = 0]). eq(fun4(Out),0,[],[Out = 1]). eq(fun5(V1, Out),0,[encArg(V20, Ret16)],[Out = 1 + Ret16,V20 >= 0,V1 = V20]). eq(encArg(V1, Out),0,[],[Out = 0,V21 >= 0,V1 = V21]). eq(fun(V1, V, V2, Out),0,[],[Out = 0,V23 >= 0,V2 = V24,V22 >= 0,V1 = V23,V = V22,V24 >= 0]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, V, Out),0,[],[Out = 0,V26 >= 0,V25 >= 0,V1 = V26,V = V25]). eq(fun4(Out),0,[],[Out = 0]). eq(fun5(V1, Out),0,[],[Out = 0,V27 >= 0,V1 = V27]). eq(cond(V1, V, V2, Out),0,[],[Out = 0,V28 >= 0,V2 = V29,V30 >= 0,V1 = V28,V = V30,V29 >= 0]). eq(gr(V1, V, Out),0,[],[Out = 0,V31 >= 0,V32 >= 0,V1 = V31,V = V32]). input_output_vars(cond(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(gr(V1,V,Out),[V1,V],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(fun1(Out),[],[Out]). input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). input_output_vars(fun3(Out),[],[Out]). input_output_vars(fun4(Out),[],[Out]). input_output_vars(fun5(V1,Out),[V1],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [gr/3] 1. recursive : [cond/4] 2. recursive [non_tail,multiple] : [encArg/2] 3. non_recursive : [fun/4] 4. non_recursive : [fun1/1] 5. non_recursive : [fun2/3] 6. non_recursive : [fun3/1] 7. non_recursive : [fun4/1] 8. non_recursive : [fun5/2] 9. non_recursive : [start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into gr/3 1. SCC is partially evaluated into cond/4 2. SCC is partially evaluated into encArg/2 3. SCC is partially evaluated into fun/4 4. SCC is partially evaluated into fun1/1 5. SCC is partially evaluated into fun2/3 6. SCC is completely evaluated into other SCCs 7. SCC is partially evaluated into fun4/1 8. SCC is partially evaluated into fun5/2 9. SCC is partially evaluated into start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations gr/3 * CE 15 is refined into CE [32] * CE 13 is refined into CE [33] * CE 12 is refined into CE [34] * CE 14 is refined into CE [35] ### Cost equations --> "Loop" of gr/3 * CEs [35] --> Loop 21 * CEs [32] --> Loop 22 * CEs [33] --> Loop 23 * CEs [34] --> Loop 24 ### Ranking functions of CR gr(V1,V,Out) * RF of phase [21]: [V,V1] #### Partial ranking functions of CR gr(V1,V,Out) * Partial RF of phase [21]: - RF of loop [21:1]: V V1 ### Specialization of cost equations cond/4 * CE 11 is refined into CE [36] * CE 10 is refined into CE [37,38,39,40,41] ### Cost equations --> "Loop" of cond/4 * CEs [41] --> Loop 25 * CEs [40] --> Loop 26 * CEs [39] --> Loop 27 * CEs [38] --> Loop 28 * CEs [37] --> Loop 29 * CEs [36] --> Loop 30 ### Ranking functions of CR cond(V1,V,V2,Out) #### Partial ranking functions of CR cond(V1,V,V2,Out) ### Specialization of cost equations encArg/2 * CE 17 is refined into CE [42] * CE 16 is refined into CE [43] * CE 18 is refined into CE [44] * CE 21 is refined into CE [45,46,47,48,49] * CE 20 is refined into CE [50,51] * CE 19 is refined into CE [52] ### Cost equations --> "Loop" of encArg/2 * CEs [52] --> Loop 31 * CEs [50,51] --> Loop 32 * CEs [49] --> Loop 33 * CEs [46] --> Loop 34 * CEs [48] --> Loop 35 * CEs [45] --> Loop 36 * CEs [47] --> Loop 37 * CEs [42] --> Loop 38 * CEs [43] --> Loop 39 * CEs [44] --> Loop 40 ### Ranking functions of CR encArg(V1,Out) * RF of phase [31,32,33,34,35,36,37]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [31,32,33,34,35,36,37]: - RF of loop [31:1,32:1,32:2,32:3,33:1,33:2,34:1,34:2,35:1,35:2,36:1,36:2,37:1,37:2]: V1 ### Specialization of cost equations fun/4 * CE 22 is refined into CE [53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87] * CE 23 is refined into CE [88] ### Cost equations --> "Loop" of fun/4 * CEs [58,59,60,61,62,82,83,84] --> Loop 41 * CEs [55,64,68,77,80,86] --> Loop 42 * CEs [53,54,56,57,63,65,66,67,69,70,71,72,73,74,75,76,78,79,81,85,87,88] --> Loop 43 ### Ranking functions of CR fun(V1,V,V2,Out) #### Partial ranking functions of CR fun(V1,V,V2,Out) ### Specialization of cost equations fun1/1 * CE 24 is refined into CE [89] * CE 25 is refined into CE [90] ### Cost equations --> "Loop" of fun1/1 * CEs [89] --> Loop 44 * CEs [90] --> Loop 45 ### Ranking functions of CR fun1(Out) #### Partial ranking functions of CR fun1(Out) ### Specialization of cost equations fun2/3 * CE 26 is refined into CE [91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116] * CE 27 is refined into CE [117] ### Cost equations --> "Loop" of fun2/3 * CEs [99] --> Loop 46 * CEs [96,98,113] --> Loop 47 * CEs [97,114] --> Loop 48 * CEs [92,95,101,103,106,109] --> Loop 49 * CEs [91,94,100,105,108,111,115] --> Loop 50 * CEs [93,102,104,107,110,112,116,117] --> Loop 51 ### Ranking functions of CR fun2(V1,V,Out) #### Partial ranking functions of CR fun2(V1,V,Out) ### Specialization of cost equations fun4/1 * CE 28 is refined into CE [118] * CE 29 is refined into CE [119] ### Cost equations --> "Loop" of fun4/1 * CEs [118] --> Loop 52 * CEs [119] --> Loop 53 ### Ranking functions of CR fun4(Out) #### Partial ranking functions of CR fun4(Out) ### Specialization of cost equations fun5/2 * CE 30 is refined into CE [120,121,122] * CE 31 is refined into CE [123] ### Cost equations --> "Loop" of fun5/2 * CEs [122] --> Loop 54 * CEs [123] --> Loop 55 * CEs [120,121] --> Loop 56 ### Ranking functions of CR fun5(V1,Out) #### Partial ranking functions of CR fun5(V1,Out) ### Specialization of cost equations start/3 * CE 1 is refined into CE [124,125] * CE 2 is refined into CE [126,127,128,129,130] * CE 3 is refined into CE [131,132,133] * CE 4 is refined into CE [134,135] * CE 5 is refined into CE [136,137] * CE 6 is refined into CE [138,139,140] * CE 7 is refined into CE [141] * CE 8 is refined into CE [142,143] * CE 9 is refined into CE [144,145,146] ### Cost equations --> "Loop" of start/3 * CEs [124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146] --> Loop 57 ### Ranking functions of CR start(V1,V,V2) #### Partial ranking functions of CR start(V1,V,V2) Computing Bounds ===================================== #### Cost of chains of gr(V1,V,Out): * Chain [[21],24]: 1*it(21)+1 Such that:it(21) =< V1 with precondition: [Out=1,V1>=1,V>=V1] * Chain [[21],23]: 1*it(21)+1 Such that:it(21) =< V with precondition: [Out=2,V>=1,V1>=V+1] * Chain [[21],22]: 1*it(21)+0 Such that:it(21) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [24]: 1 with precondition: [V1=0,Out=1,V>=0] * Chain [23]: 1 with precondition: [V=0,Out=2,V1>=1] * Chain [22]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of cond(V1,V,V2,Out): * Chain [30]: 0 with precondition: [Out=0,V1>=0,V>=0,V2>=0] * Chain [29,30]: 2 with precondition: [V1=2,V=0,Out=0,V2>=0] * Chain [28,30]: 2 with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [28,29,30]: 4 with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [28,27,30]: 1*s(2)+3 Such that:s(2) =< V with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [27,30]: 1*s(2)+1 Such that:s(2) =< V2 with precondition: [V1=2,Out=0,V>=0,V2>=0] * Chain [26,30]: 1*s(3)+2 Such that:s(3) =< V with precondition: [V1=2,Out=0,V>=1,V2>=V] * Chain [25,30]: 1*s(4)+2 Such that:s(4) =< V2 with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [25,27,30]: 1*s(2)+1*s(4)+3 Such that:s(2) =< V s(4) =< V2 with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [25,26,30]: 2*s(3)+4 Such that:aux(1) =< V2 s(3) =< aux(1) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] #### Cost of chains of encArg(V1,Out): * Chain [40]: 0 with precondition: [V1=1,Out=1] * Chain [39]: 0 with precondition: [V1=2,Out=2] * Chain [38]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([31,32,33,34,35,36,37],[[40],[39],[38]])]: 5*it(32)+1*it(33)+1*it(34)+1*it(35)+2*s(29)+5*s(30)+1*s(31)+1*s(34)+1*s(35)+1*s(36)+0 Such that:aux(20) =< V1 aux(21) =< V1/2 aux(22) =< 2/3*V1 aux(23) =< 2/5*V1 it(31) =< aux(20) it(32) =< aux(20) it(33) =< aux(20) it(34) =< aux(20) it(35) =< aux(20) it(35) =< aux(21) it(34) =< aux(22) it(35) =< aux(22) it(33) =< aux(23) aux(5) =< aux(20)-1 aux(11) =< aux(20)-2 aux(8) =< aux(20)-3 s(33) =< it(32)*aux(20) s(32) =< it(32)*aux(5) s(31) =< it(32)*aux(5) s(36) =< it(31)*aux(5) s(35) =< it(35)*aux(11) s(34) =< it(33)*aux(8) s(29) =< s(33) s(30) =< s(32) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,V2,Out): * Chain [43]: 30*s(61)+6*s(62)+6*s(63)+6*s(64)+6*s(70)+6*s(71)+6*s(72)+6*s(73)+12*s(74)+30*s(75)+66*s(80)+10*s(81)+10*s(82)+10*s(83)+10*s(89)+10*s(90)+10*s(91)+10*s(92)+20*s(93)+50*s(94)+85*s(99)+10*s(100)+10*s(101)+10*s(102)+10*s(108)+10*s(109)+10*s(110)+10*s(111)+20*s(112)+50*s(113)+13*s(467)+4 Such that:aux(45) =< 2 aux(46) =< V1 aux(47) =< V1/2 aux(48) =< 2/3*V1 aux(49) =< 2/5*V1 aux(50) =< V aux(51) =< V/2 aux(52) =< 2/3*V aux(53) =< 2/5*V aux(54) =< V2 aux(55) =< V2/2 aux(56) =< 2/3*V2 aux(57) =< 2/5*V2 s(467) =< aux(45) s(99) =< aux(54) s(100) =< aux(54) s(101) =< aux(54) s(102) =< aux(54) s(102) =< aux(55) s(101) =< aux(56) s(102) =< aux(56) s(100) =< aux(57) s(103) =< aux(54)-1 s(104) =< aux(54)-2 s(105) =< aux(54)-3 s(106) =< s(99)*aux(54) s(107) =< s(99)*s(103) s(108) =< s(99)*s(103) s(109) =< aux(54)*s(103) s(110) =< s(102)*s(104) s(111) =< s(100)*s(105) s(112) =< s(106) s(113) =< s(107) s(80) =< aux(50) s(81) =< aux(50) s(82) =< aux(50) s(83) =< aux(50) s(83) =< aux(51) s(82) =< aux(52) s(83) =< aux(52) s(81) =< aux(53) s(84) =< aux(50)-1 s(85) =< aux(50)-2 s(86) =< aux(50)-3 s(87) =< s(80)*aux(50) s(88) =< s(80)*s(84) s(89) =< s(80)*s(84) s(90) =< aux(50)*s(84) s(91) =< s(83)*s(85) s(92) =< s(81)*s(86) s(93) =< s(87) s(94) =< s(88) s(61) =< aux(46) s(62) =< aux(46) s(63) =< aux(46) s(64) =< aux(46) s(64) =< aux(47) s(63) =< aux(48) s(64) =< aux(48) s(62) =< aux(49) s(65) =< aux(46)-1 s(66) =< aux(46)-2 s(67) =< aux(46)-3 s(68) =< s(61)*aux(46) s(69) =< s(61)*s(65) s(70) =< s(61)*s(65) s(71) =< aux(46)*s(65) s(72) =< s(64)*s(66) s(73) =< s(62)*s(67) s(74) =< s(68) s(75) =< s(69) with precondition: [Out=0,V1>=0,V>=0,V2>=0] * Chain [42]: 10*s(621)+2*s(622)+2*s(623)+2*s(624)+2*s(630)+2*s(631)+2*s(632)+2*s(633)+4*s(634)+10*s(635)+21*s(640)+3*s(641)+3*s(642)+3*s(643)+3*s(649)+3*s(650)+3*s(651)+3*s(652)+6*s(653)+15*s(654)+30*s(658)+4 Such that:aux(61) =< 2 aux(62) =< V1 aux(63) =< V1/2 aux(64) =< 2/3*V1 aux(65) =< 2/5*V1 aux(66) =< V aux(67) =< V/2 aux(68) =< 2/3*V aux(69) =< 2/5*V s(640) =< aux(66) s(658) =< aux(61) s(641) =< aux(66) s(642) =< aux(66) s(643) =< aux(66) s(643) =< aux(67) s(642) =< aux(68) s(643) =< aux(68) s(641) =< aux(69) s(644) =< aux(66)-1 s(645) =< aux(66)-2 s(646) =< aux(66)-3 s(647) =< s(640)*aux(66) s(648) =< s(640)*s(644) s(649) =< s(640)*s(644) s(650) =< aux(66)*s(644) s(651) =< s(643)*s(645) s(652) =< s(641)*s(646) s(653) =< s(647) s(654) =< s(648) s(621) =< aux(62) s(622) =< aux(62) s(623) =< aux(62) s(624) =< aux(62) s(624) =< aux(63) s(623) =< aux(64) s(624) =< aux(64) s(622) =< aux(65) s(625) =< aux(62)-1 s(626) =< aux(62)-2 s(627) =< aux(62)-3 s(628) =< s(621)*aux(62) s(629) =< s(621)*s(625) s(630) =< s(621)*s(625) s(631) =< aux(62)*s(625) s(632) =< s(624)*s(626) s(633) =< s(622)*s(627) s(634) =< s(628) s(635) =< s(629) with precondition: [V2=2,Out=0,V1>=0,V>=0] * Chain [41]: 25*s(740)+5*s(741)+5*s(742)+5*s(743)+5*s(749)+5*s(750)+5*s(751)+5*s(752)+10*s(753)+25*s(754)+25*s(759)+3*s(760)+3*s(761)+3*s(762)+3*s(768)+3*s(769)+3*s(770)+3*s(771)+6*s(772)+15*s(773)+24*s(776)+4 Such that:aux(74) =< 2 aux(75) =< V1 aux(76) =< V1/2 aux(77) =< 2/3*V1 aux(78) =< 2/5*V1 aux(79) =< V2 aux(80) =< V2/2 aux(81) =< 2/3*V2 aux(82) =< 2/5*V2 s(776) =< aux(74) s(759) =< aux(79) s(760) =< aux(79) s(761) =< aux(79) s(762) =< aux(79) s(762) =< aux(80) s(761) =< aux(81) s(762) =< aux(81) s(760) =< aux(82) s(763) =< aux(79)-1 s(764) =< aux(79)-2 s(765) =< aux(79)-3 s(766) =< s(759)*aux(79) s(767) =< s(759)*s(763) s(768) =< s(759)*s(763) s(769) =< aux(79)*s(763) s(770) =< s(762)*s(764) s(771) =< s(760)*s(765) s(772) =< s(766) s(773) =< s(767) s(740) =< aux(75) s(741) =< aux(75) s(742) =< aux(75) s(743) =< aux(75) s(743) =< aux(76) s(742) =< aux(77) s(743) =< aux(77) s(741) =< aux(78) s(744) =< aux(75)-1 s(745) =< aux(75)-2 s(746) =< aux(75)-3 s(747) =< s(740)*aux(75) s(748) =< s(740)*s(744) s(749) =< s(740)*s(744) s(750) =< aux(75)*s(744) s(751) =< s(743)*s(745) s(752) =< s(741)*s(746) s(753) =< s(747) s(754) =< s(748) with precondition: [V=2,Out=0,V1>=0,V2>=0] #### Cost of chains of fun1(Out): * Chain [45]: 0 with precondition: [Out=0] * Chain [44]: 0 with precondition: [Out=2] #### Cost of chains of fun2(V1,V,Out): * Chain [51]: 10*s(1017)+2*s(1018)+2*s(1019)+2*s(1020)+2*s(1026)+2*s(1027)+2*s(1028)+2*s(1029)+4*s(1030)+10*s(1031)+18*s(1036)+3*s(1037)+3*s(1038)+3*s(1039)+3*s(1045)+3*s(1046)+3*s(1047)+3*s(1048)+6*s(1049)+15*s(1050)+1*s(1092)+0 Such that:s(1092) =< 2 aux(95) =< V1 aux(96) =< V1/2 aux(97) =< 2/3*V1 aux(98) =< 2/5*V1 aux(99) =< V aux(100) =< V/2 aux(101) =< 2/3*V aux(102) =< 2/5*V s(1036) =< aux(99) s(1037) =< aux(99) s(1038) =< aux(99) s(1039) =< aux(99) s(1039) =< aux(100) s(1038) =< aux(101) s(1039) =< aux(101) s(1037) =< aux(102) s(1040) =< aux(99)-1 s(1041) =< aux(99)-2 s(1042) =< aux(99)-3 s(1043) =< s(1036)*aux(99) s(1044) =< s(1036)*s(1040) s(1045) =< s(1036)*s(1040) s(1046) =< aux(99)*s(1040) s(1047) =< s(1039)*s(1041) s(1048) =< s(1037)*s(1042) s(1049) =< s(1043) s(1050) =< s(1044) s(1017) =< aux(95) s(1018) =< aux(95) s(1019) =< aux(95) s(1020) =< aux(95) s(1020) =< aux(96) s(1019) =< aux(97) s(1020) =< aux(97) s(1018) =< aux(98) s(1021) =< aux(95)-1 s(1022) =< aux(95)-2 s(1023) =< aux(95)-3 s(1024) =< s(1017)*aux(95) s(1025) =< s(1017)*s(1021) s(1026) =< s(1017)*s(1021) s(1027) =< aux(95)*s(1021) s(1028) =< s(1020)*s(1022) s(1029) =< s(1018)*s(1023) s(1030) =< s(1024) s(1031) =< s(1025) with precondition: [Out=0,V1>=0,V>=0] * Chain [50]: 15*s(1119)+3*s(1120)+3*s(1121)+3*s(1122)+3*s(1128)+3*s(1129)+3*s(1130)+3*s(1131)+6*s(1132)+15*s(1133)+21*s(1138)+4*s(1139)+4*s(1140)+4*s(1141)+4*s(1147)+4*s(1148)+4*s(1149)+4*s(1150)+8*s(1151)+20*s(1152)+2*s(1230)+1 Such that:aux(104) =< 2 aux(105) =< V1 aux(106) =< V1/2 aux(107) =< 2/3*V1 aux(108) =< 2/5*V1 aux(109) =< V aux(110) =< V/2 aux(111) =< 2/3*V aux(112) =< 2/5*V s(1230) =< aux(104) s(1138) =< aux(109) s(1139) =< aux(109) s(1140) =< aux(109) s(1141) =< aux(109) s(1141) =< aux(110) s(1140) =< aux(111) s(1141) =< aux(111) s(1139) =< aux(112) s(1142) =< aux(109)-1 s(1143) =< aux(109)-2 s(1144) =< aux(109)-3 s(1145) =< s(1138)*aux(109) s(1146) =< s(1138)*s(1142) s(1147) =< s(1138)*s(1142) s(1148) =< aux(109)*s(1142) s(1149) =< s(1141)*s(1143) s(1150) =< s(1139)*s(1144) s(1151) =< s(1145) s(1152) =< s(1146) s(1119) =< aux(105) s(1120) =< aux(105) s(1121) =< aux(105) s(1122) =< aux(105) s(1122) =< aux(106) s(1121) =< aux(107) s(1122) =< aux(107) s(1120) =< aux(108) s(1123) =< aux(105)-1 s(1124) =< aux(105)-2 s(1125) =< aux(105)-3 s(1126) =< s(1119)*aux(105) s(1127) =< s(1119)*s(1123) s(1128) =< s(1119)*s(1123) s(1129) =< aux(105)*s(1123) s(1130) =< s(1122)*s(1124) s(1131) =< s(1120)*s(1125) s(1132) =< s(1126) s(1133) =< s(1127) with precondition: [Out=1,V1>=0,V>=0] * Chain [49]: 15*s(1255)+3*s(1256)+3*s(1257)+3*s(1258)+3*s(1264)+3*s(1265)+3*s(1266)+3*s(1267)+6*s(1268)+15*s(1269)+21*s(1274)+4*s(1275)+4*s(1276)+4*s(1277)+4*s(1283)+4*s(1284)+4*s(1285)+4*s(1286)+8*s(1287)+20*s(1288)+1*s(1385)+1 Such that:s(1385) =< 1 aux(114) =< V1 aux(115) =< V1/2 aux(116) =< 2/3*V1 aux(117) =< 2/5*V1 aux(118) =< V aux(119) =< V/2 aux(120) =< 2/3*V aux(121) =< 2/5*V s(1274) =< aux(118) s(1275) =< aux(118) s(1276) =< aux(118) s(1277) =< aux(118) s(1277) =< aux(119) s(1276) =< aux(120) s(1277) =< aux(120) s(1275) =< aux(121) s(1278) =< aux(118)-1 s(1279) =< aux(118)-2 s(1280) =< aux(118)-3 s(1281) =< s(1274)*aux(118) s(1282) =< s(1274)*s(1278) s(1283) =< s(1274)*s(1278) s(1284) =< aux(118)*s(1278) s(1285) =< s(1277)*s(1279) s(1286) =< s(1275)*s(1280) s(1287) =< s(1281) s(1288) =< s(1282) s(1255) =< aux(114) s(1256) =< aux(114) s(1257) =< aux(114) s(1258) =< aux(114) s(1258) =< aux(115) s(1257) =< aux(116) s(1258) =< aux(116) s(1256) =< aux(117) s(1259) =< aux(114)-1 s(1260) =< aux(114)-2 s(1261) =< aux(114)-3 s(1262) =< s(1255)*aux(114) s(1263) =< s(1255)*s(1259) s(1264) =< s(1255)*s(1259) s(1265) =< aux(114)*s(1259) s(1266) =< s(1258)*s(1260) s(1267) =< s(1256)*s(1261) s(1268) =< s(1262) s(1269) =< s(1263) with precondition: [Out=2,V1>=1,V>=0] * Chain [48]: 5*s(1390)+1*s(1391)+1*s(1392)+1*s(1393)+1*s(1399)+1*s(1400)+1*s(1401)+1*s(1402)+2*s(1403)+5*s(1404)+2*s(1405)+0 Such that:s(1386) =< V1 s(1387) =< V1/2 s(1388) =< 2/3*V1 s(1389) =< 2/5*V1 aux(122) =< 2 s(1405) =< aux(122) s(1390) =< s(1386) s(1391) =< s(1386) s(1392) =< s(1386) s(1393) =< s(1386) s(1393) =< s(1387) s(1392) =< s(1388) s(1393) =< s(1388) s(1391) =< s(1389) s(1394) =< s(1386)-1 s(1395) =< s(1386)-2 s(1396) =< s(1386)-3 s(1397) =< s(1390)*s(1386) s(1398) =< s(1390)*s(1394) s(1399) =< s(1390)*s(1394) s(1400) =< s(1386)*s(1394) s(1401) =< s(1393)*s(1395) s(1402) =< s(1391)*s(1396) s(1403) =< s(1397) s(1404) =< s(1398) with precondition: [V=2,Out=0,V1>=0] * Chain [47]: 11*s(1411)+2*s(1412)+2*s(1413)+2*s(1414)+2*s(1420)+2*s(1421)+2*s(1422)+2*s(1423)+4*s(1424)+10*s(1425)+1 Such that:aux(124) =< V1 aux(125) =< V1/2 aux(126) =< 2/3*V1 aux(127) =< 2/5*V1 s(1411) =< aux(124) s(1412) =< aux(124) s(1413) =< aux(124) s(1414) =< aux(124) s(1414) =< aux(125) s(1413) =< aux(126) s(1414) =< aux(126) s(1412) =< aux(127) s(1415) =< aux(124)-1 s(1416) =< aux(124)-2 s(1417) =< aux(124)-3 s(1418) =< s(1411)*aux(124) s(1419) =< s(1411)*s(1415) s(1420) =< s(1411)*s(1415) s(1421) =< aux(124)*s(1415) s(1422) =< s(1414)*s(1416) s(1423) =< s(1412)*s(1417) s(1424) =< s(1418) s(1425) =< s(1419) with precondition: [V=2,Out=1,V1>=0] * Chain [46]: 5*s(1450)+1*s(1451)+1*s(1452)+1*s(1453)+1*s(1459)+1*s(1460)+1*s(1461)+1*s(1462)+2*s(1463)+5*s(1464)+1*s(1465)+1 Such that:s(1465) =< 2 s(1446) =< V1 s(1447) =< V1/2 s(1448) =< 2/3*V1 s(1449) =< 2/5*V1 s(1450) =< s(1446) s(1451) =< s(1446) s(1452) =< s(1446) s(1453) =< s(1446) s(1453) =< s(1447) s(1452) =< s(1448) s(1453) =< s(1448) s(1451) =< s(1449) s(1454) =< s(1446)-1 s(1455) =< s(1446)-2 s(1456) =< s(1446)-3 s(1457) =< s(1450)*s(1446) s(1458) =< s(1450)*s(1454) s(1459) =< s(1450)*s(1454) s(1460) =< s(1446)*s(1454) s(1461) =< s(1453)*s(1455) s(1462) =< s(1451)*s(1456) s(1463) =< s(1457) s(1464) =< s(1458) with precondition: [V=2,Out=2,V1>=3] #### Cost of chains of fun4(Out): * Chain [53]: 0 with precondition: [Out=0] * Chain [52]: 0 with precondition: [Out=1] #### Cost of chains of fun5(V1,Out): * Chain [56]: 5*s(1648)+1*s(1649)+1*s(1650)+1*s(1651)+1*s(1657)+1*s(1658)+1*s(1659)+1*s(1660)+2*s(1661)+5*s(1662)+0 Such that:s(1644) =< V1 s(1645) =< V1/2 s(1646) =< 2/3*V1 s(1647) =< 2/5*V1 s(1648) =< s(1644) s(1649) =< s(1644) s(1650) =< s(1644) s(1651) =< s(1644) s(1651) =< s(1645) s(1650) =< s(1646) s(1651) =< s(1646) s(1649) =< s(1647) s(1652) =< s(1644)-1 s(1653) =< s(1644)-2 s(1654) =< s(1644)-3 s(1655) =< s(1648)*s(1644) s(1656) =< s(1648)*s(1652) s(1657) =< s(1648)*s(1652) s(1658) =< s(1644)*s(1652) s(1659) =< s(1651)*s(1653) s(1660) =< s(1649)*s(1654) s(1661) =< s(1655) s(1662) =< s(1656) with precondition: [V1>=1,Out>=1,V1+1>=Out] * Chain [55]: 0 with precondition: [Out=0,V1>=0] * Chain [54]: 0 with precondition: [Out=1,V1>=0] #### Cost of chains of start(V1,V,V2): * Chain [57]: 152*s(1665)+115*s(1666)+137*s(1669)+27*s(1676)+27*s(1677)+27*s(1678)+27*s(1684)+27*s(1685)+27*s(1686)+27*s(1687)+54*s(1688)+135*s(1689)+73*s(1703)+13*s(1705)+13*s(1706)+13*s(1707)+13*s(1713)+13*s(1714)+13*s(1715)+13*s(1716)+26*s(1717)+65*s(1718)+24*s(1735)+24*s(1736)+24*s(1737)+24*s(1743)+24*s(1744)+24*s(1745)+24*s(1746)+48*s(1747)+120*s(1748)+1*s(1869)+4 Such that:s(1869) =< 1 s(1700) =< V2/2 s(1701) =< 2/3*V2 s(1702) =< 2/5*V2 aux(141) =< 2 aux(142) =< V1 aux(143) =< V1/2 aux(144) =< 2/3*V1 aux(145) =< 2/5*V1 aux(146) =< V aux(147) =< V/2 aux(148) =< 2/3*V aux(149) =< 2/5*V aux(150) =< V2 s(1703) =< aux(141) s(1669) =< aux(142) s(1665) =< aux(146) s(1735) =< aux(146) s(1736) =< aux(146) s(1737) =< aux(146) s(1737) =< aux(147) s(1736) =< aux(148) s(1737) =< aux(148) s(1735) =< aux(149) s(1738) =< aux(146)-1 s(1739) =< aux(146)-2 s(1740) =< aux(146)-3 s(1741) =< s(1665)*aux(146) s(1742) =< s(1665)*s(1738) s(1743) =< s(1665)*s(1738) s(1744) =< aux(146)*s(1738) s(1745) =< s(1737)*s(1739) s(1746) =< s(1735)*s(1740) s(1747) =< s(1741) s(1748) =< s(1742) s(1676) =< aux(142) s(1677) =< aux(142) s(1678) =< aux(142) s(1678) =< aux(143) s(1677) =< aux(144) s(1678) =< aux(144) s(1676) =< aux(145) s(1679) =< aux(142)-1 s(1680) =< aux(142)-2 s(1681) =< aux(142)-3 s(1682) =< s(1669)*aux(142) s(1683) =< s(1669)*s(1679) s(1684) =< s(1669)*s(1679) s(1685) =< aux(142)*s(1679) s(1686) =< s(1678)*s(1680) s(1687) =< s(1676)*s(1681) s(1688) =< s(1682) s(1689) =< s(1683) s(1666) =< aux(150) s(1705) =< aux(150) s(1706) =< aux(150) s(1707) =< aux(150) s(1707) =< s(1700) s(1706) =< s(1701) s(1707) =< s(1701) s(1705) =< s(1702) s(1708) =< aux(150)-1 s(1709) =< aux(150)-2 s(1710) =< aux(150)-3 s(1711) =< s(1666)*aux(150) s(1712) =< s(1666)*s(1708) s(1713) =< s(1666)*s(1708) s(1714) =< aux(150)*s(1708) s(1715) =< s(1707)*s(1709) s(1716) =< s(1705)*s(1710) s(1717) =< s(1711) s(1718) =< s(1712) with precondition: [] Closed-form bounds of start(V1,V,V2): ------------------------------------- * Chain [57] with precondition: [] - Upper bound: nat(V1)*218+151+nat(V1)*54*nat(V1)+nat(V1)*27*nat(nat(V1)+ -3)+nat(V1)*27*nat(nat(V1)+ -2)+nat(V1)*189*nat(nat(V1)+ -1)+nat(V)*224+nat(V)*48*nat(V)+nat(V)*24*nat(nat(V)+ -3)+nat(V)*24*nat(nat(V)+ -2)+nat(V)*168*nat(nat(V)+ -1)+nat(V2)*154+nat(V2)*26*nat(V2)+nat(V2)*13*nat(nat(V2)+ -3)+nat(V2)*13*nat(nat(V2)+ -2)+nat(V2)*91*nat(nat(V2)+ -1) - Complexity: n^2 ### Maximum cost of start(V1,V,V2): nat(V1)*218+151+nat(V1)*54*nat(V1)+nat(V1)*27*nat(nat(V1)+ -3)+nat(V1)*27*nat(nat(V1)+ -2)+nat(V1)*189*nat(nat(V1)+ -1)+nat(V)*224+nat(V)*48*nat(V)+nat(V)*24*nat(nat(V)+ -3)+nat(V)*24*nat(nat(V)+ -2)+nat(V)*168*nat(nat(V)+ -1)+nat(V2)*154+nat(V2)*26*nat(V2)+nat(V2)*13*nat(nat(V2)+ -3)+nat(V2)*13*nat(nat(V2)+ -2)+nat(V2)*91*nat(nat(V2)+ -1) Asymptotic class: n^2 * Total analysis performed in 2992 ms. ---------------------------------------- (14) BOUNDS(1, n^2) ---------------------------------------- (15) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (16) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_false -> false encode_s(x_1) -> s(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_false -> false encode_s(x_1) -> s(encArg(x_1)) Types: cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr true :: true:0':false:s:cons_cond:cons_gr gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr 0' :: true:0':false:s:cons_cond:cons_gr false :: true:0':false:s:cons_cond:cons_gr s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encArg :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_true :: true:0':false:s:cons_cond:cons_gr encode_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_0 :: true:0':false:s:cons_cond:cons_gr encode_false :: true:0':false:s:cons_cond:cons_gr encode_s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr hole_true:0':false:s:cons_cond:cons_gr1_4 :: true:0':false:s:cons_cond:cons_gr gen_true:0':false:s:cons_cond:cons_gr2_4 :: Nat -> true:0':false:s:cons_cond:cons_gr ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: cond, gr, encArg They will be analysed ascendingly in the following order: gr < cond cond < encArg gr < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_false -> false encode_s(x_1) -> s(encArg(x_1)) Types: cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr true :: true:0':false:s:cons_cond:cons_gr gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr 0' :: true:0':false:s:cons_cond:cons_gr false :: true:0':false:s:cons_cond:cons_gr s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encArg :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_true :: true:0':false:s:cons_cond:cons_gr encode_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_0 :: true:0':false:s:cons_cond:cons_gr encode_false :: true:0':false:s:cons_cond:cons_gr encode_s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr hole_true:0':false:s:cons_cond:cons_gr1_4 :: true:0':false:s:cons_cond:cons_gr gen_true:0':false:s:cons_cond:cons_gr2_4 :: Nat -> true:0':false:s:cons_cond:cons_gr Generator Equations: gen_true:0':false:s:cons_cond:cons_gr2_4(0) <=> true gen_true:0':false:s:cons_cond:cons_gr2_4(+(x, 1)) <=> s(gen_true:0':false:s:cons_cond:cons_gr2_4(x)) The following defined symbols remain to be analysed: gr, cond, encArg They will be analysed ascendingly in the following order: gr < cond cond < encArg gr < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: gr(gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, n4_4)), gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4) Induction Base: gr(gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, 0)), gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, 0))) Induction Step: gr(gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, +(n4_4, 1))), gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, +(n4_4, 1)))) ->_R^Omega(1) gr(gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, n4_4)), gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, n4_4))) ->_IH *3_4 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (22) Complex Obligation (BEST) ---------------------------------------- (23) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_false -> false encode_s(x_1) -> s(encArg(x_1)) Types: cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr true :: true:0':false:s:cons_cond:cons_gr gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr 0' :: true:0':false:s:cons_cond:cons_gr false :: true:0':false:s:cons_cond:cons_gr s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encArg :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_true :: true:0':false:s:cons_cond:cons_gr encode_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_0 :: true:0':false:s:cons_cond:cons_gr encode_false :: true:0':false:s:cons_cond:cons_gr encode_s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr hole_true:0':false:s:cons_cond:cons_gr1_4 :: true:0':false:s:cons_cond:cons_gr gen_true:0':false:s:cons_cond:cons_gr2_4 :: Nat -> true:0':false:s:cons_cond:cons_gr Generator Equations: gen_true:0':false:s:cons_cond:cons_gr2_4(0) <=> true gen_true:0':false:s:cons_cond:cons_gr2_4(+(x, 1)) <=> s(gen_true:0':false:s:cons_cond:cons_gr2_4(x)) The following defined symbols remain to be analysed: gr, cond, encArg They will be analysed ascendingly in the following order: gr < cond cond < encArg gr < encArg ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: cond(true, x, y) -> cond(gr(x, y), y, x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_false -> false encode_s(x_1) -> s(encArg(x_1)) Types: cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr true :: true:0':false:s:cons_cond:cons_gr gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr 0' :: true:0':false:s:cons_cond:cons_gr false :: true:0':false:s:cons_cond:cons_gr s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encArg :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr cons_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_cond :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_true :: true:0':false:s:cons_cond:cons_gr encode_gr :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr encode_0 :: true:0':false:s:cons_cond:cons_gr encode_false :: true:0':false:s:cons_cond:cons_gr encode_s :: true:0':false:s:cons_cond:cons_gr -> true:0':false:s:cons_cond:cons_gr hole_true:0':false:s:cons_cond:cons_gr1_4 :: true:0':false:s:cons_cond:cons_gr gen_true:0':false:s:cons_cond:cons_gr2_4 :: Nat -> true:0':false:s:cons_cond:cons_gr Lemmas: gr(gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, n4_4)), gen_true:0':false:s:cons_cond:cons_gr2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4) Generator Equations: gen_true:0':false:s:cons_cond:cons_gr2_4(0) <=> true gen_true:0':false:s:cons_cond:cons_gr2_4(+(x, 1)) <=> s(gen_true:0':false:s:cons_cond:cons_gr2_4(x)) The following defined symbols remain to be analysed: cond, encArg They will be analysed ascendingly in the following order: cond < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_true:0':false:s:cons_cond:cons_gr2_4(n2221_4)) -> gen_true:0':false:s:cons_cond:cons_gr2_4(n2221_4), rt in Omega(0) Induction Base: encArg(gen_true:0':false:s:cons_cond:cons_gr2_4(0)) ->_R^Omega(0) true Induction Step: encArg(gen_true:0':false:s:cons_cond:cons_gr2_4(+(n2221_4, 1))) ->_R^Omega(0) s(encArg(gen_true:0':false:s:cons_cond:cons_gr2_4(n2221_4))) ->_IH s(gen_true:0':false:s:cons_cond:cons_gr2_4(c2222_4)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (28) BOUNDS(1, INF)