/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), 162 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, 2408 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), 1138 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), 20 ms] (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 14 ms] (30) 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: minus(X, 0) -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0, s(Y)) -> 0 div(s(X), s(Y)) -> s(div(minus(X, Y), s(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(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) ---------------------------------------- (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: minus(X, 0) -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0, s(Y)) -> 0 div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) 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: minus(X, 0) -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0, s(Y)) -> 0 div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) 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: minus(X, 0) -> X [1] minus(s(X), s(Y)) -> p(minus(X, Y)) [1] p(s(X)) -> X [1] div(0, s(Y)) -> 0 [1] div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [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: minus(X, 0) -> X [1] minus(s(X), s(Y)) -> p(minus(X, Y)) [1] p(s(X)) -> X [1] div(0, s(Y)) -> 0 [1] div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] The TRS has the following type information: minus :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div 0 :: 0:s:cons_minus:cons_p:cons_div s :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div p :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div div :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div encArg :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div cons_minus :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div cons_p :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div cons_div :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div encode_minus :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div encode_0 :: 0:s:cons_minus:cons_p:cons_div encode_s :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div encode_p :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div encode_div :: 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div -> 0:s:cons_minus:cons_p:cons_div 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_minus(v0, v1) -> null_encode_minus [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_p(v0) -> null_encode_p [0] encode_div(v0, v1) -> null_encode_div [0] minus(v0, v1) -> null_minus [0] p(v0) -> null_p [0] div(v0, v1) -> null_div [0] And the following fresh constants: null_encArg, null_encode_minus, null_encode_0, null_encode_s, null_encode_p, null_encode_div, null_minus, null_p, null_div ---------------------------------------- (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: minus(X, 0) -> X [1] minus(s(X), s(Y)) -> p(minus(X, Y)) [1] p(s(X)) -> X [1] div(0, s(Y)) -> 0 [1] div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] encArg(v0) -> null_encArg [0] encode_minus(v0, v1) -> null_encode_minus [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_p(v0) -> null_encode_p [0] encode_div(v0, v1) -> null_encode_div [0] minus(v0, v1) -> null_minus [0] p(v0) -> null_p [0] div(v0, v1) -> null_div [0] The TRS has the following type information: minus :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div 0 :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div s :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div p :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div div :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div encArg :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div cons_minus :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div cons_p :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div cons_div :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div encode_minus :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div encode_0 :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div encode_s :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div encode_p :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div encode_div :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div -> 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_encArg :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_encode_minus :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_encode_0 :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_encode_s :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_encode_p :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_encode_div :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_minus :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_p :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div null_div :: 0:s:cons_minus:cons_p:cons_div:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_p:null_encode_div:null_minus:null_p:null_div 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: 0 => 0 null_encArg => 0 null_encode_minus => 0 null_encode_0 => 0 null_encode_s => 0 null_encode_p => 0 null_encode_div => 0 null_minus => 0 null_p => 0 null_div => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: div(z, z') -{ 1 }-> 0 :|: Y >= 0, z' = 1 + Y, z = 0 div(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 div(z, z') -{ 1 }-> 1 + div(minus(X, Y), 1 + Y) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 encArg(z) -{ 0 }-> p(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> minus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 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_div(z, z') -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_div(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_minus(z, z') -{ 0 }-> minus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_p(z) -{ 0 }-> p(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 minus(z, z') -{ 1 }-> X :|: X >= 0, z = X, z' = 0 minus(z, z') -{ 1 }-> p(minus(X, Y)) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 p(z) -{ 1 }-> X :|: z = 1 + X, X >= 0 p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 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),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[p(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[div(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun1(Out)],[]). eq(start(V1, V),0,[fun2(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun3(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun4(V1, V, Out)],[V1 >= 0,V >= 0]). eq(minus(V1, V, Out),1,[],[Out = X1,X1 >= 0,V1 = X1,V = 0]). eq(minus(V1, V, Out),1,[minus(X2, Y1, Ret0),p(Ret0, Ret)],[Out = Ret,V1 = 1 + X2,Y1 >= 0,V = 1 + Y1,X2 >= 0]). eq(p(V1, Out),1,[],[Out = X3,V1 = 1 + X3,X3 >= 0]). eq(div(V1, V, Out),1,[],[Out = 0,Y2 >= 0,V = 1 + Y2,V1 = 0]). eq(div(V1, V, Out),1,[minus(X4, Y3, Ret10),div(Ret10, 1 + Y3, Ret1)],[Out = 1 + Ret1,V1 = 1 + X4,Y3 >= 0,V = 1 + Y3,X4 >= 0]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[encArg(V2, Ret11)],[Out = 1 + Ret11,V1 = 1 + V2,V2 >= 0]). eq(encArg(V1, Out),0,[encArg(V3, Ret01),encArg(V4, Ret12),minus(Ret01, Ret12, Ret2)],[Out = Ret2,V3 >= 0,V1 = 1 + V3 + V4,V4 >= 0]). eq(encArg(V1, Out),0,[encArg(V5, Ret02),p(Ret02, Ret3)],[Out = Ret3,V1 = 1 + V5,V5 >= 0]). eq(encArg(V1, Out),0,[encArg(V7, Ret03),encArg(V6, Ret13),div(Ret03, Ret13, Ret4)],[Out = Ret4,V7 >= 0,V1 = 1 + V6 + V7,V6 >= 0]). eq(fun(V1, V, Out),0,[encArg(V9, Ret04),encArg(V8, Ret14),minus(Ret04, Ret14, Ret5)],[Out = Ret5,V9 >= 0,V8 >= 0,V1 = V9,V = V8]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, Out),0,[encArg(V10, Ret15)],[Out = 1 + Ret15,V10 >= 0,V1 = V10]). eq(fun3(V1, Out),0,[encArg(V11, Ret05),p(Ret05, Ret6)],[Out = Ret6,V11 >= 0,V1 = V11]). eq(fun4(V1, V, Out),0,[encArg(V13, Ret06),encArg(V12, Ret16),div(Ret06, Ret16, Ret7)],[Out = Ret7,V13 >= 0,V12 >= 0,V1 = V13,V = V12]). eq(encArg(V1, Out),0,[],[Out = 0,V14 >= 0,V1 = V14]). eq(fun(V1, V, Out),0,[],[Out = 0,V16 >= 0,V15 >= 0,V1 = V16,V = V15]). eq(fun2(V1, Out),0,[],[Out = 0,V17 >= 0,V1 = V17]). eq(fun3(V1, Out),0,[],[Out = 0,V18 >= 0,V1 = V18]). eq(fun4(V1, V, Out),0,[],[Out = 0,V19 >= 0,V20 >= 0,V1 = V19,V = V20]). eq(minus(V1, V, Out),0,[],[Out = 0,V21 >= 0,V22 >= 0,V1 = V21,V = V22]). eq(p(V1, Out),0,[],[Out = 0,V23 >= 0,V1 = V23]). eq(div(V1, V, Out),0,[],[Out = 0,V24 >= 0,V25 >= 0,V1 = V24,V = V25]). input_output_vars(minus(V1,V,Out),[V1,V],[Out]). input_output_vars(p(V1,Out),[V1],[Out]). input_output_vars(div(V1,V,Out),[V1,V],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(Out),[],[Out]). input_output_vars(fun2(V1,Out),[V1],[Out]). input_output_vars(fun3(V1,Out),[V1],[Out]). input_output_vars(fun4(V1,V,Out),[V1,V],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [p/2] 1. recursive [non_tail] : [minus/3] 2. recursive : [(div)/3] 3. recursive [non_tail,multiple] : [encArg/2] 4. non_recursive : [fun/3] 5. non_recursive : [fun1/1] 6. non_recursive : [fun2/2] 7. non_recursive : [fun3/2] 8. non_recursive : [fun4/3] 9. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into p/2 1. SCC is partially evaluated into minus/3 2. SCC is partially evaluated into (div)/3 3. SCC is partially evaluated into encArg/2 4. SCC is partially evaluated into fun/3 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into fun2/2 7. SCC is partially evaluated into fun3/2 8. SCC is partially evaluated into fun4/3 9. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations p/2 * CE 13 is refined into CE [31] * CE 14 is refined into CE [32] ### Cost equations --> "Loop" of p/2 * CEs [31] --> Loop 16 * CEs [32] --> Loop 17 ### Ranking functions of CR p(V1,Out) #### Partial ranking functions of CR p(V1,Out) ### Specialization of cost equations minus/3 * CE 12 is refined into CE [33] * CE 10 is refined into CE [34] * CE 11 is refined into CE [35,36] ### Cost equations --> "Loop" of minus/3 * CEs [36] --> Loop 18 * CEs [35] --> Loop 19 * CEs [33] --> Loop 20 * CEs [34] --> Loop 21 ### Ranking functions of CR minus(V1,V,Out) * RF of phase [18]: [V,V1] * RF of phase [19]: [V,V1] #### Partial ranking functions of CR minus(V1,V,Out) * Partial RF of phase [18]: - RF of loop [18:1]: V V1 * Partial RF of phase [19]: - RF of loop [19:1]: V V1 ### Specialization of cost equations (div)/3 * CE 15 is refined into CE [37] * CE 17 is refined into CE [38] * CE 16 is refined into CE [39,40,41] ### Cost equations --> "Loop" of (div)/3 * CEs [41] --> Loop 22 * CEs [40] --> Loop 23 * CEs [39] --> Loop 24 * CEs [37,38] --> Loop 25 ### Ranking functions of CR div(V1,V,Out) * RF of phase [22]: [V1/3-2/3,V1/3-2/3*V+2/3] * RF of phase [24]: [V1] #### Partial ranking functions of CR div(V1,V,Out) * Partial RF of phase [22]: - RF of loop [22:1]: V1/3-2/3 V1/3-2/3*V+2/3 * Partial RF of phase [24]: - RF of loop [24:1]: V1 ### Specialization of cost equations encArg/2 * CE 18 is refined into CE [42] * CE 20 is refined into CE [43,44,45] * CE 22 is refined into CE [46,47,48,49,50] * CE 19 is refined into CE [51] * CE 21 is refined into CE [52,53] ### Cost equations --> "Loop" of encArg/2 * CEs [51] --> Loop 26 * CEs [53] --> Loop 27 * CEs [52] --> Loop 28 * CEs [50] --> Loop 29 * CEs [49] --> Loop 30 * CEs [45] --> Loop 31 * CEs [46] --> Loop 32 * CEs [43] --> Loop 33 * CEs [48] --> Loop 34 * CEs [44,47] --> Loop 35 * CEs [42] --> Loop 36 ### Ranking functions of CR encArg(V1,Out) * RF of phase [26,27,28,29,30,31,32,33,34,35]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [26,27,28,29,30,31,32,33,34,35]: - RF of loop [26:1,27:1,28:1,29:1,29:2,30:1,30:2,31:1,31:2,32:1,32:2,33:1,33:2,34:1,34:2,35:1,35:2]: V1 ### Specialization of cost equations fun/3 * CE 23 is refined into CE [54,55,56,57,58,59,60,61,62] * CE 24 is refined into CE [63] ### Cost equations --> "Loop" of fun/3 * CEs [58,60,62] --> Loop 37 * CEs [54,55,56,57,59,61,63] --> Loop 38 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations fun2/2 * CE 25 is refined into CE [64,65] * CE 26 is refined into CE [66] ### Cost equations --> "Loop" of fun2/2 * CEs [65] --> Loop 39 * CEs [64] --> Loop 40 * CEs [66] --> Loop 41 ### Ranking functions of CR fun2(V1,Out) #### Partial ranking functions of CR fun2(V1,Out) ### Specialization of cost equations fun3/2 * CE 27 is refined into CE [67,68,69] * CE 28 is refined into CE [70] ### Cost equations --> "Loop" of fun3/2 * CEs [69] --> Loop 42 * CEs [67,68,70] --> Loop 43 ### Ranking functions of CR fun3(V1,Out) #### Partial ranking functions of CR fun3(V1,Out) ### Specialization of cost equations fun4/3 * CE 29 is refined into CE [71,72,73,74,75,76,77,78] * CE 30 is refined into CE [79] ### Cost equations --> "Loop" of fun4/3 * CEs [74,76,77,78] --> Loop 44 * CEs [71,72,73,75,79] --> Loop 45 ### Ranking functions of CR fun4(V1,V,Out) #### Partial ranking functions of CR fun4(V1,V,Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [80,81,82] * CE 2 is refined into CE [83,84] * CE 3 is refined into CE [85,86,87,88,89] * CE 4 is refined into CE [90,91] * CE 5 is refined into CE [92,93] * CE 6 is refined into CE [94] * CE 7 is refined into CE [95,96,97] * CE 8 is refined into CE [98,99] * CE 9 is refined into CE [100,101] ### Cost equations --> "Loop" of start/2 * CEs [80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101] --> Loop 46 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of p(V1,Out): * Chain [17]: 0 with precondition: [Out=0,V1>=0] * Chain [16]: 1 with precondition: [V1=Out+1,V1>=1] #### Cost of chains of minus(V1,V,Out): * Chain [[19],[18],21]: 3*it(18)+1 Such that:aux(1) =< V it(18) =< aux(1) with precondition: [Out=0,V>=2,V1>=V+1] * Chain [[19],21]: 1*it(19)+1 Such that:it(19) =< V with precondition: [Out=0,V>=1,V1>=V] * Chain [[19],20]: 1*it(19)+0 Such that:it(19) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [[18],21]: 2*it(18)+1 Such that:it(18) =< V with precondition: [V1=2*V+Out,V>=1,V1>=2*V] * Chain [21]: 1 with precondition: [V=0,V1=Out,V1>=0] * Chain [20]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of div(V1,V,Out): * Chain [[24],25]: 2*it(24)+1 Such that:it(24) =< Out with precondition: [V=1,Out>=1,V1>=Out] * Chain [[24],23,25]: 2*it(24)+5*s(6)+3 Such that:s(5) =< 1 it(24) =< Out s(6) =< s(5) with precondition: [V=1,Out>=2,V1>=Out] * Chain [[22],25]: 2*it(22)+2*s(9)+1 Such that:it(22) =< V1/3-2/3*V+2/3 s(9) =< 2/3*V1-V/3+2/3 with precondition: [V>=2,Out>=1,V1+4>=3*Out+2*V] * Chain [[22],23,25]: 2*it(22)+5*s(6)+2*s(9)+3 Such that:it(22) =< V1/3-2/3*V+2/3 s(9) =< 2/3*V1 s(5) =< V s(6) =< s(5) with precondition: [V>=2,Out>=2,V1+6>=3*Out+2*V] * Chain [25]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [23,25]: 5*s(6)+3 Such that:s(5) =< V s(6) =< s(5) with precondition: [Out=1,V1>=1,V>=1] #### Cost of chains of encArg(V1,Out): * Chain [36]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([26,27,28,29,30,31,32,33,34,35],[[36]])]: 3*it(27)+3*it(29)+1*it(30)+1*it(31)+6*it(32)+7*s(43)+2*s(44)+2*s(46)+2*s(47)+2*s(48)+4*s(49)+5*s(50)+5*s(53)+5*s(55)+0 Such that:aux(22) =< V1 aux(23) =< V1/2 aux(24) =< V1/4 aux(25) =< 2/5*V1 aux(26) =< 2/7*V1 it(27) =< aux(22) it(29) =< aux(22) it(30) =< aux(22) it(31) =< aux(22) it(32) =< aux(22) it(32) =< aux(23) it(29) =< aux(24) it(31) =< aux(25) it(30) =< aux(26) aux(15) =< aux(22) aux(17) =< aux(22)-1 aux(12) =< aux(22)-2 aux(9) =< aux(22)*(1/3)-1/3 aux(7) =< aux(22)*(2/3)-2/3 s(56) =< it(27)*aux(15) s(54) =< it(32)*aux(17) s(52) =< it(32)*aux(15) s(48) =< it(31)*aux(12) aux(10) =< it(30)*aux(9) s(46) =< it(30)*aux(9) s(44) =< it(29)*aux(7) s(45) =< it(29)*aux(22) s(47) =< aux(10)*2 s(55) =< s(56) s(53) =< s(54) s(49) =< s(52) s(50) =< aux(23) s(43) =< s(45) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,Out): * Chain [38]: 19*s(64)+9*s(65)+3*s(66)+3*s(67)+18*s(68)+6*s(77)+6*s(79)+6*s(80)+6*s(82)+15*s(83)+15*s(84)+12*s(85)+15*s(86)+21*s(87)+6*s(124)+6*s(125)+2*s(126)+2*s(127)+12*s(128)+4*s(137)+4*s(139)+4*s(140)+4*s(142)+10*s(143)+10*s(144)+8*s(145)+10*s(146)+14*s(147)+1 Such that:aux(29) =< V1 aux(30) =< V1/2 aux(31) =< V1/4 aux(32) =< 2/5*V1 aux(33) =< 2/7*V1 aux(34) =< V aux(35) =< V/2 aux(36) =< V/4 aux(37) =< 2/5*V aux(38) =< 2/7*V s(124) =< aux(29) s(125) =< aux(29) s(126) =< aux(29) s(127) =< aux(29) s(128) =< aux(29) s(128) =< aux(30) s(125) =< aux(31) s(127) =< aux(32) s(126) =< aux(33) s(129) =< aux(29) s(130) =< aux(29)-1 s(131) =< aux(29)-2 s(132) =< aux(29)*(1/3)-1/3 s(133) =< aux(29)*(2/3)-2/3 s(134) =< s(124)*s(129) s(135) =< s(128)*s(130) s(136) =< s(128)*s(129) s(137) =< s(127)*s(131) s(138) =< s(126)*s(132) s(139) =< s(126)*s(132) s(140) =< s(125)*s(133) s(141) =< s(125)*aux(29) s(142) =< s(138)*2 s(143) =< s(134) s(144) =< s(135) s(145) =< s(136) s(146) =< aux(30) s(147) =< s(141) s(64) =< aux(34) s(65) =< aux(34) s(66) =< aux(34) s(67) =< aux(34) s(68) =< aux(34) s(68) =< aux(35) s(65) =< aux(36) s(67) =< aux(37) s(66) =< aux(38) s(69) =< aux(34) s(70) =< aux(34)-1 s(71) =< aux(34)-2 s(72) =< aux(34)*(1/3)-1/3 s(73) =< aux(34)*(2/3)-2/3 s(74) =< s(64)*s(69) s(75) =< s(68)*s(70) s(76) =< s(68)*s(69) s(77) =< s(67)*s(71) s(78) =< s(66)*s(72) s(79) =< s(66)*s(72) s(80) =< s(65)*s(73) s(81) =< s(65)*aux(34) s(82) =< s(78)*2 s(83) =< s(74) s(84) =< s(75) s(85) =< s(76) s(86) =< aux(35) s(87) =< s(81) with precondition: [Out=0,V1>=0,V>=0] * Chain [37]: 9*s(215)+9*s(216)+3*s(217)+3*s(218)+18*s(219)+6*s(228)+6*s(230)+6*s(231)+6*s(233)+15*s(234)+15*s(235)+12*s(236)+15*s(237)+21*s(238)+8*s(273)+6*s(274)+2*s(275)+2*s(276)+12*s(277)+4*s(286)+4*s(288)+4*s(289)+4*s(291)+10*s(292)+10*s(293)+8*s(294)+10*s(295)+14*s(296)+1 Such that:aux(40) =< V1 aux(41) =< V1/2 aux(42) =< V1/4 aux(43) =< 2/5*V1 aux(44) =< 2/7*V1 aux(45) =< V aux(46) =< V/2 aux(47) =< V/4 aux(48) =< 2/5*V aux(49) =< 2/7*V s(215) =< aux(40) s(216) =< aux(40) s(217) =< aux(40) s(218) =< aux(40) s(219) =< aux(40) s(219) =< aux(41) s(216) =< aux(42) s(218) =< aux(43) s(217) =< aux(44) s(220) =< aux(40) s(221) =< aux(40)-1 s(222) =< aux(40)-2 s(223) =< aux(40)*(1/3)-1/3 s(224) =< aux(40)*(2/3)-2/3 s(225) =< s(215)*s(220) s(226) =< s(219)*s(221) s(227) =< s(219)*s(220) s(228) =< s(218)*s(222) s(229) =< s(217)*s(223) s(230) =< s(217)*s(223) s(231) =< s(216)*s(224) s(232) =< s(216)*aux(40) s(233) =< s(229)*2 s(234) =< s(225) s(235) =< s(226) s(236) =< s(227) s(237) =< aux(41) s(238) =< s(232) s(273) =< aux(45) s(274) =< aux(45) s(275) =< aux(45) s(276) =< aux(45) s(277) =< aux(45) s(277) =< aux(46) s(274) =< aux(47) s(276) =< aux(48) s(275) =< aux(49) s(278) =< aux(45) s(279) =< aux(45)-1 s(280) =< aux(45)-2 s(281) =< aux(45)*(1/3)-1/3 s(282) =< aux(45)*(2/3)-2/3 s(283) =< s(273)*s(278) s(284) =< s(277)*s(279) s(285) =< s(277)*s(278) s(286) =< s(276)*s(280) s(287) =< s(275)*s(281) s(288) =< s(275)*s(281) s(289) =< s(274)*s(282) s(290) =< s(274)*aux(45) s(291) =< s(287)*2 s(292) =< s(283) s(293) =< s(284) s(294) =< s(285) s(295) =< aux(46) s(296) =< s(290) with precondition: [V1>=1,V>=0,Out>=0,V1>=Out] #### Cost of chains of fun2(V1,Out): * Chain [41]: 0 with precondition: [Out=0,V1>=0] * Chain [40]: 0 with precondition: [Out=1,V1>=0] * Chain [39]: 3*s(361)+3*s(362)+1*s(363)+1*s(364)+6*s(365)+2*s(374)+2*s(376)+2*s(377)+2*s(379)+5*s(380)+5*s(381)+4*s(382)+5*s(383)+7*s(384)+0 Such that:s(356) =< V1 s(357) =< V1/2 s(358) =< V1/4 s(359) =< 2/5*V1 s(360) =< 2/7*V1 s(361) =< s(356) s(362) =< s(356) s(363) =< s(356) s(364) =< s(356) s(365) =< s(356) s(365) =< s(357) s(362) =< s(358) s(364) =< s(359) s(363) =< s(360) s(366) =< s(356) s(367) =< s(356)-1 s(368) =< s(356)-2 s(369) =< s(356)*(1/3)-1/3 s(370) =< s(356)*(2/3)-2/3 s(371) =< s(361)*s(366) s(372) =< s(365)*s(367) s(373) =< s(365)*s(366) s(374) =< s(364)*s(368) s(375) =< s(363)*s(369) s(376) =< s(363)*s(369) s(377) =< s(362)*s(370) s(378) =< s(362)*s(356) s(379) =< s(375)*2 s(380) =< s(371) s(381) =< s(372) s(382) =< s(373) s(383) =< s(357) s(384) =< s(378) with precondition: [V1>=1,Out>=1,V1+1>=Out] #### Cost of chains of fun3(V1,Out): * Chain [43]: 3*s(390)+3*s(391)+1*s(392)+1*s(393)+6*s(394)+2*s(403)+2*s(405)+2*s(406)+2*s(408)+5*s(409)+5*s(410)+4*s(411)+5*s(412)+7*s(413)+0 Such that:s(385) =< V1 s(386) =< V1/2 s(387) =< V1/4 s(388) =< 2/5*V1 s(389) =< 2/7*V1 s(390) =< s(385) s(391) =< s(385) s(392) =< s(385) s(393) =< s(385) s(394) =< s(385) s(394) =< s(386) s(391) =< s(387) s(393) =< s(388) s(392) =< s(389) s(395) =< s(385) s(396) =< s(385)-1 s(397) =< s(385)-2 s(398) =< s(385)*(1/3)-1/3 s(399) =< s(385)*(2/3)-2/3 s(400) =< s(390)*s(395) s(401) =< s(394)*s(396) s(402) =< s(394)*s(395) s(403) =< s(393)*s(397) s(404) =< s(392)*s(398) s(405) =< s(392)*s(398) s(406) =< s(391)*s(399) s(407) =< s(391)*s(385) s(408) =< s(404)*2 s(409) =< s(400) s(410) =< s(401) s(411) =< s(402) s(412) =< s(386) s(413) =< s(407) with precondition: [Out=0,V1>=0] * Chain [42]: 3*s(419)+3*s(420)+1*s(421)+1*s(422)+6*s(423)+2*s(432)+2*s(434)+2*s(435)+2*s(437)+5*s(438)+5*s(439)+4*s(440)+5*s(441)+7*s(442)+1 Such that:s(414) =< V1 s(415) =< V1/2 s(416) =< V1/4 s(417) =< 2/5*V1 s(418) =< 2/7*V1 s(419) =< s(414) s(420) =< s(414) s(421) =< s(414) s(422) =< s(414) s(423) =< s(414) s(423) =< s(415) s(420) =< s(416) s(422) =< s(417) s(421) =< s(418) s(424) =< s(414) s(425) =< s(414)-1 s(426) =< s(414)-2 s(427) =< s(414)*(1/3)-1/3 s(428) =< s(414)*(2/3)-2/3 s(429) =< s(419)*s(424) s(430) =< s(423)*s(425) s(431) =< s(423)*s(424) s(432) =< s(422)*s(426) s(433) =< s(421)*s(427) s(434) =< s(421)*s(427) s(435) =< s(420)*s(428) s(436) =< s(420)*s(414) s(437) =< s(433)*2 s(438) =< s(429) s(439) =< s(430) s(440) =< s(431) s(441) =< s(415) s(442) =< s(436) with precondition: [Out>=0,V1>=Out+1] #### Cost of chains of fun4(V1,V,Out): * Chain [45]: 6*s(448)+6*s(449)+2*s(450)+2*s(451)+12*s(452)+4*s(461)+4*s(463)+4*s(464)+4*s(466)+10*s(467)+10*s(468)+8*s(469)+10*s(470)+14*s(471)+6*s(477)+6*s(478)+2*s(479)+2*s(480)+12*s(481)+4*s(490)+4*s(492)+4*s(493)+4*s(495)+10*s(496)+10*s(497)+8*s(498)+10*s(499)+14*s(500)+1 Such that:aux(50) =< V1 aux(51) =< V1/2 aux(52) =< V1/4 aux(53) =< 2/5*V1 aux(54) =< 2/7*V1 aux(55) =< V aux(56) =< V/2 aux(57) =< V/4 aux(58) =< 2/5*V aux(59) =< 2/7*V s(477) =< aux(50) s(478) =< aux(50) s(479) =< aux(50) s(480) =< aux(50) s(481) =< aux(50) s(481) =< aux(51) s(478) =< aux(52) s(480) =< aux(53) s(479) =< aux(54) s(482) =< aux(50) s(483) =< aux(50)-1 s(484) =< aux(50)-2 s(485) =< aux(50)*(1/3)-1/3 s(486) =< aux(50)*(2/3)-2/3 s(487) =< s(477)*s(482) s(488) =< s(481)*s(483) s(489) =< s(481)*s(482) s(490) =< s(480)*s(484) s(491) =< s(479)*s(485) s(492) =< s(479)*s(485) s(493) =< s(478)*s(486) s(494) =< s(478)*aux(50) s(495) =< s(491)*2 s(496) =< s(487) s(497) =< s(488) s(498) =< s(489) s(499) =< aux(51) s(500) =< s(494) s(448) =< aux(55) s(449) =< aux(55) s(450) =< aux(55) s(451) =< aux(55) s(452) =< aux(55) s(452) =< aux(56) s(449) =< aux(57) s(451) =< aux(58) s(450) =< aux(59) s(453) =< aux(55) s(454) =< aux(55)-1 s(455) =< aux(55)-2 s(456) =< aux(55)*(1/3)-1/3 s(457) =< aux(55)*(2/3)-2/3 s(458) =< s(448)*s(453) s(459) =< s(452)*s(454) s(460) =< s(452)*s(453) s(461) =< s(451)*s(455) s(462) =< s(450)*s(456) s(463) =< s(450)*s(456) s(464) =< s(449)*s(457) s(465) =< s(449)*aux(55) s(466) =< s(462)*2 s(467) =< s(458) s(468) =< s(459) s(469) =< s(460) s(470) =< aux(56) s(471) =< s(465) with precondition: [Out=0,V1>=0,V>=0] * Chain [44]: 16*s(564)+12*s(565)+4*s(566)+4*s(567)+24*s(568)+8*s(577)+8*s(579)+8*s(580)+8*s(582)+20*s(583)+20*s(584)+16*s(585)+20*s(586)+28*s(587)+17*s(593)+12*s(594)+4*s(595)+4*s(596)+24*s(597)+8*s(606)+8*s(608)+8*s(609)+8*s(611)+20*s(612)+20*s(613)+16*s(614)+20*s(615)+28*s(616)+5*s(620)+2*s(739)+4*s(740)+7*s(799)+3 Such that:s(617) =< 1 aux(62) =< V1+2 s(739) =< V1/3 aux(63) =< V1 aux(64) =< V1/2 aux(65) =< V1/4 aux(66) =< 2/3*V1 aux(67) =< 2/5*V1 aux(68) =< 2/7*V1 aux(69) =< V aux(70) =< V/2 aux(71) =< V/4 aux(72) =< 2/5*V aux(73) =< 2/7*V s(740) =< aux(66) s(564) =< aux(63) s(620) =< s(617) s(593) =< aux(69) s(594) =< aux(69) s(595) =< aux(69) s(596) =< aux(69) s(597) =< aux(69) s(597) =< aux(70) s(594) =< aux(71) s(596) =< aux(72) s(595) =< aux(73) s(598) =< aux(69) s(599) =< aux(69)-1 s(600) =< aux(69)-2 s(601) =< aux(69)*(1/3)-1/3 s(602) =< aux(69)*(2/3)-2/3 s(603) =< s(593)*s(598) s(604) =< s(597)*s(599) s(605) =< s(597)*s(598) s(606) =< s(596)*s(600) s(607) =< s(595)*s(601) s(608) =< s(595)*s(601) s(609) =< s(594)*s(602) s(610) =< s(594)*aux(69) s(611) =< s(607)*2 s(612) =< s(603) s(613) =< s(604) s(614) =< s(605) s(615) =< aux(70) s(616) =< s(610) s(565) =< aux(63) s(566) =< aux(63) s(567) =< aux(63) s(568) =< aux(63) s(568) =< aux(64) s(565) =< aux(65) s(567) =< aux(67) s(566) =< aux(68) s(569) =< aux(63) s(570) =< aux(63)-1 s(571) =< aux(63)-2 s(572) =< aux(63)*(1/3)-1/3 s(573) =< aux(63)*(2/3)-2/3 s(574) =< s(564)*s(569) s(575) =< s(568)*s(570) s(576) =< s(568)*s(569) s(577) =< s(567)*s(571) s(578) =< s(566)*s(572) s(579) =< s(566)*s(572) s(580) =< s(565)*s(573) s(581) =< s(565)*aux(63) s(582) =< s(578)*2 s(583) =< s(574) s(584) =< s(575) s(585) =< s(576) s(586) =< aux(64) s(587) =< s(581) s(799) =< aux(62) with precondition: [V>=1,Out>=1,V1>=Out] #### Cost of chains of start(V1,V): * Chain [46]: 67*s(804)+53*s(808)+10*s(809)+4*s(812)+2*s(813)+6*s(815)+45*s(824)+15*s(825)+15*s(826)+90*s(827)+30*s(836)+30*s(838)+30*s(839)+30*s(841)+75*s(842)+75*s(843)+60*s(844)+75*s(845)+105*s(846)+33*s(882)+11*s(883)+11*s(884)+66*s(885)+22*s(894)+22*s(896)+22*s(897)+22*s(899)+55*s(900)+55*s(901)+44*s(902)+55*s(903)+77*s(904)+2*s(1110)+7*s(1172)+3 Such that:s(1109) =< V1+2 s(1110) =< V1/3 s(813) =< 2/3*V1-V/3+2/3 aux(74) =< 1 aux(75) =< V1 aux(76) =< V1/2 aux(77) =< V1/3-2/3*V+2/3 aux(78) =< V1/4 aux(79) =< 2/3*V1 aux(80) =< 2/5*V1 aux(81) =< 2/7*V1 aux(82) =< V aux(83) =< V/2 aux(84) =< V/4 aux(85) =< 2/5*V aux(86) =< 2/7*V s(812) =< aux(77) s(815) =< aux(79) s(804) =< aux(82) s(808) =< aux(75) s(809) =< aux(74) s(882) =< aux(82) s(883) =< aux(82) s(884) =< aux(82) s(885) =< aux(82) s(885) =< aux(83) s(882) =< aux(84) s(884) =< aux(85) s(883) =< aux(86) s(886) =< aux(82) s(887) =< aux(82)-1 s(888) =< aux(82)-2 s(889) =< aux(82)*(1/3)-1/3 s(890) =< aux(82)*(2/3)-2/3 s(891) =< s(804)*s(886) s(892) =< s(885)*s(887) s(893) =< s(885)*s(886) s(894) =< s(884)*s(888) s(895) =< s(883)*s(889) s(896) =< s(883)*s(889) s(897) =< s(882)*s(890) s(898) =< s(882)*aux(82) s(899) =< s(895)*2 s(900) =< s(891) s(901) =< s(892) s(902) =< s(893) s(903) =< aux(83) s(904) =< s(898) s(824) =< aux(75) s(825) =< aux(75) s(826) =< aux(75) s(827) =< aux(75) s(827) =< aux(76) s(824) =< aux(78) s(826) =< aux(80) s(825) =< aux(81) s(828) =< aux(75) s(829) =< aux(75)-1 s(830) =< aux(75)-2 s(831) =< aux(75)*(1/3)-1/3 s(832) =< aux(75)*(2/3)-2/3 s(833) =< s(808)*s(828) s(834) =< s(827)*s(829) s(835) =< s(827)*s(828) s(836) =< s(826)*s(830) s(837) =< s(825)*s(831) s(838) =< s(825)*s(831) s(839) =< s(824)*s(832) s(840) =< s(824)*aux(75) s(841) =< s(837)*2 s(842) =< s(833) s(843) =< s(834) s(844) =< s(835) s(845) =< aux(76) s(846) =< s(840) s(1172) =< s(1109) with precondition: [] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [46] with precondition: [] - Upper bound: nat(V1)*218+13+nat(V1)*240*nat(V1)+nat(V1)*30*nat(nat(V1)+ -2)+nat(V1)*75*nat(nat(V1)+ -1)+nat(V1)*30*nat(-2/3+2/3*nat(V1))+nat(V1)*90*nat(-1/3+1/3*nat(V1))+nat(V)*188+nat(V)*176*nat(V)+nat(V)*22*nat(nat(V)+ -2)+nat(V)*55*nat(nat(V)+ -1)+nat(V)*22*nat(-2/3+2/3*nat(V))+nat(V)*66*nat(-1/3+1/3*nat(V))+nat(2/3*V1)*6+nat(V1+2)*7+nat(2/3*V1-V/3+2/3)*2+nat(V1/3-2/3*V+2/3)*4+nat(V1/2)*75+nat(V1/3)*2+nat(V/2)*55 - Complexity: n^2 ### Maximum cost of start(V1,V): nat(V1)*218+13+nat(V1)*240*nat(V1)+nat(V1)*30*nat(nat(V1)+ -2)+nat(V1)*75*nat(nat(V1)+ -1)+nat(V1)*30*nat(-2/3+2/3*nat(V1))+nat(V1)*90*nat(-1/3+1/3*nat(V1))+nat(V)*188+nat(V)*176*nat(V)+nat(V)*22*nat(nat(V)+ -2)+nat(V)*55*nat(nat(V)+ -1)+nat(V)*22*nat(-2/3+2/3*nat(V))+nat(V)*66*nat(-1/3+1/3*nat(V))+nat(2/3*V1)*6+nat(V1+2)*7+nat(2/3*V1-V/3+2/3)*2+nat(V1/3-2/3*V+2/3)*4+nat(V1/2)*75+nat(V1/3)*2+nat(V/2)*55 Asymptotic class: n^2 * Total analysis performed in 2090 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: minus(X, 0') -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0', s(Y)) -> 0' div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) The (relative) TRS S consists of the following rules: encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: minus(X, 0') -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0', s(Y)) -> 0' div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div 0' :: 0':s:cons_minus:cons_p:cons_div s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encArg :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_0 :: 0':s:cons_minus:cons_p:cons_div encode_s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div hole_0':s:cons_minus:cons_p:cons_div1_3 :: 0':s:cons_minus:cons_p:cons_div gen_0':s:cons_minus:cons_p:cons_div2_3 :: Nat -> 0':s:cons_minus:cons_p:cons_div ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: minus, div, encArg They will be analysed ascendingly in the following order: minus < div minus < encArg div < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: minus(X, 0') -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0', s(Y)) -> 0' div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div 0' :: 0':s:cons_minus:cons_p:cons_div s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encArg :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_0 :: 0':s:cons_minus:cons_p:cons_div encode_s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div hole_0':s:cons_minus:cons_p:cons_div1_3 :: 0':s:cons_minus:cons_p:cons_div gen_0':s:cons_minus:cons_p:cons_div2_3 :: Nat -> 0':s:cons_minus:cons_p:cons_div Generator Equations: gen_0':s:cons_minus:cons_p:cons_div2_3(0) <=> 0' gen_0':s:cons_minus:cons_p:cons_div2_3(+(x, 1)) <=> s(gen_0':s:cons_minus:cons_p:cons_div2_3(x)) The following defined symbols remain to be analysed: minus, div, encArg They will be analysed ascendingly in the following order: minus < div minus < encArg div < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: minus(gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3)), gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3))) -> *3_3, rt in Omega(n4_3) Induction Base: minus(gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, 0)), gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, 0))) Induction Step: minus(gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, +(n4_3, 1))), gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, +(n4_3, 1)))) ->_R^Omega(1) p(minus(gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3)), gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3)))) ->_IH p(*3_3) 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: minus(X, 0') -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0', s(Y)) -> 0' div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div 0' :: 0':s:cons_minus:cons_p:cons_div s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encArg :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_0 :: 0':s:cons_minus:cons_p:cons_div encode_s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div hole_0':s:cons_minus:cons_p:cons_div1_3 :: 0':s:cons_minus:cons_p:cons_div gen_0':s:cons_minus:cons_p:cons_div2_3 :: Nat -> 0':s:cons_minus:cons_p:cons_div Generator Equations: gen_0':s:cons_minus:cons_p:cons_div2_3(0) <=> 0' gen_0':s:cons_minus:cons_p:cons_div2_3(+(x, 1)) <=> s(gen_0':s:cons_minus:cons_p:cons_div2_3(x)) The following defined symbols remain to be analysed: minus, div, encArg They will be analysed ascendingly in the following order: minus < div minus < encArg div < encArg ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: minus(X, 0') -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0', s(Y)) -> 0' div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div 0' :: 0':s:cons_minus:cons_p:cons_div s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encArg :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_0 :: 0':s:cons_minus:cons_p:cons_div encode_s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div hole_0':s:cons_minus:cons_p:cons_div1_3 :: 0':s:cons_minus:cons_p:cons_div gen_0':s:cons_minus:cons_p:cons_div2_3 :: Nat -> 0':s:cons_minus:cons_p:cons_div Lemmas: minus(gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3)), gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3))) -> *3_3, rt in Omega(n4_3) Generator Equations: gen_0':s:cons_minus:cons_p:cons_div2_3(0) <=> 0' gen_0':s:cons_minus:cons_p:cons_div2_3(+(x, 1)) <=> s(gen_0':s:cons_minus:cons_p:cons_div2_3(x)) The following defined symbols remain to be analysed: div, encArg They will be analysed ascendingly in the following order: div < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: div(gen_0':s:cons_minus:cons_p:cons_div2_3(n3754_3), gen_0':s:cons_minus:cons_p:cons_div2_3(1)) -> gen_0':s:cons_minus:cons_p:cons_div2_3(n3754_3), rt in Omega(1 + n3754_3) Induction Base: div(gen_0':s:cons_minus:cons_p:cons_div2_3(0), gen_0':s:cons_minus:cons_p:cons_div2_3(1)) ->_R^Omega(1) 0' Induction Step: div(gen_0':s:cons_minus:cons_p:cons_div2_3(+(n3754_3, 1)), gen_0':s:cons_minus:cons_p:cons_div2_3(1)) ->_R^Omega(1) s(div(minus(gen_0':s:cons_minus:cons_p:cons_div2_3(n3754_3), gen_0':s:cons_minus:cons_p:cons_div2_3(0)), s(gen_0':s:cons_minus:cons_p:cons_div2_3(0)))) ->_R^Omega(1) s(div(gen_0':s:cons_minus:cons_p:cons_div2_3(n3754_3), s(gen_0':s:cons_minus:cons_p:cons_div2_3(0)))) ->_IH s(gen_0':s:cons_minus:cons_p:cons_div2_3(c3755_3)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (28) Obligation: Innermost TRS: Rules: minus(X, 0') -> X minus(s(X), s(Y)) -> p(minus(X, Y)) p(s(X)) -> X div(0', s(Y)) -> 0' div(s(X), s(Y)) -> s(div(minus(X, Y), s(Y))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div 0' :: 0':s:cons_minus:cons_p:cons_div s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encArg :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div cons_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_minus :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_0 :: 0':s:cons_minus:cons_p:cons_div encode_s :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_p :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div encode_div :: 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div -> 0':s:cons_minus:cons_p:cons_div hole_0':s:cons_minus:cons_p:cons_div1_3 :: 0':s:cons_minus:cons_p:cons_div gen_0':s:cons_minus:cons_p:cons_div2_3 :: Nat -> 0':s:cons_minus:cons_p:cons_div Lemmas: minus(gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3)), gen_0':s:cons_minus:cons_p:cons_div2_3(+(1, n4_3))) -> *3_3, rt in Omega(n4_3) div(gen_0':s:cons_minus:cons_p:cons_div2_3(n3754_3), gen_0':s:cons_minus:cons_p:cons_div2_3(1)) -> gen_0':s:cons_minus:cons_p:cons_div2_3(n3754_3), rt in Omega(1 + n3754_3) Generator Equations: gen_0':s:cons_minus:cons_p:cons_div2_3(0) <=> 0' gen_0':s:cons_minus:cons_p:cons_div2_3(+(x, 1)) <=> s(gen_0':s:cons_minus:cons_p:cons_div2_3(x)) The following defined symbols remain to be analysed: encArg ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_0':s:cons_minus:cons_p:cons_div2_3(n4473_3)) -> gen_0':s:cons_minus:cons_p:cons_div2_3(n4473_3), rt in Omega(0) Induction Base: encArg(gen_0':s:cons_minus:cons_p:cons_div2_3(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_0':s:cons_minus:cons_p:cons_div2_3(+(n4473_3, 1))) ->_R^Omega(0) s(encArg(gen_0':s:cons_minus:cons_p:cons_div2_3(n4473_3))) ->_IH s(gen_0':s:cons_minus:cons_p:cons_div2_3(c4474_3)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (30) BOUNDS(1, INF)