/export/starexec/sandbox2/solver/bin/starexec_run_complexity /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 Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).

(0) CpxTRS
(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxWeightedTrs
    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxTypedWeightedTrs
    (5) CompletionProof [UPPER BOUND(ID), 1 ms]
    (6) CpxTypedWeightedCompleteTrs
    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (8) CpxRNTS
    (9) CompleteCoflocoProof [FINISHED, 3379 ms]
    (10) BOUNDS(1, n^2)
(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(12) CpxTRS
    (13) SlicingProof [LOWER BOUND(ID), 0 ms]
    (14) CpxTRS
    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) typed CpxTrs
    (17) OrderProof [LOWER BOUND(ID), 0 ms]
    (18) typed CpxTrs
    (19) RewriteLemmaProof [LOWER BOUND(ID), 282 ms]
    (20) BEST
        (21) proven lower bound
            (22) LowerBoundPropagationProof [FINISHED, 0 ms]
            (23) BOUNDS(n^1, INF)
        (24) typed CpxTrs
            (25) RewriteLemmaProof [LOWER BOUND(ID), 64 ms]
            (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 50 ms]
            (28) typed CpxTrs


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

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   gcd(x, y) -> gcd2(x, y, 0)
   gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i))
   if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i))
   if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
   if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i))
   if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
   if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
   if3(true, b3, x, y, i) -> if4(b3, x, y, i)
   if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
   if4(true, x, y, i) -> pair(result(x), neededIterations(i))
   inc(0) -> 0
   inc(s(i)) -> s(inc(i))
   le(s(x), 0) -> false
   le(0, y) -> true
   le(s(x), s(y)) -> le(x, y)
   minus(x, 0) -> x
   minus(0, y) -> 0
   minus(s(x), s(y)) -> minus(x, y)
   a -> b
   a -> c

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

(2)
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:

   gcd(x, y) -> gcd2(x, y, 0) [1]
   gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) [1]
   if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) [1]
   if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) [1]
   if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) [1]
   if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) [1]
   if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) [1]
   if3(true, b3, x, y, i) -> if4(b3, x, y, i) [1]
   if4(false, x, y, i) -> gcd2(x, minus(y, x), i) [1]
   if4(true, x, y, i) -> pair(result(x), neededIterations(i)) [1]
   inc(0) -> 0 [1]
   inc(s(i)) -> s(inc(i)) [1]
   le(s(x), 0) -> false [1]
   le(0, y) -> true [1]
   le(s(x), s(y)) -> le(x, y) [1]
   minus(x, 0) -> x [1]
   minus(0, y) -> 0 [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   a -> b [1]
   a -> c [1]

Rewrite Strategy: INNERMOST
----------------------------------------

(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(4)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   gcd(x, y) -> gcd2(x, y, 0) [1]
   gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) [1]
   if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) [1]
   if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) [1]
   if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) [1]
   if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) [1]
   if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) [1]
   if3(true, b3, x, y, i) -> if4(b3, x, y, i) [1]
   if4(false, x, y, i) -> gcd2(x, minus(y, x), i) [1]
   if4(true, x, y, i) -> pair(result(x), neededIterations(i)) [1]
   inc(0) -> 0 [1]
   inc(s(i)) -> s(inc(i)) [1]
   le(s(x), 0) -> false [1]
   le(0, y) -> true [1]
   le(s(x), s(y)) -> le(x, y) [1]
   minus(x, 0) -> x [1]
   minus(0, y) -> 0 [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   a -> b [1]
   a -> c [1]

The TRS has the following type information:
gcd :: 0:s -> 0:s -> pair
gcd2 :: 0:s -> 0:s -> 0:s -> pair
0 :: 0:s
if1 :: true:false -> true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair
le :: 0:s -> 0:s -> true:false
inc :: 0:s -> 0:s
true :: true:false
pair :: result -> neededIterations -> pair
result :: 0:s -> result
neededIterations :: 0:s -> neededIterations
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair
if3 :: true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair
minus :: 0:s -> 0:s -> 0:s
if4 :: true:false -> 0:s -> 0:s -> 0:s -> pair
s :: 0:s -> 0:s
a :: b:c
b :: b:c
c :: b:c

Rewrite Strategy: INNERMOST
----------------------------------------

(5) 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:
none

And the following fresh constants:    const, const1, const2

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

(6)
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:

   gcd(x, y) -> gcd2(x, y, 0) [1]
   gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) [1]
   if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) [1]
   if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) [1]
   if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) [1]
   if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) [1]
   if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) [1]
   if3(true, b3, x, y, i) -> if4(b3, x, y, i) [1]
   if4(false, x, y, i) -> gcd2(x, minus(y, x), i) [1]
   if4(true, x, y, i) -> pair(result(x), neededIterations(i)) [1]
   inc(0) -> 0 [1]
   inc(s(i)) -> s(inc(i)) [1]
   le(s(x), 0) -> false [1]
   le(0, y) -> true [1]
   le(s(x), s(y)) -> le(x, y) [1]
   minus(x, 0) -> x [1]
   minus(0, y) -> 0 [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   a -> b [1]
   a -> c [1]

The TRS has the following type information:
gcd :: 0:s -> 0:s -> pair
gcd2 :: 0:s -> 0:s -> 0:s -> pair
0 :: 0:s
if1 :: true:false -> true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair
le :: 0:s -> 0:s -> true:false
inc :: 0:s -> 0:s
true :: true:false
pair :: result -> neededIterations -> pair
result :: 0:s -> result
neededIterations :: 0:s -> neededIterations
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair
if3 :: true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair
minus :: 0:s -> 0:s -> 0:s
if4 :: true:false -> 0:s -> 0:s -> 0:s -> pair
s :: 0:s -> 0:s
a :: b:c
b :: b:c
c :: b:c
const :: pair
const1 :: result
const2 :: neededIterations

Rewrite Strategy: INNERMOST
----------------------------------------

(7) 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
   true => 1
   false => 0
   b => 0
   c => 1
   const => 0
   const1 => 0
   const2 => 0

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

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

   a -{ 1 }-> 1 :|: 
   a -{ 1 }-> 0 :|: 
   gcd(z, z') -{ 1 }-> gcd2(x, y, 0) :|: x >= 0, y >= 0, z = x, z' = y
   gcd2(z, z', z'') -{ 1 }-> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) :|: z'' = i, x >= 0, y >= 0, i >= 0, z = x, z' = y
   if1(z, z', z'', z1, z2, z3, z4) -{ 1 }-> if2(b1, b2, b3, x, y, i) :|: z2 = x, b1 >= 0, z1 = b3, z3 = y, y >= 0, z4 = i, i >= 0, z' = b1, z = 0, z'' = b2, b3 >= 0, b2 >= 0, x >= 0
   if1(z, z', z'', z1, z2, z3, z4) -{ 1 }-> 1 + (1 + y) + (1 + i) :|: z2 = x, b1 >= 0, z = 1, z1 = b3, z3 = y, y >= 0, z4 = i, i >= 0, z' = b1, z'' = b2, b3 >= 0, b2 >= 0, x >= 0
   if2(z, z', z'', z1, z2, z3) -{ 1 }-> if3(b2, b3, x, y, i) :|: b2 >= 0, z2 = y, z3 = i, x >= 0, y >= 0, i >= 0, z' = b2, z = 0, z'' = b3, z1 = x, b3 >= 0
   if2(z, z', z'', z1, z2, z3) -{ 1 }-> 1 + (1 + x) + (1 + i) :|: b2 >= 0, z2 = y, z = 1, z3 = i, x >= 0, y >= 0, i >= 0, z' = b2, z'' = b3, z1 = x, b3 >= 0
   if3(z, z', z'', z1, z2) -{ 1 }-> if4(b3, x, y, i) :|: z1 = y, z2 = i, z' = b3, z = 1, x >= 0, y >= 0, i >= 0, z'' = x, b3 >= 0
   if3(z, z', z'', z1, z2) -{ 1 }-> gcd2(minus(x, y), y, i) :|: z1 = y, z2 = i, z' = b3, x >= 0, y >= 0, i >= 0, z'' = x, z = 0, b3 >= 0
   if4(z, z', z'', z1) -{ 1 }-> gcd2(x, minus(y, x), i) :|: z' = x, z'' = y, x >= 0, y >= 0, i >= 0, z = 0, z1 = i
   if4(z, z', z'', z1) -{ 1 }-> 1 + (1 + x) + (1 + i) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0, i >= 0, z1 = i
   inc(z) -{ 1 }-> 0 :|: z = 0
   inc(z) -{ 1 }-> 1 + inc(i) :|: z = 1 + i, i >= 0
   le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   le(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y
   le(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0
   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') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y

Only complete derivations are relevant for the runtime complexity.

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

(9) CompleteCoflocoProof (FINISHED)
Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:

eq(start(V1, V, V5, V17, V15, V16, V10),0,[gcd(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[gcd2(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[if1(V1, V, V5, V17, V15, V16, V10, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0,V15 >= 0,V16 >= 0,V10 >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[if2(V1, V, V5, V17, V15, V16, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0,V15 >= 0,V16 >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[if3(V1, V, V5, V17, V15, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0,V15 >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[if4(V1, V, V5, V17, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[inc(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[le(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V5, V17, V15, V16, V10),0,[a(Out)],[]).
eq(gcd(V1, V, Out),1,[gcd2(V3, V2, 0, Ret)],[Out = Ret,V3 >= 0,V2 >= 0,V1 = V3,V = V2]).
eq(gcd2(V1, V, V5, Out),1,[le(V4, 0, Ret0),le(V7, 0, Ret1),le(V4, V7, Ret2),le(V7, V4, Ret3),inc(V6, Ret6),if1(Ret0, Ret1, Ret2, Ret3, V4, V7, Ret6, Ret4)],[Out = Ret4,V5 = V6,V4 >= 0,V7 >= 0,V6 >= 0,V1 = V4,V = V7]).
eq(if1(V1, V, V5, V17, V15, V16, V10, Out),1,[],[Out = 3 + V11 + V9,V15 = V12,V8 >= 0,V1 = 1,V17 = V14,V16 = V11,V11 >= 0,V10 = V9,V9 >= 0,V = V8,V5 = V13,V14 >= 0,V13 >= 0,V12 >= 0]).
eq(if1(V1, V, V5, V17, V15, V16, V10, Out),1,[if2(V19, V20, V23, V21, V22, V18, Ret5)],[Out = Ret5,V15 = V21,V19 >= 0,V17 = V23,V16 = V22,V22 >= 0,V10 = V18,V18 >= 0,V = V19,V1 = 0,V5 = V20,V23 >= 0,V20 >= 0,V21 >= 0]).
eq(if2(V1, V, V5, V17, V15, V16, Out),1,[],[Out = 3 + V25 + V26,V27 >= 0,V15 = V24,V1 = 1,V16 = V26,V25 >= 0,V24 >= 0,V26 >= 0,V = V27,V5 = V28,V17 = V25,V28 >= 0]).
eq(if2(V1, V, V5, V17, V15, V16, Out),1,[if3(V32, V33, V31, V30, V29, Ret7)],[Out = Ret7,V32 >= 0,V15 = V30,V16 = V29,V31 >= 0,V30 >= 0,V29 >= 0,V = V32,V1 = 0,V5 = V33,V17 = V31,V33 >= 0]).
eq(if3(V1, V, V5, V17, V15, Out),1,[minus(V36, V35, Ret01),gcd2(Ret01, V35, V34, Ret8)],[Out = Ret8,V17 = V35,V15 = V34,V = V37,V36 >= 0,V35 >= 0,V34 >= 0,V5 = V36,V1 = 0,V37 >= 0]).
eq(if3(V1, V, V5, V17, V15, Out),1,[if4(V41, V38, V40, V39, Ret9)],[Out = Ret9,V17 = V40,V15 = V39,V = V41,V1 = 1,V38 >= 0,V40 >= 0,V39 >= 0,V5 = V38,V41 >= 0]).
eq(if4(V1, V, V5, V17, Out),1,[minus(V42, V43, Ret11),gcd2(V43, Ret11, V44, Ret10)],[Out = Ret10,V = V43,V5 = V42,V43 >= 0,V42 >= 0,V44 >= 0,V1 = 0,V17 = V44]).
eq(if4(V1, V, V5, V17, Out),1,[],[Out = 3 + V45 + V46,V = V46,V5 = V47,V1 = 1,V46 >= 0,V47 >= 0,V45 >= 0,V17 = V45]).
eq(inc(V1, Out),1,[],[Out = 0,V1 = 0]).
eq(inc(V1, Out),1,[inc(V48, Ret12)],[Out = 1 + Ret12,V1 = 1 + V48,V48 >= 0]).
eq(le(V1, V, Out),1,[],[Out = 0,V49 >= 0,V1 = 1 + V49,V = 0]).
eq(le(V1, V, Out),1,[],[Out = 1,V50 >= 0,V1 = 0,V = V50]).
eq(le(V1, V, Out),1,[le(V52, V51, Ret13)],[Out = Ret13,V = 1 + V51,V52 >= 0,V51 >= 0,V1 = 1 + V52]).
eq(minus(V1, V, Out),1,[],[Out = V53,V53 >= 0,V1 = V53,V = 0]).
eq(minus(V1, V, Out),1,[],[Out = 0,V54 >= 0,V1 = 0,V = V54]).
eq(minus(V1, V, Out),1,[minus(V55, V56, Ret14)],[Out = Ret14,V = 1 + V56,V55 >= 0,V56 >= 0,V1 = 1 + V55]).
eq(a(Out),1,[],[Out = 0]).
eq(a(Out),1,[],[Out = 1]).
input_output_vars(gcd(V1,V,Out),[V1,V],[Out]).
input_output_vars(gcd2(V1,V,V5,Out),[V1,V,V5],[Out]).
input_output_vars(if1(V1,V,V5,V17,V15,V16,V10,Out),[V1,V,V5,V17,V15,V16,V10],[Out]).
input_output_vars(if2(V1,V,V5,V17,V15,V16,Out),[V1,V,V5,V17,V15,V16],[Out]).
input_output_vars(if3(V1,V,V5,V17,V15,Out),[V1,V,V5,V17,V15],[Out]).
input_output_vars(if4(V1,V,V5,V17,Out),[V1,V,V5,V17],[Out]).
input_output_vars(inc(V1,Out),[V1],[Out]).
input_output_vars(le(V1,V,Out),[V1,V],[Out]).
input_output_vars(minus(V1,V,Out),[V1,V],[Out]).
input_output_vars(a(Out),[],[Out]).


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

#### Computed strongly connected components 
0. non_recursive  : [a/1]
1. recursive  : [minus/3]
2. recursive  : [inc/2]
3. recursive  : [le/3]
4. recursive  : [gcd2/4,if1/8,if2/7,if3/6,if4/5]
5. non_recursive  : [gcd/3]
6. non_recursive  : [start/7]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into a/1
1. SCC is partially evaluated into minus/3
2. SCC is partially evaluated into inc/2
3. SCC is partially evaluated into le/3
4. SCC is partially evaluated into gcd2/4
5. SCC is completely evaluated into other SCCs
6. SCC is partially evaluated into start/7

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

### Specialization of cost equations a/1 
* CE 33 is refined into CE [34] 
* CE 32 is refined into CE [35] 


### Cost equations --> "Loop" of a/1 
* CEs [34] --> Loop 16 
* CEs [35] --> Loop 17 

### Ranking functions of CR a(Out) 

#### Partial ranking functions of CR a(Out) 


### Specialization of cost equations minus/3 
* CE 21 is refined into CE [36] 
* CE 19 is refined into CE [37] 
* CE 20 is refined into CE [38] 


### Cost equations --> "Loop" of minus/3 
* CEs [37] --> Loop 18 
* CEs [38] --> Loop 19 
* CEs [36] --> Loop 20 

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

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


### Specialization of cost equations inc/2 
* CE 28 is refined into CE [39] 
* CE 27 is refined into CE [40] 


### Cost equations --> "Loop" of inc/2 
* CEs [40] --> Loop 21 
* CEs [39] --> Loop 22 

### Ranking functions of CR inc(V1,Out) 
* RF of phase [22]: [V1]

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


### Specialization of cost equations le/3 
* CE 31 is refined into CE [41] 
* CE 29 is refined into CE [42] 
* CE 30 is refined into CE [43] 


### Cost equations --> "Loop" of le/3 
* CEs [42] --> Loop 23 
* CEs [43] --> Loop 24 
* CEs [41] --> Loop 25 

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

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


### Specialization of cost equations gcd2/4 
* CE 25 is refined into CE [44,45,46,47] 
* CE 24 is refined into CE [48,49] 
* CE 26 is refined into CE [50,51] 
* CE 22 is refined into CE [52,53] 
* CE 23 is refined into CE [54,55] 


### Cost equations --> "Loop" of gcd2/4 
* CEs [53] --> Loop 26 
* CEs [55] --> Loop 27 
* CEs [52] --> Loop 28 
* CEs [54] --> Loop 29 
* CEs [49] --> Loop 30 
* CEs [48] --> Loop 31 
* CEs [51] --> Loop 32 
* CEs [50] --> Loop 33 
* CEs [47] --> Loop 34 
* CEs [46] --> Loop 35 
* CEs [45] --> Loop 36 
* CEs [44] --> Loop 37 

### Ranking functions of CR gcd2(V1,V,V5,Out) 
* RF of phase [26,27]: [V1+V-2]
* RF of phase [28,29]: [V1+V-2]

#### Partial ranking functions of CR gcd2(V1,V,V5,Out) 
* Partial RF of phase [26,27]:
  - RF of loop [26:1]:
    V1-1
    V1-V depends on loops [27:1] 
  - RF of loop [27:1]:
    V-1
    -V1+V depends on loops [26:1] 
* Partial RF of phase [28,29]:
  - RF of loop [28:1]:
    V1-1
    V1-V depends on loops [29:1] 
  - RF of loop [29:1]:
    V-1
    -V1+V depends on loops [28:1] 


### Specialization of cost equations start/7 
* CE 1 is refined into CE [56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71] 
* CE 2 is refined into CE [72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87] 
* CE 3 is refined into CE [88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103] 
* CE 4 is refined into CE [104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119] 
* CE 5 is refined into CE [120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135] 
* CE 6 is refined into CE [136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151] 
* CE 7 is refined into CE [152] 
* CE 8 is refined into CE [153] 
* CE 9 is refined into CE [154] 
* CE 10 is refined into CE [155] 
* CE 11 is refined into CE [156] 
* CE 12 is refined into CE [157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172] 
* CE 13 is refined into CE [173,174,175,176,177] 
* CE 14 is refined into CE [178,179,180,181,182,183,184,185,186,187] 
* CE 15 is refined into CE [188,189] 
* CE 16 is refined into CE [190,191,192,193] 
* CE 17 is refined into CE [194,195,196,197] 
* CE 18 is refined into CE [198,199] 


### Cost equations --> "Loop" of start/7 
* CEs [56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199] --> Loop 38 

### Ranking functions of CR start(V1,V,V5,V17,V15,V16,V10) 

#### Partial ranking functions of CR start(V1,V,V5,V17,V15,V16,V10) 


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

#### Cost of chains of a(Out):
* Chain [17]: 1
  with precondition: [Out=0] 

* Chain [16]: 1
  with precondition: [Out=1] 


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

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

* Chain [[20],18]: 1*it(20)+1
  Such that:it(20) =< V

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

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

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


#### Cost of chains of inc(V1,Out):
* Chain [[22],21]: 1*it(22)+1
  Such that:it(22) =< Out

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

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


#### Cost of chains of le(V1,V,Out):
* Chain [[25],24]: 1*it(25)+1
  Such that:it(25) =< V1

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

* Chain [[25],23]: 1*it(25)+1
  Such that:it(25) =< V

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

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

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


#### Cost of chains of gcd2(V1,V,V5,Out):
* Chain [[28,29],31]: 10*it(28)+11*it(29)+2*s(1)+3*s(13)+3*s(15)+10
  Such that:aux(7) =< -V1+V
aux(8) =< V1
aux(5) =< V1-V
aux(9) =< V1+V
aux(10) =< V1+V-2*Out+6
aux(11) =< V1-Out+3
aux(12) =< V
aux(13) =< V-Out+3
aux(1) =< Out
s(1) =< aux(1)
aux(6) =< aux(8)
it(28) =< aux(8)
it(28) =< aux(9)
it(29) =< aux(9)
it(28) =< aux(10)
it(29) =< aux(10)
aux(6) =< aux(11)
it(28) =< aux(11)
aux(4) =< aux(12)
it(29) =< aux(12)
aux(4) =< aux(13)
it(29) =< aux(13)
it(29) =< aux(6)+aux(7)
it(28) =< aux(4)+aux(5)
s(15) =< aux(4)
s(13) =< aux(6)

  with precondition: [V5=0,Out>=4,V1+3>=Out,V+3>=Out,V+V1+9>=3*Out] 

* Chain [[26,27],30]: 10*it(26)+11*it(27)+2*s(17)+1*s(19)+3*s(34)+1*s(35)+3*s(37)+1*s(38)+10
  Such that:aux(21) =< -V1+V
aux(23) =< V1
aux(18) =< V1-V
aux(24) =< V1+V
aux(25) =< V1+V+2*V5-2*Out+6
aux(26) =< V1+V5-Out+3
aux(27) =< V
aux(28) =< V+V5-Out+3
aux(14) =< -V5+Out
aux(29) =< V5
s(19) =< aux(29)
s(17) =< aux(14)
aux(20) =< aux(23)
it(26) =< aux(23)
it(26) =< aux(24)
it(27) =< aux(24)
it(26) =< aux(25)
it(27) =< aux(25)
aux(20) =< aux(26)
it(26) =< aux(26)
aux(17) =< aux(27)
it(27) =< aux(27)
aux(17) =< aux(28)
it(27) =< aux(28)
aux(22) =< aux(29)
it(27) =< aux(20)+aux(21)
it(26) =< aux(17)+aux(18)
s(38) =< it(27)*aux(22)
s(35) =< it(26)*aux(29)
s(37) =< aux(17)
s(34) =< aux(20)

  with precondition: [V5>=1,Out>=V5+4,V1+V5+3>=Out,V+V5+3>=Out,V+V1+3*V5+9>=3*Out] 

* Chain [37]: 7
  with precondition: [V1=0,V=0,V5=0,Out=3] 

* Chain [36]: 1*s(40)+7
  Such that:s(40) =< V5

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

* Chain [35]: 7
  with precondition: [V1=0,V5=0,V+3=Out,V>=1] 

* Chain [34]: 1*s(41)+7
  Such that:s(41) =< V5

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

* Chain [33]: 8
  with precondition: [V=0,V5=0,V1+3=Out,V1>=1] 

* Chain [32]: 1*s(42)+8
  Such that:s(42) =< V5

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

* Chain [31]: 2*s(1)+10
  Such that:aux(1) =< V
s(1) =< aux(1)

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

* Chain [30]: 2*s(17)+1*s(19)+10
  Such that:s(19) =< V5
aux(14) =< V1
s(17) =< aux(14)

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


#### Cost of chains of start(V1,V,V5,V17,V15,V16,V10):
* Chain [38]: 16*s(43)+34*s(47)+27*s(50)+4*s(66)+20*s(68)+22*s(69)+6*s(71)+6*s(72)+1*s(95)+1*s(96)+26*s(103)+4*s(122)+20*s(124)+22*s(125)+12*s(127)+6*s(128)+1*s(151)+1*s(152)+14*s(159)+4*s(178)+20*s(180)+22*s(181)+12*s(183)+6*s(184)+1*s(207)+1*s(208)+6*s(221)+4*s(234)+20*s(236)+22*s(237)+6*s(239)+1*s(263)+1*s(264)+6*s(277)+4*s(290)+20*s(292)+22*s(293)+6*s(295)+1*s(319)+1*s(320)+6*s(333)+4*s(346)+20*s(348)+22*s(349)+6*s(351)+6*s(352)+1*s(375)+1*s(376)+10*s(386)+6*s(389)+4*s(402)+20*s(404)+22*s(405)+6*s(407)+15*s(408)+1*s(431)+1*s(432)+6*s(446)+30*s(448)+33*s(449)+9*s(452)+5*s(457)+1*s(494)+1*s(495)+15
  Such that:aux(75) =< -V1+V
aux(76) =< V1
aux(77) =< V1+3
aux(78) =< V1-V
aux(79) =< V1+V
aux(80) =< V1+V+6
aux(81) =< -2*V+V5
aux(82) =< -V+V5
aux(83) =< -V+V5+3
aux(84) =< V
aux(85) =< V+3
aux(86) =< 2*V-V5
aux(87) =< -2*V5+V17
aux(88) =< -V5+V17
aux(89) =< -V5+V17+3
aux(90) =< -V5+2*V17
aux(91) =< V5
aux(92) =< V5+3
aux(93) =< V5+6
aux(94) =< V5-2*V17
aux(95) =< V5-V17
aux(96) =< V5-V17+3
aux(97) =< 2*V5-V17
aux(98) =< V5/2
aux(99) =< -2*V17+V15
aux(100) =< -V17+V15
aux(101) =< -V17+V15+3
aux(102) =< -V17+2*V15
aux(103) =< V17
aux(104) =< V17+3
aux(105) =< V17+6
aux(106) =< V17-2*V15
aux(107) =< V17-V15
aux(108) =< V17-V15+3
aux(109) =< 2*V17-V15
aux(110) =< V17/2
aux(111) =< -2*V15+V16
aux(112) =< -V15+V16
aux(113) =< -V15+V16+3
aux(114) =< -V15+2*V16
aux(115) =< V15
aux(116) =< V15+3
aux(117) =< V15+6
aux(118) =< V15-2*V16
aux(119) =< V15-V16
aux(120) =< V15-V16+3
aux(121) =< 2*V15-V16
aux(122) =< V15/2
aux(123) =< V16
aux(124) =< V16+3
aux(125) =< V16+6
aux(126) =< V16/2
aux(127) =< V10
s(457) =< aux(76)
s(386) =< aux(84)
s(159) =< aux(91)
s(103) =< aux(103)
s(47) =< aux(115)
s(50) =< aux(123)
s(43) =< aux(127)
s(446) =< aux(85)
s(447) =< aux(76)
s(448) =< aux(76)
s(448) =< aux(79)
s(449) =< aux(79)
s(448) =< aux(80)
s(449) =< aux(80)
s(447) =< aux(77)
s(448) =< aux(77)
s(403) =< aux(84)
s(449) =< aux(84)
s(403) =< aux(85)
s(449) =< aux(85)
s(449) =< s(447)+aux(75)
s(448) =< s(403)+aux(78)
s(408) =< s(403)
s(452) =< s(447)
s(493) =< aux(91)
s(494) =< s(449)*s(493)
s(495) =< s(448)*aux(91)
s(402) =< aux(83)
s(404) =< aux(84)
s(404) =< aux(91)
s(405) =< aux(91)
s(404) =< aux(93)
s(405) =< aux(93)
s(404) =< aux(85)
s(406) =< aux(82)
s(405) =< aux(82)
s(406) =< aux(83)
s(405) =< aux(83)
s(405) =< s(403)+aux(81)
s(404) =< s(406)+aux(86)
s(407) =< s(406)
s(430) =< aux(103)
s(431) =< s(405)*s(430)
s(432) =< s(404)*aux(103)
s(346) =< aux(89)
s(347) =< aux(91)
s(348) =< aux(91)
s(348) =< aux(103)
s(349) =< aux(103)
s(348) =< aux(105)
s(349) =< aux(105)
s(347) =< aux(92)
s(348) =< aux(92)
s(350) =< aux(88)
s(349) =< aux(88)
s(350) =< aux(89)
s(349) =< aux(89)
s(349) =< s(347)+aux(87)
s(348) =< s(350)+aux(97)
s(351) =< s(350)
s(352) =< s(347)
s(206) =< aux(115)
s(375) =< s(349)*s(206)
s(376) =< s(348)*aux(115)
s(178) =< aux(104)
s(179) =< aux(95)
s(180) =< aux(95)
s(180) =< aux(91)
s(181) =< aux(91)
s(180) =< aux(93)
s(181) =< aux(93)
s(179) =< aux(96)
s(180) =< aux(96)
s(182) =< aux(103)
s(181) =< aux(103)
s(182) =< aux(104)
s(181) =< aux(104)
s(181) =< s(179)+aux(90)
s(180) =< s(182)+aux(94)
s(183) =< s(182)
s(184) =< s(179)
s(207) =< s(181)*s(206)
s(208) =< s(180)*aux(115)
s(389) =< aux(98)
s(290) =< aux(101)
s(292) =< aux(103)
s(292) =< aux(115)
s(293) =< aux(115)
s(292) =< aux(117)
s(293) =< aux(117)
s(292) =< aux(104)
s(294) =< aux(100)
s(293) =< aux(100)
s(294) =< aux(101)
s(293) =< aux(101)
s(293) =< s(182)+aux(99)
s(292) =< s(294)+aux(109)
s(295) =< s(294)
s(150) =< aux(123)
s(319) =< s(293)*s(150)
s(320) =< s(292)*aux(123)
s(122) =< aux(116)
s(123) =< aux(107)
s(124) =< aux(107)
s(124) =< aux(103)
s(125) =< aux(103)
s(124) =< aux(105)
s(125) =< aux(105)
s(123) =< aux(108)
s(124) =< aux(108)
s(126) =< aux(115)
s(125) =< aux(115)
s(126) =< aux(116)
s(125) =< aux(116)
s(125) =< s(123)+aux(102)
s(124) =< s(126)+aux(106)
s(127) =< s(126)
s(128) =< s(123)
s(151) =< s(125)*s(150)
s(152) =< s(124)*aux(123)
s(333) =< aux(110)
s(234) =< aux(113)
s(236) =< aux(115)
s(236) =< aux(123)
s(237) =< aux(123)
s(236) =< aux(125)
s(237) =< aux(125)
s(236) =< aux(116)
s(238) =< aux(112)
s(237) =< aux(112)
s(238) =< aux(113)
s(237) =< aux(113)
s(237) =< s(126)+aux(111)
s(236) =< s(238)+aux(121)
s(239) =< s(238)
s(94) =< aux(127)
s(263) =< s(237)*s(94)
s(264) =< s(236)*aux(127)
s(66) =< aux(124)
s(67) =< aux(119)
s(68) =< aux(119)
s(68) =< aux(115)
s(69) =< aux(115)
s(68) =< aux(117)
s(69) =< aux(117)
s(67) =< aux(120)
s(68) =< aux(120)
s(70) =< aux(123)
s(69) =< aux(123)
s(70) =< aux(124)
s(69) =< aux(124)
s(69) =< s(67)+aux(114)
s(68) =< s(70)+aux(118)
s(71) =< s(70)
s(72) =< s(67)
s(95) =< s(69)*s(94)
s(96) =< s(68)*aux(127)
s(277) =< aux(122)
s(221) =< aux(126)

  with precondition: [] 


Closed-form bounds of start(V1,V,V5,V17,V15,V16,V10): 
-------------------------------------
* Chain [38] with precondition: [] 
    - Upper bound: nat(V1)*44+15+nat(V5)*nat(V1)+nat(V)*45+nat(V17)*nat(V)+nat(V5)*84+nat(V17)*nat(V5)+nat(V5)*2*nat(V15)+nat(V1+V)*nat(V5)+nat(V17)*102+nat(V15)*nat(V17)+nat(V17)*2*nat(V16)+nat(V15)*110+nat(V16)*nat(V15)+nat(V15)*2*nat(V10)+nat(V5-V17)*nat(V15)+nat(V16)*55+nat(V10)*nat(V16)+nat(V17-V15)*nat(V16)+nat(V10)*16+nat(V15-V16)*nat(V10)+nat(V1+V)*33+nat(V+3)*6+nat(V17+3)*4+nat(V15+3)*4+nat(V16+3)*4+nat(-V+V5)*6+nat(-V5+V17)*6+nat(-V17+V15)*6+nat(-V15+V16)*6+nat(-V+V5+3)*4+nat(-V5+V17+3)*4+nat(-V17+V15+3)*4+nat(-V15+V16+3)*4+nat(V5-V17)*26+nat(V17-V15)*26+nat(V15-V16)*26+nat(V5/2)*6+nat(V17/2)*6+nat(V15/2)*6+nat(V16/2)*6 
    - Complexity: n^2 

### Maximum cost of start(V1,V,V5,V17,V15,V16,V10): nat(V1)*44+15+nat(V5)*nat(V1)+nat(V)*45+nat(V17)*nat(V)+nat(V5)*84+nat(V17)*nat(V5)+nat(V5)*2*nat(V15)+nat(V1+V)*nat(V5)+nat(V17)*102+nat(V15)*nat(V17)+nat(V17)*2*nat(V16)+nat(V15)*110+nat(V16)*nat(V15)+nat(V15)*2*nat(V10)+nat(V5-V17)*nat(V15)+nat(V16)*55+nat(V10)*nat(V16)+nat(V17-V15)*nat(V16)+nat(V10)*16+nat(V15-V16)*nat(V10)+nat(V1+V)*33+nat(V+3)*6+nat(V17+3)*4+nat(V15+3)*4+nat(V16+3)*4+nat(-V+V5)*6+nat(-V5+V17)*6+nat(-V17+V15)*6+nat(-V15+V16)*6+nat(-V+V5+3)*4+nat(-V5+V17+3)*4+nat(-V17+V15+3)*4+nat(-V15+V16+3)*4+nat(V5-V17)*26+nat(V17-V15)*26+nat(V15-V16)*26+nat(V5/2)*6+nat(V17/2)*6+nat(V15/2)*6+nat(V16/2)*6 
Asymptotic class: n^2 
* Total analysis performed in 2881 ms.


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

(10)
BOUNDS(1, n^2)

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

(11) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(12)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   gcd(x, y) -> gcd2(x, y, 0')
   gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
   if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i))
   if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
   if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i))
   if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
   if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
   if3(true, b3, x, y, i) -> if4(b3, x, y, i)
   if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
   if4(true, x, y, i) -> pair(result(x), neededIterations(i))
   inc(0') -> 0'
   inc(s(i)) -> s(inc(i))
   le(s(x), 0') -> false
   le(0', y) -> true
   le(s(x), s(y)) -> le(x, y)
   minus(x, 0') -> x
   minus(0', y) -> 0'
   minus(s(x), s(y)) -> minus(x, y)
   a -> b
   a -> c

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(13) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
pair/0
pair/1
result/0
neededIterations/0

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

(14)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   gcd(x, y) -> gcd2(x, y, 0')
   gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
   if1(true, b1, b2, b3, x, y, i) -> pair
   if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
   if2(true, b2, b3, x, y, i) -> pair
   if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
   if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
   if3(true, b3, x, y, i) -> if4(b3, x, y, i)
   if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
   if4(true, x, y, i) -> pair
   inc(0') -> 0'
   inc(s(i)) -> s(inc(i))
   le(s(x), 0') -> false
   le(0', y) -> true
   le(s(x), s(y)) -> le(x, y)
   minus(x, 0') -> x
   minus(0', y) -> 0'
   minus(s(x), s(y)) -> minus(x, y)
   a -> b
   a -> c

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(15) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(16)
Obligation:
Innermost TRS:
Rules:
gcd(x, y) -> gcd2(x, y, 0')
gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
if1(true, b1, b2, b3, x, y, i) -> pair
if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
if2(true, b2, b3, x, y, i) -> pair
if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
if3(true, b3, x, y, i) -> if4(b3, x, y, i)
if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
if4(true, x, y, i) -> pair
inc(0') -> 0'
inc(s(i)) -> s(inc(i))
le(s(x), 0') -> false
le(0', y) -> true
le(s(x), s(y)) -> le(x, y)
minus(x, 0') -> x
minus(0', y) -> 0'
minus(s(x), s(y)) -> minus(x, y)
a -> b
a -> c

Types:
gcd :: 0':s -> 0':s -> pair
gcd2 :: 0':s -> 0':s -> 0':s -> pair
0' :: 0':s
if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
le :: 0':s -> 0':s -> true:false
inc :: 0':s -> 0':s
true :: true:false
pair :: pair
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
minus :: 0':s -> 0':s -> 0':s
if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair
s :: 0':s -> 0':s
a :: b:c
b :: b:c
c :: b:c
hole_pair1_0 :: pair
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_b:c4_0 :: b:c
gen_0':s5_0 :: Nat -> 0':s

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

(17) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
gcd2, le, inc, minus

They will be analysed ascendingly in the following order:
le < gcd2
inc < gcd2
minus < gcd2

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

(18)
Obligation:
Innermost TRS:
Rules:
gcd(x, y) -> gcd2(x, y, 0')
gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
if1(true, b1, b2, b3, x, y, i) -> pair
if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
if2(true, b2, b3, x, y, i) -> pair
if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
if3(true, b3, x, y, i) -> if4(b3, x, y, i)
if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
if4(true, x, y, i) -> pair
inc(0') -> 0'
inc(s(i)) -> s(inc(i))
le(s(x), 0') -> false
le(0', y) -> true
le(s(x), s(y)) -> le(x, y)
minus(x, 0') -> x
minus(0', y) -> 0'
minus(s(x), s(y)) -> minus(x, y)
a -> b
a -> c

Types:
gcd :: 0':s -> 0':s -> pair
gcd2 :: 0':s -> 0':s -> 0':s -> pair
0' :: 0':s
if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
le :: 0':s -> 0':s -> true:false
inc :: 0':s -> 0':s
true :: true:false
pair :: pair
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
minus :: 0':s -> 0':s -> 0':s
if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair
s :: 0':s -> 0':s
a :: b:c
b :: b:c
c :: b:c
hole_pair1_0 :: pair
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_b:c4_0 :: b:c
gen_0':s5_0 :: Nat -> 0':s


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


The following defined symbols remain to be analysed:
le, gcd2, inc, minus

They will be analysed ascendingly in the following order:
le < gcd2
inc < gcd2
minus < gcd2

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

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0)

Induction Base:
le(gen_0':s5_0(+(1, 0)), gen_0':s5_0(0)) ->_R^Omega(1)
false

Induction Step:
le(gen_0':s5_0(+(1, +(n7_0, 1))), gen_0':s5_0(+(n7_0, 1))) ->_R^Omega(1)
le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) ->_IH
false

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

(20)
Complex Obligation (BEST)

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

(21)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
gcd(x, y) -> gcd2(x, y, 0')
gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
if1(true, b1, b2, b3, x, y, i) -> pair
if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
if2(true, b2, b3, x, y, i) -> pair
if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
if3(true, b3, x, y, i) -> if4(b3, x, y, i)
if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
if4(true, x, y, i) -> pair
inc(0') -> 0'
inc(s(i)) -> s(inc(i))
le(s(x), 0') -> false
le(0', y) -> true
le(s(x), s(y)) -> le(x, y)
minus(x, 0') -> x
minus(0', y) -> 0'
minus(s(x), s(y)) -> minus(x, y)
a -> b
a -> c

Types:
gcd :: 0':s -> 0':s -> pair
gcd2 :: 0':s -> 0':s -> 0':s -> pair
0' :: 0':s
if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
le :: 0':s -> 0':s -> true:false
inc :: 0':s -> 0':s
true :: true:false
pair :: pair
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
minus :: 0':s -> 0':s -> 0':s
if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair
s :: 0':s -> 0':s
a :: b:c
b :: b:c
c :: b:c
hole_pair1_0 :: pair
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_b:c4_0 :: b:c
gen_0':s5_0 :: Nat -> 0':s


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


The following defined symbols remain to be analysed:
le, gcd2, inc, minus

They will be analysed ascendingly in the following order:
le < gcd2
inc < gcd2
minus < gcd2

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

(22) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(23)
BOUNDS(n^1, INF)

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

(24)
Obligation:
Innermost TRS:
Rules:
gcd(x, y) -> gcd2(x, y, 0')
gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
if1(true, b1, b2, b3, x, y, i) -> pair
if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
if2(true, b2, b3, x, y, i) -> pair
if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
if3(true, b3, x, y, i) -> if4(b3, x, y, i)
if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
if4(true, x, y, i) -> pair
inc(0') -> 0'
inc(s(i)) -> s(inc(i))
le(s(x), 0') -> false
le(0', y) -> true
le(s(x), s(y)) -> le(x, y)
minus(x, 0') -> x
minus(0', y) -> 0'
minus(s(x), s(y)) -> minus(x, y)
a -> b
a -> c

Types:
gcd :: 0':s -> 0':s -> pair
gcd2 :: 0':s -> 0':s -> 0':s -> pair
0' :: 0':s
if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
le :: 0':s -> 0':s -> true:false
inc :: 0':s -> 0':s
true :: true:false
pair :: pair
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
minus :: 0':s -> 0':s -> 0':s
if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair
s :: 0':s -> 0':s
a :: b:c
b :: b:c
c :: b:c
hole_pair1_0 :: pair
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_b:c4_0 :: b:c
gen_0':s5_0 :: Nat -> 0':s


Lemmas:
le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0)


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


The following defined symbols remain to be analysed:
inc, gcd2, minus

They will be analysed ascendingly in the following order:
inc < gcd2
minus < gcd2

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

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
inc(gen_0':s5_0(n344_0)) -> gen_0':s5_0(n344_0), rt in Omega(1 + n344_0)

Induction Base:
inc(gen_0':s5_0(0)) ->_R^Omega(1)
0'

Induction Step:
inc(gen_0':s5_0(+(n344_0, 1))) ->_R^Omega(1)
s(inc(gen_0':s5_0(n344_0))) ->_IH
s(gen_0':s5_0(c345_0))

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

(26)
Obligation:
Innermost TRS:
Rules:
gcd(x, y) -> gcd2(x, y, 0')
gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
if1(true, b1, b2, b3, x, y, i) -> pair
if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
if2(true, b2, b3, x, y, i) -> pair
if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
if3(true, b3, x, y, i) -> if4(b3, x, y, i)
if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
if4(true, x, y, i) -> pair
inc(0') -> 0'
inc(s(i)) -> s(inc(i))
le(s(x), 0') -> false
le(0', y) -> true
le(s(x), s(y)) -> le(x, y)
minus(x, 0') -> x
minus(0', y) -> 0'
minus(s(x), s(y)) -> minus(x, y)
a -> b
a -> c

Types:
gcd :: 0':s -> 0':s -> pair
gcd2 :: 0':s -> 0':s -> 0':s -> pair
0' :: 0':s
if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
le :: 0':s -> 0':s -> true:false
inc :: 0':s -> 0':s
true :: true:false
pair :: pair
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
minus :: 0':s -> 0':s -> 0':s
if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair
s :: 0':s -> 0':s
a :: b:c
b :: b:c
c :: b:c
hole_pair1_0 :: pair
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_b:c4_0 :: b:c
gen_0':s5_0 :: Nat -> 0':s


Lemmas:
le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0)
inc(gen_0':s5_0(n344_0)) -> gen_0':s5_0(n344_0), rt in Omega(1 + n344_0)


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


The following defined symbols remain to be analysed:
minus, gcd2

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

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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
minus(gen_0':s5_0(n594_0), gen_0':s5_0(n594_0)) -> gen_0':s5_0(0), rt in Omega(1 + n594_0)

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

Induction Step:
minus(gen_0':s5_0(+(n594_0, 1)), gen_0':s5_0(+(n594_0, 1))) ->_R^Omega(1)
minus(gen_0':s5_0(n594_0), gen_0':s5_0(n594_0)) ->_IH
gen_0':s5_0(0)

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:
gcd(x, y) -> gcd2(x, y, 0')
gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i))
if1(true, b1, b2, b3, x, y, i) -> pair
if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i)
if2(true, b2, b3, x, y, i) -> pair
if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i)
if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i)
if3(true, b3, x, y, i) -> if4(b3, x, y, i)
if4(false, x, y, i) -> gcd2(x, minus(y, x), i)
if4(true, x, y, i) -> pair
inc(0') -> 0'
inc(s(i)) -> s(inc(i))
le(s(x), 0') -> false
le(0', y) -> true
le(s(x), s(y)) -> le(x, y)
minus(x, 0') -> x
minus(0', y) -> 0'
minus(s(x), s(y)) -> minus(x, y)
a -> b
a -> c

Types:
gcd :: 0':s -> 0':s -> pair
gcd2 :: 0':s -> 0':s -> 0':s -> pair
0' :: 0':s
if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
le :: 0':s -> 0':s -> true:false
inc :: 0':s -> 0':s
true :: true:false
pair :: pair
false :: true:false
if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair
minus :: 0':s -> 0':s -> 0':s
if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair
s :: 0':s -> 0':s
a :: b:c
b :: b:c
c :: b:c
hole_pair1_0 :: pair
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_b:c4_0 :: b:c
gen_0':s5_0 :: Nat -> 0':s


Lemmas:
le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0)
inc(gen_0':s5_0(n344_0)) -> gen_0':s5_0(n344_0), rt in Omega(1 + n344_0)
minus(gen_0':s5_0(n594_0), gen_0':s5_0(n594_0)) -> gen_0':s5_0(0), rt in Omega(1 + n594_0)


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


The following defined symbols remain to be analysed:
gcd2