/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), 186 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, 1394 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), 261 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), 74 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:

   minus(x, 0) -> x
   minus(s(x), s(y)) -> minus(x, y)
   quot(0, s(y)) -> 0
   quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(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)) -> minus(x, y)
   quot(0, s(y)) -> 0
   quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(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)) -> minus(x, y)
   quot(0, s(y)) -> 0
   quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(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)) -> minus(x, y) [1]
   quot(0, s(y)) -> 0 [1]
   quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(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)) -> minus(x, y) [1]
   quot(0, s(y)) -> 0 [1]
   quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
minus :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
0 :: 0:s:cons_minus:cons_quot
s :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
quot :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
encArg :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
cons_minus :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
cons_quot :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
encode_minus :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
encode_0 :: 0:s:cons_minus:cons_quot
encode_s :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot
encode_quot :: 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot -> 0:s:cons_minus:cons_quot

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_quot(v0, v1) -> null_encode_quot [0]
   minus(v0, v1) -> null_minus [0]
   quot(v0, v1) -> null_quot [0]

And the following fresh constants:    null_encArg, null_encode_minus, null_encode_0, null_encode_s, null_encode_quot, null_minus, null_quot

----------------------------------------

(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)) -> minus(x, y) [1]
   quot(0, s(y)) -> 0 [1]
   quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(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_quot(v0, v1) -> null_encode_quot [0]
   minus(v0, v1) -> null_minus [0]
   quot(v0, v1) -> null_quot [0]

The TRS has the following type information:
minus :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
0 :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
s :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
quot :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
encArg :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
cons_minus :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
cons_quot :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
encode_minus :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
encode_0 :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
encode_s :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
encode_quot :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot -> 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
null_encArg :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
null_encode_minus :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
null_encode_0 :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
null_encode_s :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
null_encode_quot :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
null_minus :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot
null_quot :: 0:s:cons_minus:cons_quot:null_encArg:null_encode_minus:null_encode_0:null_encode_s:null_encode_quot:null_minus:null_quot

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_quot => 0
   null_minus => 0
   null_quot => 0

----------------------------------------

(12)
Obligation:
Complexity RNTS consisting of the following rules:

   encArg(z) -{ 0 }-> quot(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 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 }-> 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_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_quot(z, z') -{ 0 }-> quot(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_quot(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1
   minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   quot(z, z') -{ 1 }-> 0 :|: z' = 1 + y, y >= 0, z = 0
   quot(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   quot(z, z') -{ 1 }-> 1 + quot(minus(x, y), 1 + y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x

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,[quot(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, V, Out)],[V1 >= 0,V >= 0]).
eq(minus(V1, V, Out),1,[],[Out = V2,V2 >= 0,V1 = V2,V = 0]).
eq(minus(V1, V, Out),1,[minus(V3, V4, Ret)],[Out = Ret,V = 1 + V4,V3 >= 0,V4 >= 0,V1 = 1 + V3]).
eq(quot(V1, V, Out),1,[],[Out = 0,V = 1 + V5,V5 >= 0,V1 = 0]).
eq(quot(V1, V, Out),1,[minus(V7, V6, Ret10),quot(Ret10, 1 + V6, Ret1)],[Out = 1 + Ret1,V = 1 + V6,V7 >= 0,V6 >= 0,V1 = 1 + V7]).
eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]).
eq(encArg(V1, Out),0,[encArg(V8, Ret11)],[Out = 1 + Ret11,V1 = 1 + V8,V8 >= 0]).
eq(encArg(V1, Out),0,[encArg(V9, Ret0),encArg(V10, Ret12),minus(Ret0, Ret12, Ret2)],[Out = Ret2,V9 >= 0,V1 = 1 + V10 + V9,V10 >= 0]).
eq(encArg(V1, Out),0,[encArg(V11, Ret01),encArg(V12, Ret13),quot(Ret01, Ret13, Ret3)],[Out = Ret3,V11 >= 0,V1 = 1 + V11 + V12,V12 >= 0]).
eq(fun(V1, V, Out),0,[encArg(V14, Ret02),encArg(V13, Ret14),minus(Ret02, Ret14, Ret4)],[Out = Ret4,V14 >= 0,V13 >= 0,V1 = V14,V = V13]).
eq(fun1(Out),0,[],[Out = 0]).
eq(fun2(V1, Out),0,[encArg(V15, Ret15)],[Out = 1 + Ret15,V15 >= 0,V1 = V15]).
eq(fun3(V1, V, Out),0,[encArg(V17, Ret03),encArg(V16, Ret16),quot(Ret03, Ret16, Ret5)],[Out = Ret5,V17 >= 0,V16 >= 0,V1 = V17,V = V16]).
eq(encArg(V1, Out),0,[],[Out = 0,V18 >= 0,V1 = V18]).
eq(fun(V1, V, Out),0,[],[Out = 0,V20 >= 0,V19 >= 0,V1 = V20,V = V19]).
eq(fun2(V1, Out),0,[],[Out = 0,V21 >= 0,V1 = V21]).
eq(fun3(V1, V, Out),0,[],[Out = 0,V22 >= 0,V23 >= 0,V1 = V22,V = V23]).
eq(minus(V1, V, Out),0,[],[Out = 0,V24 >= 0,V25 >= 0,V1 = V24,V = V25]).
eq(quot(V1, V, Out),0,[],[Out = 0,V26 >= 0,V27 >= 0,V1 = V26,V = V27]).
input_output_vars(minus(V1,V,Out),[V1,V],[Out]).
input_output_vars(quot(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,V,Out),[V1,V],[Out]).


CoFloCo proof output:
Preprocessing Cost Relations
=====================================

#### Computed strongly connected components 
0. recursive  : [minus/3]
1. recursive  : [quot/3]
2. recursive [non_tail,multiple] : [encArg/2]
3. non_recursive  : [fun/3]
4. non_recursive  : [fun1/1]
5. non_recursive  : [fun2/2]
6. non_recursive  : [fun3/3]
7. non_recursive  : [start/2]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into minus/3
1. SCC is partially evaluated into quot/3
2. SCC is partially evaluated into encArg/2
3. SCC is partially evaluated into fun/3
4. SCC is completely evaluated into other SCCs
5. SCC is partially evaluated into fun2/2
6. SCC is partially evaluated into fun3/3
7. SCC is partially evaluated into start/2

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations minus/3 
* CE 10 is refined into CE [24] 
* CE 8 is refined into CE [25] 
* CE 9 is refined into CE [26] 


### Cost equations --> "Loop" of minus/3 
* CEs [26] --> Loop 13 
* CEs [24] --> Loop 14 
* CEs [25] --> Loop 15 

### Ranking functions of CR minus(V1,V,Out) 
* RF of phase [13]: [V,V1]

#### Partial ranking functions of CR minus(V1,V,Out) 
* Partial RF of phase [13]:
  - RF of loop [13:1]:
    V
    V1


### Specialization of cost equations quot/3 
* CE 11 is refined into CE [27] 
* CE 13 is refined into CE [28] 
* CE 12 is refined into CE [29,30,31] 


### Cost equations --> "Loop" of quot/3 
* CEs [31] --> Loop 16 
* CEs [30] --> Loop 17 
* CEs [29] --> Loop 18 
* CEs [27,28] --> Loop 19 

### Ranking functions of CR quot(V1,V,Out) 
* RF of phase [16]: [V1-1,V1-V+1]
* RF of phase [18]: [V1]

#### Partial ranking functions of CR quot(V1,V,Out) 
* Partial RF of phase [16]:
  - RF of loop [16:1]:
    V1-1
    V1-V+1
* Partial RF of phase [18]:
  - RF of loop [18:1]:
    V1


### Specialization of cost equations encArg/2 
* CE 14 is refined into CE [32] 
* CE 16 is refined into CE [33,34,35] 
* CE 17 is refined into CE [36,37,38,39,40] 
* CE 15 is refined into CE [41] 


### Cost equations --> "Loop" of encArg/2 
* CEs [41] --> Loop 20 
* CEs [40] --> Loop 21 
* CEs [39] --> Loop 22 
* CEs [35] --> Loop 23 
* CEs [36] --> Loop 24 
* CEs [33] --> Loop 25 
* CEs [38] --> Loop 26 
* CEs [34,37] --> Loop 27 
* CEs [32] --> Loop 28 

### Ranking functions of CR encArg(V1,Out) 
* RF of phase [20,21,22,23,24,25,26,27]: [V1]

#### Partial ranking functions of CR encArg(V1,Out) 
* Partial RF of phase [20,21,22,23,24,25,26,27]:
  - RF of loop [20:1,21:1,21:2,22:1,22:2,23:1,23:2,24:1,24:2,25:1,25:2,26:1,26:2,27:1,27:2]:
    V1


### Specialization of cost equations fun/3 
* CE 18 is refined into CE [42,43,44,45,46,47,48,49,50] 
* CE 19 is refined into CE [51] 


### Cost equations --> "Loop" of fun/3 
* CEs [46,48,50] --> Loop 29 
* CEs [42,43,44,45,47,49,51] --> Loop 30 

### Ranking functions of CR fun(V1,V,Out) 

#### Partial ranking functions of CR fun(V1,V,Out) 


### Specialization of cost equations fun2/2 
* CE 20 is refined into CE [52,53] 
* CE 21 is refined into CE [54] 


### Cost equations --> "Loop" of fun2/2 
* CEs [53] --> Loop 31 
* CEs [52] --> Loop 32 
* CEs [54] --> Loop 33 

### Ranking functions of CR fun2(V1,Out) 

#### Partial ranking functions of CR fun2(V1,Out) 


### Specialization of cost equations fun3/3 
* CE 22 is refined into CE [55,56,57,58,59,60,61,62] 
* CE 23 is refined into CE [63] 


### Cost equations --> "Loop" of fun3/3 
* CEs [58,60,61,62] --> Loop 34 
* CEs [55,56,57,59,63] --> Loop 35 

### Ranking functions of CR fun3(V1,V,Out) 

#### Partial ranking functions of CR fun3(V1,V,Out) 


### Specialization of cost equations start/2 
* CE 1 is refined into CE [64,65,66] 
* CE 2 is refined into CE [67,68,69,70,71] 
* CE 3 is refined into CE [72,73] 
* CE 4 is refined into CE [74,75] 
* CE 5 is refined into CE [76] 
* CE 6 is refined into CE [77,78,79] 
* CE 7 is refined into CE [80,81] 


### Cost equations --> "Loop" of start/2 
* CEs [64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81] --> Loop 36 

### Ranking functions of CR start(V1,V) 

#### Partial ranking functions of CR start(V1,V) 


Computing Bounds
=====================================

#### Cost of chains of minus(V1,V,Out):
* Chain [[13],15]: 1*it(13)+1
  Such that:it(13) =< V

  with precondition: [V1=Out+V,V>=1,V1>=V] 

* Chain [[13],14]: 1*it(13)+0
  Such that:it(13) =< V

  with precondition: [Out=0,V1>=1,V>=1] 

* Chain [15]: 1
  with precondition: [V=0,V1=Out,V1>=0] 

* Chain [14]: 0
  with precondition: [Out=0,V1>=0,V>=0] 


#### Cost of chains of quot(V1,V,Out):
* Chain [[18],19]: 2*it(18)+1
  Such that:it(18) =< Out

  with precondition: [V=1,Out>=1,V1>=Out] 

* Chain [[18],17,19]: 2*it(18)+1*s(2)+2
  Such that:s(2) =< 1
it(18) =< Out

  with precondition: [V=1,Out>=2,V1>=Out] 

* Chain [[16],19]: 2*it(16)+1*s(5)+1
  Such that:it(16) =< V1-V+1
aux(3) =< V1
it(16) =< aux(3)
s(5) =< aux(3)

  with precondition: [V>=2,Out>=1,V1+2>=2*Out+V] 

* Chain [[16],17,19]: 2*it(16)+1*s(2)+1*s(5)+2
  Such that:it(16) =< V1-V+1
s(2) =< V
aux(4) =< V1
it(16) =< aux(4)
s(5) =< aux(4)

  with precondition: [V>=2,Out>=2,V1+3>=2*Out+V] 

* Chain [19]: 1
  with precondition: [Out=0,V1>=0,V>=0] 

* Chain [17,19]: 1*s(2)+2
  Such that:s(2) =< V

  with precondition: [Out=1,V1>=1,V>=1] 


#### Cost of chains of encArg(V1,Out):
* Chain [28]: 0
  with precondition: [Out=0,V1>=0] 

* Chain [multiple([20,21,22,23,24,25,26,27],[[28]])]: 2*it(21)+1*it(22)+5*it(23)+2*it(25)+4*s(32)+3*s(34)+2*s(36)+1*s(37)+4*s(38)+1*s(41)+0
  Such that:aux(23) =< V1
aux(24) =< V1/2
aux(25) =< V1/3
aux(26) =< 2/7*V1
it(21) =< aux(23)
it(22) =< aux(23)
it(23) =< aux(23)
it(25) =< aux(23)
it(23) =< aux(24)
it(22) =< aux(25)
it(21) =< aux(26)
aux(16) =< aux(23)+1
aux(11) =< aux(23)
s(41) =< it(25)*aux(16)
s(36) =< it(23)*aux(11)
s(39) =< it(23)*aux(16)
s(37) =< aux(24)
s(35) =< it(22)*aux(11)
s(33) =< it(21)*aux(23)
s(38) =< s(39)
s(34) =< s(35)
s(32) =< s(33)

  with precondition: [V1>=1,Out>=0,V1>=Out] 


#### Cost of chains of fun(V1,V,Out):
* Chain [30]: 6*s(47)+3*s(48)+15*s(49)+8*s(50)+3*s(53)+6*s(54)+3*s(56)+12*s(59)+9*s(60)+12*s(61)+4*s(86)+2*s(87)+10*s(88)+4*s(89)+2*s(92)+4*s(93)+2*s(95)+8*s(98)+6*s(99)+8*s(100)+1
  Such that:aux(29) =< V1
aux(30) =< V1/2
aux(31) =< V1/3
aux(32) =< 2/7*V1
aux(33) =< V
aux(34) =< V/2
aux(35) =< V/3
aux(36) =< 2/7*V
s(86) =< aux(29)
s(87) =< aux(29)
s(88) =< aux(29)
s(89) =< aux(29)
s(88) =< aux(30)
s(87) =< aux(31)
s(86) =< aux(32)
s(90) =< aux(29)+1
s(91) =< aux(29)
s(92) =< s(89)*s(90)
s(93) =< s(88)*s(91)
s(94) =< s(88)*s(90)
s(95) =< aux(30)
s(96) =< s(87)*s(91)
s(97) =< s(86)*aux(29)
s(98) =< s(94)
s(99) =< s(96)
s(100) =< s(97)
s(50) =< aux(33)
s(47) =< aux(33)
s(48) =< aux(33)
s(49) =< aux(33)
s(49) =< aux(34)
s(48) =< aux(35)
s(47) =< aux(36)
s(51) =< aux(33)+1
s(52) =< aux(33)
s(53) =< s(50)*s(51)
s(54) =< s(49)*s(52)
s(55) =< s(49)*s(51)
s(56) =< aux(34)
s(57) =< s(48)*s(52)
s(58) =< s(47)*aux(33)
s(59) =< s(55)
s(60) =< s(57)
s(61) =< s(58)

  with precondition: [Out=0,V1>=0,V>=0] 

* Chain [29]: 6*s(145)+3*s(146)+15*s(147)+6*s(148)+3*s(151)+6*s(152)+3*s(154)+12*s(157)+9*s(158)+12*s(159)+4*s(183)+2*s(184)+10*s(185)+5*s(186)+2*s(189)+4*s(190)+2*s(192)+8*s(195)+6*s(196)+8*s(197)+1
  Such that:aux(38) =< V1
aux(39) =< V1/2
aux(40) =< V1/3
aux(41) =< 2/7*V1
aux(42) =< V
aux(43) =< V/2
aux(44) =< V/3
aux(45) =< 2/7*V
s(145) =< aux(38)
s(146) =< aux(38)
s(147) =< aux(38)
s(148) =< aux(38)
s(147) =< aux(39)
s(146) =< aux(40)
s(145) =< aux(41)
s(149) =< aux(38)+1
s(150) =< aux(38)
s(151) =< s(148)*s(149)
s(152) =< s(147)*s(150)
s(153) =< s(147)*s(149)
s(154) =< aux(39)
s(155) =< s(146)*s(150)
s(156) =< s(145)*aux(38)
s(157) =< s(153)
s(158) =< s(155)
s(159) =< s(156)
s(183) =< aux(42)
s(184) =< aux(42)
s(185) =< aux(42)
s(186) =< aux(42)
s(185) =< aux(43)
s(184) =< aux(44)
s(183) =< aux(45)
s(187) =< aux(42)+1
s(188) =< aux(42)
s(189) =< s(186)*s(187)
s(190) =< s(185)*s(188)
s(191) =< s(185)*s(187)
s(192) =< aux(43)
s(193) =< s(184)*s(188)
s(194) =< s(183)*aux(42)
s(195) =< s(191)
s(196) =< s(193)
s(197) =< s(194)

  with precondition: [V1>=1,V>=0,Out>=0,V1>=Out] 


#### Cost of chains of fun2(V1,Out):
* Chain [33]: 0
  with precondition: [Out=0,V1>=0] 

* Chain [32]: 0
  with precondition: [Out=1,V1>=0] 

* Chain [31]: 2*s(241)+1*s(242)+5*s(243)+2*s(244)+1*s(247)+2*s(248)+1*s(250)+4*s(253)+3*s(254)+4*s(255)+0
  Such that:s(237) =< V1
s(238) =< V1/2
s(239) =< V1/3
s(240) =< 2/7*V1
s(241) =< s(237)
s(242) =< s(237)
s(243) =< s(237)
s(244) =< s(237)
s(243) =< s(238)
s(242) =< s(239)
s(241) =< s(240)
s(245) =< s(237)+1
s(246) =< s(237)
s(247) =< s(244)*s(245)
s(248) =< s(243)*s(246)
s(249) =< s(243)*s(245)
s(250) =< s(238)
s(251) =< s(242)*s(246)
s(252) =< s(241)*s(237)
s(253) =< s(249)
s(254) =< s(251)
s(255) =< s(252)

  with precondition: [V1>=1,Out>=1,V1+1>=Out] 


#### Cost of chains of fun3(V1,V,Out):
* Chain [35]: 4*s(260)+2*s(261)+10*s(262)+4*s(263)+2*s(266)+4*s(267)+2*s(269)+8*s(272)+6*s(273)+8*s(274)+4*s(279)+2*s(280)+10*s(281)+4*s(282)+2*s(285)+4*s(286)+2*s(288)+8*s(291)+6*s(292)+8*s(293)+1
  Such that:aux(46) =< V1
aux(47) =< V1/2
aux(48) =< V1/3
aux(49) =< 2/7*V1
aux(50) =< V
aux(51) =< V/2
aux(52) =< V/3
aux(53) =< 2/7*V
s(279) =< aux(46)
s(280) =< aux(46)
s(281) =< aux(46)
s(282) =< aux(46)
s(281) =< aux(47)
s(280) =< aux(48)
s(279) =< aux(49)
s(283) =< aux(46)+1
s(284) =< aux(46)
s(285) =< s(282)*s(283)
s(286) =< s(281)*s(284)
s(287) =< s(281)*s(283)
s(288) =< aux(47)
s(289) =< s(280)*s(284)
s(290) =< s(279)*aux(46)
s(291) =< s(287)
s(292) =< s(289)
s(293) =< s(290)
s(260) =< aux(50)
s(261) =< aux(50)
s(262) =< aux(50)
s(263) =< aux(50)
s(262) =< aux(51)
s(261) =< aux(52)
s(260) =< aux(53)
s(264) =< aux(50)+1
s(265) =< aux(50)
s(266) =< s(263)*s(264)
s(267) =< s(262)*s(265)
s(268) =< s(262)*s(264)
s(269) =< aux(51)
s(270) =< s(261)*s(265)
s(271) =< s(260)*aux(50)
s(272) =< s(268)
s(273) =< s(270)
s(274) =< s(271)

  with precondition: [Out=0,V1>=0,V>=0] 

* Chain [34]: 8*s(336)+4*s(337)+20*s(338)+16*s(339)+4*s(342)+8*s(343)+4*s(345)+16*s(348)+12*s(349)+16*s(350)+8*s(355)+4*s(356)+20*s(357)+9*s(358)+4*s(361)+8*s(362)+4*s(364)+16*s(367)+12*s(368)+16*s(369)+1*s(370)+2*s(491)+1*s(492)+2
  Such that:s(370) =< 1
aux(58) =< V1+1
aux(59) =< V1
aux(60) =< V1/2
aux(61) =< V1/3
aux(62) =< 2/7*V1
aux(63) =< V
aux(64) =< V/2
aux(65) =< V/3
aux(66) =< 2/7*V
s(339) =< aux(59)
s(355) =< aux(63)
s(356) =< aux(63)
s(357) =< aux(63)
s(358) =< aux(63)
s(357) =< aux(64)
s(356) =< aux(65)
s(355) =< aux(66)
s(359) =< aux(63)+1
s(360) =< aux(63)
s(361) =< s(358)*s(359)
s(362) =< s(357)*s(360)
s(363) =< s(357)*s(359)
s(364) =< aux(64)
s(365) =< s(356)*s(360)
s(366) =< s(355)*aux(63)
s(367) =< s(363)
s(368) =< s(365)
s(369) =< s(366)
s(336) =< aux(59)
s(337) =< aux(59)
s(338) =< aux(59)
s(338) =< aux(60)
s(337) =< aux(61)
s(336) =< aux(62)
s(340) =< aux(59)+1
s(341) =< aux(59)
s(342) =< s(339)*s(340)
s(343) =< s(338)*s(341)
s(344) =< s(338)*s(340)
s(345) =< aux(60)
s(346) =< s(337)*s(341)
s(347) =< s(336)*aux(59)
s(348) =< s(344)
s(349) =< s(346)
s(350) =< s(347)
s(491) =< aux(58)
s(492) =< aux(58)
s(491) =< aux(59)

  with precondition: [V>=1,Out>=1,V1>=Out] 


#### Cost of chains of start(V1,V):
* Chain [36]: 30*s(495)+2*s(497)+40*s(499)+4*s(501)+26*s(512)+13*s(513)+65*s(514)+13*s(518)+26*s(519)+13*s(521)+52*s(524)+39*s(525)+52*s(526)+22*s(551)+11*s(552)+55*s(553)+11*s(556)+22*s(557)+11*s(559)+44*s(562)+33*s(563)+44*s(564)+2*s(700)+1*s(701)+2
  Such that:s(661) =< V1+1
aux(67) =< 1
aux(68) =< V1
aux(69) =< V1-V+1
aux(70) =< V1/2
aux(71) =< V1/3
aux(72) =< 2/7*V1
aux(73) =< V
aux(74) =< V/2
aux(75) =< V/3
aux(76) =< 2/7*V
s(497) =< aux(67)
s(501) =< aux(69)
s(495) =< aux(73)
s(499) =< aux(68)
s(551) =< aux(73)
s(552) =< aux(73)
s(553) =< aux(73)
s(553) =< aux(74)
s(552) =< aux(75)
s(551) =< aux(76)
s(554) =< aux(73)+1
s(555) =< aux(73)
s(556) =< s(495)*s(554)
s(557) =< s(553)*s(555)
s(558) =< s(553)*s(554)
s(559) =< aux(74)
s(560) =< s(552)*s(555)
s(561) =< s(551)*aux(73)
s(562) =< s(558)
s(563) =< s(560)
s(564) =< s(561)
s(512) =< aux(68)
s(513) =< aux(68)
s(514) =< aux(68)
s(514) =< aux(70)
s(513) =< aux(71)
s(512) =< aux(72)
s(516) =< aux(68)+1
s(517) =< aux(68)
s(518) =< s(499)*s(516)
s(519) =< s(514)*s(517)
s(520) =< s(514)*s(516)
s(521) =< aux(70)
s(522) =< s(513)*s(517)
s(523) =< s(512)*aux(68)
s(524) =< s(520)
s(525) =< s(522)
s(526) =< s(523)
s(700) =< s(661)
s(701) =< s(661)
s(700) =< aux(68)
s(501) =< aux(68)

  with precondition: [] 


Closed-form bounds of start(V1,V): 
-------------------------------------
* Chain [36] with precondition: [] 
    - Upper bound: nat(V1)*209+4+nat(V1)*182*nat(V1)+nat(V)*173+nat(V)*154*nat(V)+nat(V1+1)*3+nat(V1-V+1)*4+nat(V1/2)*13+nat(V/2)*11 
    - Complexity: n^2 

### Maximum cost of start(V1,V): nat(V1)*209+4+nat(V1)*182*nat(V1)+nat(V)*173+nat(V)*154*nat(V)+nat(V1+1)*3+nat(V1-V+1)*4+nat(V1/2)*13+nat(V/2)*11 
Asymptotic class: n^2 
* Total analysis performed in 1164 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)) -> minus(x, y)
   quot(0', s(y)) -> 0'
   quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(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)) -> minus(x, y)
quot(0', s(y)) -> 0'
quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2))

Types:
minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
0' :: 0':s:cons_minus:cons_quot
s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encArg :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_0 :: 0':s:cons_minus:cons_quot
encode_s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
hole_0':s:cons_minus:cons_quot1_3 :: 0':s:cons_minus:cons_quot
gen_0':s:cons_minus:cons_quot2_3 :: Nat -> 0':s:cons_minus:cons_quot

----------------------------------------

(19) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
minus, quot, encArg

They will be analysed ascendingly in the following order:
minus < quot
minus < encArg
quot < encArg

----------------------------------------

(20)
Obligation:
Innermost TRS:
Rules:
minus(x, 0') -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0', s(y)) -> 0'
quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2))

Types:
minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
0' :: 0':s:cons_minus:cons_quot
s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encArg :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_0 :: 0':s:cons_minus:cons_quot
encode_s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
hole_0':s:cons_minus:cons_quot1_3 :: 0':s:cons_minus:cons_quot
gen_0':s:cons_minus:cons_quot2_3 :: Nat -> 0':s:cons_minus:cons_quot


Generator Equations:
gen_0':s:cons_minus:cons_quot2_3(0) <=> 0'
gen_0':s:cons_minus:cons_quot2_3(+(x, 1)) <=> s(gen_0':s:cons_minus:cons_quot2_3(x))


The following defined symbols remain to be analysed:
minus, quot, encArg

They will be analysed ascendingly in the following order:
minus < quot
minus < encArg
quot < encArg

----------------------------------------

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
minus(gen_0':s:cons_minus:cons_quot2_3(n4_3), gen_0':s:cons_minus:cons_quot2_3(n4_3)) -> gen_0':s:cons_minus:cons_quot2_3(0), rt in Omega(1 + n4_3)

Induction Base:
minus(gen_0':s:cons_minus:cons_quot2_3(0), gen_0':s:cons_minus:cons_quot2_3(0)) ->_R^Omega(1)
gen_0':s:cons_minus:cons_quot2_3(0)

Induction Step:
minus(gen_0':s:cons_minus:cons_quot2_3(+(n4_3, 1)), gen_0':s:cons_minus:cons_quot2_3(+(n4_3, 1))) ->_R^Omega(1)
minus(gen_0':s:cons_minus:cons_quot2_3(n4_3), gen_0':s:cons_minus:cons_quot2_3(n4_3)) ->_IH
gen_0':s:cons_minus:cons_quot2_3(0)

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)) -> minus(x, y)
quot(0', s(y)) -> 0'
quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2))

Types:
minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
0' :: 0':s:cons_minus:cons_quot
s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encArg :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_0 :: 0':s:cons_minus:cons_quot
encode_s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
hole_0':s:cons_minus:cons_quot1_3 :: 0':s:cons_minus:cons_quot
gen_0':s:cons_minus:cons_quot2_3 :: Nat -> 0':s:cons_minus:cons_quot


Generator Equations:
gen_0':s:cons_minus:cons_quot2_3(0) <=> 0'
gen_0':s:cons_minus:cons_quot2_3(+(x, 1)) <=> s(gen_0':s:cons_minus:cons_quot2_3(x))


The following defined symbols remain to be analysed:
minus, quot, encArg

They will be analysed ascendingly in the following order:
minus < quot
minus < encArg
quot < 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)) -> minus(x, y)
quot(0', s(y)) -> 0'
quot(s(x), s(y)) -> s(quot(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_quot(x_1, x_2)) -> quot(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_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2))

Types:
minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
0' :: 0':s:cons_minus:cons_quot
s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encArg :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
cons_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_minus :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_0 :: 0':s:cons_minus:cons_quot
encode_s :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
encode_quot :: 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot -> 0':s:cons_minus:cons_quot
hole_0':s:cons_minus:cons_quot1_3 :: 0':s:cons_minus:cons_quot
gen_0':s:cons_minus:cons_quot2_3 :: Nat -> 0':s:cons_minus:cons_quot


Lemmas:
minus(gen_0':s:cons_minus:cons_quot2_3(n4_3), gen_0':s:cons_minus:cons_quot2_3(n4_3)) -> gen_0':s:cons_minus:cons_quot2_3(0), rt in Omega(1 + n4_3)


Generator Equations:
gen_0':s:cons_minus:cons_quot2_3(0) <=> 0'
gen_0':s:cons_minus:cons_quot2_3(+(x, 1)) <=> s(gen_0':s:cons_minus:cons_quot2_3(x))


The following defined symbols remain to be analysed:
quot, encArg

They will be analysed ascendingly in the following order:
quot < encArg

----------------------------------------

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_0':s:cons_minus:cons_quot2_3(n432_3)) -> gen_0':s:cons_minus:cons_quot2_3(n432_3), rt in Omega(0)

Induction Base:
encArg(gen_0':s:cons_minus:cons_quot2_3(0)) ->_R^Omega(0)
0'

Induction Step:
encArg(gen_0':s:cons_minus:cons_quot2_3(+(n432_3, 1))) ->_R^Omega(0)
s(encArg(gen_0':s:cons_minus:cons_quot2_3(n432_3))) ->_IH
s(gen_0':s:cons_minus:cons_quot2_3(c433_3))

We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
----------------------------------------

(28)
BOUNDS(1, INF)