/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/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), 168 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), 1 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 656 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), 3485 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), 0 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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b 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(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b The (relative) TRS S consists of the following rules: encArg(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b The (relative) TRS S consists of the following rules: encArg(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(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: a__f(X, X) -> a__f(a, b) [1] a__b -> a [1] mark(f(X1, X2)) -> a__f(mark(X1), X2) [1] mark(b) -> a__b [1] mark(a) -> a [1] a__f(X1, X2) -> f(X1, X2) [1] a__b -> b [1] encArg(a) -> a [0] encArg(b) -> b [0] encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) [0] encArg(cons_a__b) -> a__b [0] encArg(cons_mark(x_1)) -> mark(encArg(x_1)) [0] encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) [0] encode_a -> a [0] encode_b -> b [0] encode_a__b -> a__b [0] encode_mark(x_1) -> mark(encArg(x_1)) [0] encode_f(x_1, x_2) -> f(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: a__f(X, X) -> a__f(a, b) [1] a__b -> a [1] mark(f(X1, X2)) -> a__f(mark(X1), X2) [1] mark(b) -> a__b [1] mark(a) -> a [1] a__f(X1, X2) -> f(X1, X2) [1] a__b -> b [1] encArg(a) -> a [0] encArg(b) -> b [0] encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) [0] encArg(cons_a__b) -> a__b [0] encArg(cons_mark(x_1)) -> mark(encArg(x_1)) [0] encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) [0] encode_a -> a [0] encode_b -> b [0] encode_a__b -> a__b [0] encode_mark(x_1) -> mark(encArg(x_1)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] The TRS has the following type information: a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark a :: a:b:f:cons_a__f:cons_a__b:cons_mark b :: a:b:f:cons_a__f:cons_a__b:cons_mark a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encArg :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark cons_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark 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_a__f(v0, v1) -> null_encode_a__f [0] encode_a -> null_encode_a [0] encode_b -> null_encode_b [0] encode_a__b -> null_encode_a__b [0] encode_mark(v0) -> null_encode_mark [0] encode_f(v0, v1) -> null_encode_f [0] mark(v0) -> null_mark [0] And the following fresh constants: null_encArg, null_encode_a__f, null_encode_a, null_encode_b, null_encode_a__b, null_encode_mark, null_encode_f, null_mark ---------------------------------------- (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: a__f(X, X) -> a__f(a, b) [1] a__b -> a [1] mark(f(X1, X2)) -> a__f(mark(X1), X2) [1] mark(b) -> a__b [1] mark(a) -> a [1] a__f(X1, X2) -> f(X1, X2) [1] a__b -> b [1] encArg(a) -> a [0] encArg(b) -> b [0] encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) [0] encArg(cons_a__b) -> a__b [0] encArg(cons_mark(x_1)) -> mark(encArg(x_1)) [0] encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) [0] encode_a -> a [0] encode_b -> b [0] encode_a__b -> a__b [0] encode_mark(x_1) -> mark(encArg(x_1)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] encArg(v0) -> null_encArg [0] encode_a__f(v0, v1) -> null_encode_a__f [0] encode_a -> null_encode_a [0] encode_b -> null_encode_b [0] encode_a__b -> null_encode_a__b [0] encode_mark(v0) -> null_encode_mark [0] encode_f(v0, v1) -> null_encode_f [0] mark(v0) -> null_mark [0] The TRS has the following type information: a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark a :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark b :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark mark :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark f :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark encArg :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark cons_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark cons_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark cons_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark encode_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark encode_a :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark encode_b :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark encode_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark encode_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark encode_f :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_encArg :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_encode_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_encode_a :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_encode_b :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_encode_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_encode_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_encode_f :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark null_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark:null_encArg:null_encode_a__f:null_encode_a:null_encode_b:null_encode_a__b:null_encode_mark:null_encode_f:null_mark 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: a => 0 b => 1 cons_a__b => 2 null_encArg => 0 null_encode_a__f => 0 null_encode_a => 0 null_encode_b => 0 null_encode_a__b => 0 null_encode_mark => 0 null_encode_f => 0 null_mark => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: a__b -{ 1 }-> 1 :|: a__b -{ 1 }-> 0 :|: a__f(z, z') -{ 1 }-> a__f(0, 1) :|: z' = X, X >= 0, z = X a__f(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 encArg(z) -{ 0 }-> mark(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> a__f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> a__b :|: 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) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_a -{ 0 }-> 0 :|: encode_a__b -{ 0 }-> a__b :|: encode_a__b -{ 0 }-> 0 :|: encode_a__f(z, z') -{ 0 }-> a__f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_a__f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_b -{ 0 }-> 1 :|: encode_b -{ 0 }-> 0 :|: encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_f(z, z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_mark(z) -{ 0 }-> mark(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_mark(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 mark(z) -{ 1 }-> a__f(mark(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 mark(z) -{ 1 }-> a__b :|: z = 1 mark(z) -{ 1 }-> 0 :|: z = 0 mark(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,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun1(Out)],[]). eq(start(V1, V),0,[mark(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun3(Out)],[]). eq(start(V1, V),0,[fun4(Out)],[]). eq(start(V1, V),0,[fun5(Out)],[]). eq(start(V1, V),0,[fun6(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun7(V1, V, Out)],[V1 >= 0,V >= 0]). eq(fun(V1, V, Out),1,[fun(0, 1, Ret)],[Out = Ret,V = X3,X3 >= 0,V1 = X3]). eq(fun1(Out),1,[],[Out = 0]). eq(mark(V1, Out),1,[mark(X11, Ret0),fun(Ret0, X21, Ret1)],[Out = Ret1,X11 >= 0,X21 >= 0,V1 = 1 + X11 + X21]). eq(mark(V1, Out),1,[fun1(Ret2)],[Out = Ret2,V1 = 1]). eq(mark(V1, Out),1,[],[Out = 0,V1 = 0]). eq(fun(V1, V, Out),1,[],[Out = 1 + X12 + X22,X12 >= 0,X22 >= 0,V1 = X12,V = X22]). eq(fun1(Out),1,[],[Out = 1]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]). eq(encArg(V1, Out),0,[encArg(V3, Ret01),encArg(V2, Ret11)],[Out = 1 + Ret01 + Ret11,V3 >= 0,V1 = 1 + V2 + V3,V2 >= 0]). eq(encArg(V1, Out),0,[encArg(V4, Ret02),encArg(V5, Ret12),fun(Ret02, Ret12, Ret3)],[Out = Ret3,V4 >= 0,V1 = 1 + V4 + V5,V5 >= 0]). eq(encArg(V1, Out),0,[fun1(Ret4)],[Out = Ret4,V1 = 2]). eq(encArg(V1, Out),0,[encArg(V6, Ret03),mark(Ret03, Ret5)],[Out = Ret5,V1 = 1 + V6,V6 >= 0]). eq(fun2(V1, V, Out),0,[encArg(V8, Ret04),encArg(V7, Ret13),fun(Ret04, Ret13, Ret6)],[Out = Ret6,V8 >= 0,V7 >= 0,V1 = V8,V = V7]). eq(fun3(Out),0,[],[Out = 0]). eq(fun4(Out),0,[],[Out = 1]). eq(fun5(Out),0,[fun1(Ret7)],[Out = Ret7]). eq(fun6(V1, Out),0,[encArg(V9, Ret05),mark(Ret05, Ret8)],[Out = Ret8,V9 >= 0,V1 = V9]). eq(fun7(V1, V, Out),0,[encArg(V11, Ret011),encArg(V10, Ret14)],[Out = 1 + Ret011 + Ret14,V11 >= 0,V10 >= 0,V1 = V11,V = V10]). eq(encArg(V1, Out),0,[],[Out = 0,V12 >= 0,V1 = V12]). eq(fun2(V1, V, Out),0,[],[Out = 0,V14 >= 0,V13 >= 0,V1 = V14,V = V13]). eq(fun4(Out),0,[],[Out = 0]). eq(fun5(Out),0,[],[Out = 0]). eq(fun6(V1, Out),0,[],[Out = 0,V15 >= 0,V1 = V15]). eq(fun7(V1, V, Out),0,[],[Out = 0,V16 >= 0,V17 >= 0,V1 = V16,V = V17]). eq(mark(V1, Out),0,[],[Out = 0,V18 >= 0,V1 = V18]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(Out),[],[Out]). input_output_vars(mark(V1,Out),[V1],[Out]). input_output_vars(encArg(V1,Out),[V1],[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(Out),[],[Out]). input_output_vars(fun6(V1,Out),[V1],[Out]). input_output_vars(fun7(V1,V,Out),[V1,V],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [fun/3] 1. non_recursive : [fun1/1] 2. recursive [non_tail] : [mark/2] 3. recursive [non_tail,multiple] : [encArg/2] 4. non_recursive : [fun2/3] 5. non_recursive : [fun3/1] 6. non_recursive : [fun4/1] 7. non_recursive : [fun5/1] 8. non_recursive : [fun6/2] 9. non_recursive : [fun7/3] 10. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun/3 1. SCC is partially evaluated into fun1/1 2. SCC is partially evaluated into mark/2 3. SCC is partially evaluated into encArg/2 4. SCC is partially evaluated into fun2/3 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into fun4/1 7. SCC is partially evaluated into fun5/1 8. SCC is partially evaluated into fun6/2 9. SCC is partially evaluated into fun7/3 10. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun/3 * CE 12 is refined into CE [35] * CE 11 is refined into CE [36] ### Cost equations --> "Loop" of fun/3 * CEs [36] --> Loop 20 * CEs [35] --> Loop 21 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations fun1/1 * CE 14 is refined into CE [37] * CE 13 is refined into CE [38] ### Cost equations --> "Loop" of fun1/1 * CEs [37] --> Loop 22 * CEs [38] --> Loop 23 ### Ranking functions of CR fun1(Out) #### Partial ranking functions of CR fun1(Out) ### Specialization of cost equations mark/2 * CE 16 is refined into CE [39,40] * CE 17 is refined into CE [41] * CE 18 is refined into CE [42] * CE 15 is refined into CE [43,44] ### Cost equations --> "Loop" of mark/2 * CEs [44] --> Loop 24 * CEs [43] --> Loop 25 * CEs [40] --> Loop 26 * CEs [39] --> Loop 27 * CEs [41,42] --> Loop 28 ### Ranking functions of CR mark(V1,Out) * RF of phase [24,25]: [V1] #### Partial ranking functions of CR mark(V1,Out) * Partial RF of phase [24,25]: - RF of loop [24:1,25:1]: V1 ### Specialization of cost equations encArg/2 * CE 19 is refined into CE [45] * CE 23 is refined into CE [46,47] * CE 20 is refined into CE [48] * CE 24 is refined into CE [49,50] * CE 21 is refined into CE [51] * CE 22 is refined into CE [52,53] ### Cost equations --> "Loop" of encArg/2 * CEs [51,53] --> Loop 29 * CEs [52] --> Loop 30 * CEs [50] --> Loop 31 * CEs [49] --> Loop 32 * CEs [47] --> Loop 33 * CEs [45,46] --> Loop 34 * CEs [48] --> Loop 35 ### Ranking functions of CR encArg(V1,Out) * RF of phase [29,30,31,32]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [29,30,31,32]: - RF of loop [29:1,29:2,30:1,30:2,31:1,32:1]: V1 ### Specialization of cost equations fun2/3 * CE 25 is refined into CE [54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69] * CE 26 is refined into CE [70] ### Cost equations --> "Loop" of fun2/3 * CEs [59] --> Loop 36 * CEs [69] --> Loop 37 * CEs [70] --> Loop 38 * CEs [57] --> Loop 39 * CEs [56,66,67] --> Loop 40 * CEs [55,61,63] --> Loop 41 * CEs [54,58,60,62,64,65,68] --> Loop 42 ### Ranking functions of CR fun2(V1,V,Out) #### Partial ranking functions of CR fun2(V1,V,Out) ### Specialization of cost equations fun4/1 * CE 27 is refined into CE [71] * CE 28 is refined into CE [72] ### Cost equations --> "Loop" of fun4/1 * CEs [71] --> Loop 43 * CEs [72] --> Loop 44 ### Ranking functions of CR fun4(Out) #### Partial ranking functions of CR fun4(Out) ### Specialization of cost equations fun5/1 * CE 29 is refined into CE [73,74] * CE 30 is refined into CE [75] ### Cost equations --> "Loop" of fun5/1 * CEs [74] --> Loop 45 * CEs [73,75] --> Loop 46 ### Ranking functions of CR fun5(Out) #### Partial ranking functions of CR fun5(Out) ### Specialization of cost equations fun6/2 * CE 31 is refined into CE [76,77,78,79,80] * CE 32 is refined into CE [81] ### Cost equations --> "Loop" of fun6/2 * CEs [77,79] --> Loop 47 * CEs [76,78,80,81] --> Loop 48 ### Ranking functions of CR fun6(V1,Out) #### Partial ranking functions of CR fun6(V1,Out) ### Specialization of cost equations fun7/3 * CE 33 is refined into CE [82,83,84,85,86,87,88,89,90] * CE 34 is refined into CE [91] ### Cost equations --> "Loop" of fun7/3 * CEs [90] --> Loop 49 * CEs [91] --> Loop 50 * CEs [83] --> Loop 51 * CEs [88,89] --> Loop 52 * CEs [84,87] --> Loop 53 * CEs [82,85,86] --> Loop 54 ### Ranking functions of CR fun7(V1,V,Out) #### Partial ranking functions of CR fun7(V1,V,Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [92,93] * CE 2 is refined into CE [94,95] * CE 3 is refined into CE [96,97] * CE 4 is refined into CE [98,99,100] * CE 5 is refined into CE [101,102,103,104,105,106] * CE 6 is refined into CE [107] * CE 7 is refined into CE [108,109] * CE 8 is refined into CE [110,111] * CE 9 is refined into CE [112,113] * CE 10 is refined into CE [114,115,116,117,118] ### Cost equations --> "Loop" of start/2 * CEs [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,117,118] --> Loop 55 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of fun(V1,V,Out): * Chain [21]: 1 with precondition: [V+V1+1=Out,V1>=0,V>=0] * Chain [20,21]: 2 with precondition: [Out=2,V1=V,V1>=0] #### Cost of chains of fun1(Out): * Chain [23]: 1 with precondition: [Out=0] * Chain [22]: 1 with precondition: [Out=1] #### Cost of chains of mark(V1,Out): * Chain [[24,25],28]: 5*it(24)+1 Such that:aux(3) =< V1 it(24) =< aux(3) with precondition: [V1>=1,Out>=1,V1+1>=Out] * Chain [[24,25],27]: 5*it(24)+2 Such that:aux(4) =< V1 it(24) =< aux(4) with precondition: [V1>=2,Out>=1,V1>=Out] * Chain [[24,25],26]: 5*it(24)+2 Such that:aux(5) =< V1 it(24) =< aux(5) with precondition: [Out>=2,V1>=Out] * Chain [28]: 1 with precondition: [Out=0,V1>=0] * Chain [27]: 2 with precondition: [V1=1,Out=0] * Chain [26]: 2 with precondition: [V1=1,Out=1] #### Cost of chains of encArg(V1,Out): * Chain [35]: 0 with precondition: [V1=1,Out=1] * Chain [34]: 1 with precondition: [Out=0,V1>=0] * Chain [33]: 1 with precondition: [V1=2,Out=1] * Chain [multiple([29,30,31,32],[[35],[34],[33]])]: 7*it(29)+1*it([33])+1*it([34])+15*s(11)+0 Such that:aux(7) =< 2*V1 it([33]) =< V1/3+1/3 aux(8) =< V1 aux(9) =< V1+1 it(29) =< aux(8) it([33]) =< aux(8) it([34]) =< aux(9) s(12) =< it(29)*aux(7) s(11) =< s(12) with precondition: [V1>=1,Out>=0,2*V1>=Out] #### Cost of chains of fun2(V1,V,Out): * Chain [42]: 2*s(24)+14*s(25)+2*s(26)+30*s(28)+3*s(32)+21*s(33)+3*s(34)+45*s(36)+4 Such that:aux(10) =< V1 aux(11) =< V1+1 aux(12) =< 2*V1 aux(13) =< V1/3+1/3 aux(14) =< V aux(15) =< V+1 aux(16) =< 2*V aux(17) =< V/3+1/3 s(24) =< aux(13) s(32) =< aux(17) s(33) =< aux(14) s(32) =< aux(14) s(34) =< aux(15) s(35) =< s(33)*aux(16) s(36) =< s(35) s(25) =< aux(10) s(24) =< aux(10) s(26) =< aux(11) s(27) =< s(25)*aux(12) s(28) =< s(27) with precondition: [Out=2,V1>=0,V>=0] * Chain [41]: 1*s(64)+7*s(65)+1*s(66)+15*s(68)+2*s(72)+14*s(73)+2*s(74)+30*s(76)+3 Such that:s(61) =< V1 s(62) =< V1+1 s(63) =< 2*V1 s(64) =< V1/3+1/3 aux(18) =< V aux(19) =< V+1 aux(20) =< 2*V aux(21) =< V/3+1/3 s(72) =< aux(21) s(73) =< aux(18) s(72) =< aux(18) s(74) =< aux(19) s(75) =< s(73)*aux(20) s(76) =< s(75) s(65) =< s(61) s(64) =< s(61) s(66) =< s(62) s(67) =< s(65)*s(63) s(68) =< s(67) with precondition: [V1>=1,V>=1,Out>=1,2*V+2*V1+1>=Out] * Chain [40]: 1*s(88)+7*s(89)+1*s(90)+15*s(92)+1*s(96)+7*s(97)+1*s(98)+15*s(100)+3 Such that:s(85) =< V1 s(86) =< V1+1 s(87) =< 2*V1 s(88) =< V1/3+1/3 s(93) =< V s(94) =< V+1 s(95) =< 2*V s(96) =< V/3+1/3 s(89) =< s(85) s(88) =< s(85) s(90) =< s(86) s(91) =< s(89)*s(87) s(92) =< s(91) s(97) =< s(93) s(96) =< s(93) s(98) =< s(94) s(99) =< s(97)*s(95) s(100) =< s(99) with precondition: [V1>=0,V>=1,Out>=1,2*V+1>=Out] * Chain [39]: 1*s(104)+7*s(105)+1*s(106)+15*s(108)+2 Such that:s(101) =< V1 s(102) =< V1+1 s(103) =< 2*V1 s(104) =< V1/3+1/3 s(105) =< s(101) s(104) =< s(101) s(106) =< s(102) s(107) =< s(105)*s(103) s(108) =< s(107) with precondition: [V=2,V1>=1,Out>=2,2*V1+2>=Out] * Chain [38]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [37]: 3 with precondition: [Out=1,V1>=0,V>=0] * Chain [36]: 1*s(112)+7*s(113)+1*s(114)+15*s(116)+2 Such that:s(109) =< V1 s(110) =< V1+1 s(111) =< 2*V1 s(112) =< V1/3+1/3 s(113) =< s(109) s(112) =< s(109) s(114) =< s(110) s(115) =< s(113)*s(111) s(116) =< s(115) with precondition: [V1>=1,V>=0,Out>=1,2*V1+1>=Out] #### Cost of chains of fun4(Out): * Chain [44]: 0 with precondition: [Out=0] * Chain [43]: 0 with precondition: [Out=1] #### Cost of chains of fun5(Out): * Chain [46]: 1 with precondition: [Out=0] * Chain [45]: 1 with precondition: [Out=1] #### Cost of chains of fun6(V1,Out): * Chain [48]: 1*s(145)+7*s(146)+1*s(147)+15*s(149)+3 Such that:s(142) =< V1 s(143) =< V1+1 s(144) =< 2*V1 s(145) =< V1/3+1/3 s(146) =< s(142) s(145) =< s(142) s(147) =< s(143) s(148) =< s(146)*s(144) s(149) =< s(148) with precondition: [Out=0,V1>=0] * Chain [47]: 1*s(153)+7*s(154)+1*s(155)+15*s(157)+15*s(159)+15*s(161)+3 Such that:s(160) =< 1 s(150) =< V1 s(151) =< V1+1 aux(26) =< 2*V1 s(153) =< V1/3+1/3 s(161) =< s(160) s(159) =< aux(26) s(154) =< s(150) s(153) =< s(150) s(155) =< s(151) s(156) =< s(154)*aux(26) s(157) =< s(156) with precondition: [V1>=1,Out>=1,2*V1+1>=Out] #### Cost of chains of fun7(V1,V,Out): * Chain [54]: 1*s(165)+7*s(166)+1*s(167)+15*s(169)+2*s(173)+14*s(174)+2*s(175)+30*s(177)+2 Such that:s(162) =< V1 s(163) =< V1+1 s(164) =< 2*V1 s(165) =< V1/3+1/3 aux(27) =< V aux(28) =< V+1 aux(29) =< 2*V aux(30) =< V/3+1/3 s(173) =< aux(30) s(174) =< aux(27) s(173) =< aux(27) s(175) =< aux(28) s(176) =< s(174)*aux(29) s(177) =< s(176) s(166) =< s(162) s(165) =< s(162) s(167) =< s(163) s(168) =< s(166)*s(164) s(169) =< s(168) with precondition: [V1>=1,V>=1,Out>=1,2*V+2*V1+1>=Out] * Chain [53]: 1*s(189)+7*s(190)+1*s(191)+15*s(193)+2 Such that:s(186) =< V1 s(187) =< V1+1 s(188) =< 2*V1 s(189) =< V1/3+1/3 s(190) =< s(186) s(189) =< s(186) s(191) =< s(187) s(192) =< s(190)*s(188) s(193) =< s(192) with precondition: [V1>=1,V>=0,Out>=1,2*V1+1>=Out] * Chain [52]: 1*s(197)+7*s(198)+1*s(199)+15*s(201)+2 Such that:s(194) =< V s(195) =< V+1 s(196) =< 2*V s(197) =< V/3+1/3 s(198) =< s(194) s(197) =< s(194) s(199) =< s(195) s(200) =< s(198)*s(196) s(201) =< s(200) with precondition: [V1>=0,V>=1,Out>=1,2*V+1>=Out] * Chain [51]: 1*s(205)+7*s(206)+1*s(207)+15*s(209)+1 Such that:s(202) =< V1 s(203) =< V1+1 s(204) =< 2*V1 s(205) =< V1/3+1/3 s(206) =< s(202) s(205) =< s(202) s(207) =< s(203) s(208) =< s(206)*s(204) s(209) =< s(208) with precondition: [V=2,V1>=1,Out>=2,2*V1+2>=Out] * Chain [50]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [49]: 2 with precondition: [Out=1,V1>=0,V>=0] #### Cost of chains of start(V1,V): * Chain [55]: 99*s(236)+12*s(240)+12*s(242)+180*s(244)+9*s(258)+63*s(259)+9*s(260)+135*s(262)+15*s(318)+15*s(319)+4 Such that:s(313) =< 1 aux(35) =< V1 aux(36) =< V1+1 aux(37) =< 2*V1 aux(38) =< V1/3+1/3 aux(39) =< V aux(40) =< V+1 aux(41) =< 2*V aux(42) =< V/3+1/3 s(240) =< aux(38) s(258) =< aux(42) s(318) =< s(313) s(319) =< aux(37) s(236) =< aux(35) s(240) =< aux(35) s(242) =< aux(36) s(243) =< s(236)*aux(37) s(244) =< s(243) s(259) =< aux(39) s(258) =< aux(39) s(260) =< aux(40) s(261) =< s(259)*aux(41) s(262) =< s(261) with precondition: [] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [55] with precondition: [] - Upper bound: nat(V1)*99+19+nat(V1)*180*nat(2*V1)+nat(V)*63+nat(V)*135*nat(2*V)+nat(2*V1)*15+nat(V1+1)*12+nat(V+1)*9+nat(V1/3+1/3)*12+nat(V/3+1/3)*9 - Complexity: n^2 ### Maximum cost of start(V1,V): nat(V1)*99+19+nat(V1)*180*nat(2*V1)+nat(V)*63+nat(V)*135*nat(2*V)+nat(2*V1)*15+nat(V1+1)*12+nat(V+1)*9+nat(V1/3+1/3)*12+nat(V/3+1/3)*9 Asymptotic class: n^2 * Total analysis performed in 543 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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b The (relative) TRS S consists of the following rules: encArg(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b encArg(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) Types: a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark a :: a:b:f:cons_a__f:cons_a__b:cons_mark b :: a:b:f:cons_a__f:cons_a__b:cons_mark a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encArg :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark cons_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark hole_a:b:f:cons_a__f:cons_a__b:cons_mark1_0 :: a:b:f:cons_a__f:cons_a__b:cons_mark gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0 :: Nat -> a:b:f:cons_a__f:cons_a__b:cons_mark ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: a__f, mark, encArg They will be analysed ascendingly in the following order: a__f < mark a__f < encArg mark < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b encArg(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) Types: a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark a :: a:b:f:cons_a__f:cons_a__b:cons_mark b :: a:b:f:cons_a__f:cons_a__b:cons_mark a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encArg :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark cons_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark hole_a:b:f:cons_a__f:cons_a__b:cons_mark1_0 :: a:b:f:cons_a__f:cons_a__b:cons_mark gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0 :: Nat -> a:b:f:cons_a__f:cons_a__b:cons_mark Generator Equations: gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(0) <=> a gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(x, 1)) <=> f(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(x), a) The following defined symbols remain to be analysed: a__f, mark, encArg They will be analysed ascendingly in the following order: a__f < mark a__f < encArg mark < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mark(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(1, n22_0))) -> *3_0, rt in Omega(n22_0) Induction Base: mark(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(1, 0))) Induction Step: mark(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(1, +(n22_0, 1)))) ->_R^Omega(1) a__f(mark(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(1, n22_0))), a) ->_IH a__f(*3_0, a) 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: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b encArg(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) Types: a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark a :: a:b:f:cons_a__f:cons_a__b:cons_mark b :: a:b:f:cons_a__f:cons_a__b:cons_mark a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encArg :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark cons_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark hole_a:b:f:cons_a__f:cons_a__b:cons_mark1_0 :: a:b:f:cons_a__f:cons_a__b:cons_mark gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0 :: Nat -> a:b:f:cons_a__f:cons_a__b:cons_mark Generator Equations: gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(0) <=> a gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(x, 1)) <=> f(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(x), a) The following defined symbols remain to be analysed: mark, encArg They will be analysed ascendingly in the following order: mark < encArg ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: a__f(X, X) -> a__f(a, b) a__b -> a mark(f(X1, X2)) -> a__f(mark(X1), X2) mark(b) -> a__b mark(a) -> a a__f(X1, X2) -> f(X1, X2) a__b -> b encArg(a) -> a encArg(b) -> b encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_a__f(x_1, x_2)) -> a__f(encArg(x_1), encArg(x_2)) encArg(cons_a__b) -> a__b encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1, x_2) -> a__f(encArg(x_1), encArg(x_2)) encode_a -> a encode_b -> b encode_a__b -> a__b encode_mark(x_1) -> mark(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) Types: a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark a :: a:b:f:cons_a__f:cons_a__b:cons_mark b :: a:b:f:cons_a__f:cons_a__b:cons_mark a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encArg :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark cons_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark cons_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_a :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_a__b :: a:b:f:cons_a__f:cons_a__b:cons_mark encode_mark :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark encode_f :: a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark -> a:b:f:cons_a__f:cons_a__b:cons_mark hole_a:b:f:cons_a__f:cons_a__b:cons_mark1_0 :: a:b:f:cons_a__f:cons_a__b:cons_mark gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0 :: Nat -> a:b:f:cons_a__f:cons_a__b:cons_mark Lemmas: mark(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(1, n22_0))) -> *3_0, rt in Omega(n22_0) Generator Equations: gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(0) <=> a gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(x, 1)) <=> f(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(x), a) The following defined symbols remain to be analysed: encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(n26491_0)) -> gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(n26491_0), rt in Omega(0) Induction Base: encArg(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(0)) ->_R^Omega(0) a Induction Step: encArg(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(+(n26491_0, 1))) ->_R^Omega(0) f(encArg(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(n26491_0)), encArg(a)) ->_IH f(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(c26492_0), encArg(a)) ->_R^Omega(0) f(gen_a:b:f:cons_a__f:cons_a__b:cons_mark2_0(n26491_0), a) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (28) BOUNDS(1, INF)