/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), 0 ms]
    (6) CpxTypedWeightedCompleteTrs
    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (8) CpxRNTS
    (9) CompleteCoflocoProof [FINISHED, 1553 ms]
    (10) BOUNDS(1, n^2)
(11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(12) TRS for Loop Detection
    (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (14) BEST
        (15) proven lower bound
            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
            (17) BOUNDS(n^1, INF)
        (18) TRS for Loop Detection


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

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

   cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z)
   cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z)
   cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z)
   cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z)
   cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z)
   gr(0, x) -> false
   gr(s(x), 0) -> true
   gr(s(x), s(y)) -> gr(x, y)
   add(0, x) -> x
   add(s(x), y) -> s(add(x, y))
   p(0) -> 0
   p(s(x)) -> x

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:

   cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) [1]
   cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) [1]
   cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) [1]
   cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) [1]
   cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) [1]
   gr(0, x) -> false [1]
   gr(s(x), 0) -> true [1]
   gr(s(x), s(y)) -> gr(x, y) [1]
   add(0, x) -> x [1]
   add(s(x), y) -> s(add(x, y)) [1]
   p(0) -> 0 [1]
   p(s(x)) -> x [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:

   cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) [1]
   cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) [1]
   cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) [1]
   cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) [1]
   cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) [1]
   gr(0, x) -> false [1]
   gr(s(x), 0) -> true [1]
   gr(s(x), s(y)) -> gr(x, y) [1]
   add(0, x) -> x [1]
   add(s(x), y) -> s(add(x, y)) [1]
   p(0) -> 0 [1]
   p(s(x)) -> x [1]

The TRS has the following type information:
cond1 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3
true :: true:false
cond2 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3
gr :: 0:s -> 0:s -> true:false
0 :: 0:s
add :: 0:s -> 0:s -> 0:s
p :: 0:s -> 0:s
false :: true:false
cond3 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3
s :: 0:s -> 0:s

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:

   cond1(v0, v1, v2, v3) -> null_cond1 [0]

And the following fresh constants:    null_cond1

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

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

   cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) [1]
   cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) [1]
   cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) [1]
   cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) [1]
   cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) [1]
   gr(0, x) -> false [1]
   gr(s(x), 0) -> true [1]
   gr(s(x), s(y)) -> gr(x, y) [1]
   add(0, x) -> x [1]
   add(s(x), y) -> s(add(x, y)) [1]
   p(0) -> 0 [1]
   p(s(x)) -> x [1]
   cond1(v0, v1, v2, v3) -> null_cond1 [0]

The TRS has the following type information:
cond1 :: true:false -> 0:s -> 0:s -> 0:s -> null_cond1
true :: true:false
cond2 :: true:false -> 0:s -> 0:s -> 0:s -> null_cond1
gr :: 0:s -> 0:s -> true:false
0 :: 0:s
add :: 0:s -> 0:s -> 0:s
p :: 0:s -> 0:s
false :: true:false
cond3 :: true:false -> 0:s -> 0:s -> 0:s -> null_cond1
s :: 0:s -> 0:s
null_cond1 :: null_cond1

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:

   true => 1
   0 => 0
   false => 0
   null_cond1 => 0

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

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

   add(z', z'') -{ 1 }-> x :|: x >= 0, z'' = x, z' = 0
   add(z', z'') -{ 1 }-> 1 + add(x, y) :|: z' = 1 + x, z'' = y, x >= 0, y >= 0
   cond1(z', z'', z1, z2) -{ 1 }-> cond2(gr(x, 0), x, y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1
   cond1(z', z'', z1, z2) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, v3 >= 0, z' = v0
   cond2(z', z'', z1, z2) -{ 1 }-> cond3(gr(y, 0), x, y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 0
   cond2(z', z'', z1, z2) -{ 1 }-> cond1(gr(add(x, y), z), p(x), y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1
   cond3(z', z'', z1, z2) -{ 1 }-> cond1(gr(add(x, y), z), x, y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 0
   cond3(z', z'', z1, z2) -{ 1 }-> cond1(gr(add(x, y), z), x, p(y), z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1
   gr(z', z'') -{ 1 }-> gr(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y
   gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 1 + x, x >= 0
   gr(z', z'') -{ 1 }-> 0 :|: x >= 0, z'' = x, z' = 0
   p(z') -{ 1 }-> x :|: z' = 1 + x, x >= 0
   p(z') -{ 1 }-> 0 :|: z' = 0

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(V, V1, V6, V2),0,[cond1(V, V1, V6, V2, Out)],[V >= 0,V1 >= 0,V6 >= 0,V2 >= 0]).
eq(start(V, V1, V6, V2),0,[cond2(V, V1, V6, V2, Out)],[V >= 0,V1 >= 0,V6 >= 0,V2 >= 0]).
eq(start(V, V1, V6, V2),0,[cond3(V, V1, V6, V2, Out)],[V >= 0,V1 >= 0,V6 >= 0,V2 >= 0]).
eq(start(V, V1, V6, V2),0,[gr(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1, V6, V2),0,[add(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1, V6, V2),0,[p(V, Out)],[V >= 0]).
eq(cond1(V, V1, V6, V2, Out),1,[gr(V4, 0, Ret0),cond2(Ret0, V4, V3, V5, Ret)],[Out = Ret,V6 = V3,V5 >= 0,V2 = V5,V4 >= 0,V3 >= 0,V1 = V4,V = 1]).
eq(cond2(V, V1, V6, V2, Out),1,[add(V7, V9, Ret00),gr(Ret00, V8, Ret01),p(V7, Ret1),cond1(Ret01, Ret1, V9, V8, Ret2)],[Out = Ret2,V6 = V9,V8 >= 0,V2 = V8,V7 >= 0,V9 >= 0,V1 = V7,V = 1]).
eq(cond2(V, V1, V6, V2, Out),1,[gr(V10, 0, Ret02),cond3(Ret02, V11, V10, V12, Ret3)],[Out = Ret3,V6 = V10,V12 >= 0,V2 = V12,V11 >= 0,V10 >= 0,V1 = V11,V = 0]).
eq(cond3(V, V1, V6, V2, Out),1,[add(V13, V15, Ret001),gr(Ret001, V14, Ret03),p(V15, Ret21),cond1(Ret03, V13, Ret21, V14, Ret4)],[Out = Ret4,V6 = V15,V14 >= 0,V2 = V14,V13 >= 0,V15 >= 0,V1 = V13,V = 1]).
eq(cond3(V, V1, V6, V2, Out),1,[add(V17, V16, Ret002),gr(Ret002, V18, Ret04),cond1(Ret04, V17, V16, V18, Ret5)],[Out = Ret5,V6 = V16,V18 >= 0,V2 = V18,V17 >= 0,V16 >= 0,V1 = V17,V = 0]).
eq(gr(V, V1, Out),1,[],[Out = 0,V19 >= 0,V1 = V19,V = 0]).
eq(gr(V, V1, Out),1,[],[Out = 1,V1 = 0,V = 1 + V20,V20 >= 0]).
eq(gr(V, V1, Out),1,[gr(V22, V21, Ret6)],[Out = Ret6,V = 1 + V22,V22 >= 0,V21 >= 0,V1 = 1 + V21]).
eq(add(V, V1, Out),1,[],[Out = V23,V23 >= 0,V1 = V23,V = 0]).
eq(add(V, V1, Out),1,[add(V25, V24, Ret11)],[Out = 1 + Ret11,V = 1 + V25,V1 = V24,V25 >= 0,V24 >= 0]).
eq(p(V, Out),1,[],[Out = 0,V = 0]).
eq(p(V, Out),1,[],[Out = V26,V = 1 + V26,V26 >= 0]).
eq(cond1(V, V1, V6, V2, Out),0,[],[Out = 0,V2 = V29,V28 >= 0,V6 = V30,V27 >= 0,V1 = V27,V30 >= 0,V29 >= 0,V = V28]).
input_output_vars(cond1(V,V1,V6,V2,Out),[V,V1,V6,V2],[Out]).
input_output_vars(cond2(V,V1,V6,V2,Out),[V,V1,V6,V2],[Out]).
input_output_vars(cond3(V,V1,V6,V2,Out),[V,V1,V6,V2],[Out]).
input_output_vars(gr(V,V1,Out),[V,V1],[Out]).
input_output_vars(add(V,V1,Out),[V,V1],[Out]).
input_output_vars(p(V,Out),[V],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [add/3]
1. recursive  : [gr/3]
2. non_recursive  : [p/2]
3. recursive  : [cond1/5,cond2/5,cond3/5]
4. non_recursive  : [start/4]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into add/3
1. SCC is partially evaluated into gr/3
2. SCC is partially evaluated into p/2
3. SCC is partially evaluated into cond1/5
4. SCC is partially evaluated into start/4

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

### Specialization of cost equations add/3 
* CE 11 is refined into CE [21] 
* CE 10 is refined into CE [22] 


### Cost equations --> "Loop" of add/3 
* CEs [22] --> Loop 13 
* CEs [21] --> Loop 14 

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

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


### Specialization of cost equations gr/3 
* CE 14 is refined into CE [23] 
* CE 13 is refined into CE [24] 
* CE 12 is refined into CE [25] 


### Cost equations --> "Loop" of gr/3 
* CEs [24] --> Loop 15 
* CEs [25] --> Loop 16 
* CEs [23] --> Loop 17 

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

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


### Specialization of cost equations p/2 
* CE 16 is refined into CE [26] 
* CE 15 is refined into CE [27] 


### Cost equations --> "Loop" of p/2 
* CEs [26] --> Loop 18 
* CEs [27] --> Loop 19 

### Ranking functions of CR p(V,Out) 

#### Partial ranking functions of CR p(V,Out) 


### Specialization of cost equations cond1/5 
* CE 20 is refined into CE [28] 
* CE 17 is refined into CE [29,30,31] 
* CE 18 is refined into CE [32,33,34] 
* CE 19 is refined into CE [35] 


### Cost equations --> "Loop" of cond1/5 
* CEs [31] --> Loop 20 
* CEs [30] --> Loop 21 
* CEs [29] --> Loop 22 
* CEs [34] --> Loop 23 
* CEs [33] --> Loop 24 
* CEs [32] --> Loop 25 
* CEs [35] --> Loop 26 
* CEs [28] --> Loop 27 

### Ranking functions of CR cond1(V,V1,V6,V2,Out) 
* RF of phase [20]: [V1,V1+V6-1,V1+V6-V2]
* RF of phase [22]: [V1]
* RF of phase [23]: [V6-1,V6-V2]
* RF of phase [25]: [V6]

#### Partial ranking functions of CR cond1(V,V1,V6,V2,Out) 
* Partial RF of phase [20]:
  - RF of loop [20:1]:
    V1
    V1+V6-1
    V1+V6-V2
* Partial RF of phase [22]:
  - RF of loop [22:1]:
    V1
* Partial RF of phase [23]:
  - RF of loop [23:1]:
    V6-1
    V6-V2
* Partial RF of phase [25]:
  - RF of loop [25:1]:
    V6


### Specialization of cost equations start/4 
* CE 1 is refined into CE [36,37,38,39,40,41,42,43,44,45,46,47,48,49,50] 
* CE 5 is refined into CE [51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68] 
* CE 2 is refined into CE [69,70,71,72,73,74,75,76,77,78,79,80] 
* CE 3 is refined into CE [81,82,83,84,85,86] 
* CE 4 is refined into CE [87,88,89,90,91,92,93,94,95,96,97] 
* CE 6 is refined into CE [98,99,100,101,102,103,104] 
* CE 7 is refined into CE [105,106,107,108] 
* CE 8 is refined into CE [109,110] 
* CE 9 is refined into CE [111,112] 


### Cost equations --> "Loop" of start/4 
* CEs [50] --> Loop 28 
* CEs [64,65] --> Loop 29 
* CEs [45,62,63,104] --> Loop 30 
* CEs [58,59] --> Loop 31 
* CEs [48] --> Loop 32 
* CEs [46,47,49,66,67,68,103] --> Loop 33 
* CEs [42,43,44,60,61,102] --> Loop 34 
* CEs [39,54,100] --> Loop 35 
* CEs [40,41,55,56,57,101] --> Loop 36 
* CEs [37,38,52,53,98,99] --> Loop 37 
* CEs [36,51,106,107,108,110,112] --> Loop 38 
* CEs [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,105,109,111] --> Loop 39 

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

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


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

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

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

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


#### Cost of chains of gr(V,V1,Out):
* Chain [[17],16]: 1*it(17)+1
  Such that:it(17) =< V

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

* Chain [[17],15]: 1*it(17)+1
  Such that:it(17) =< V1

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

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

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


#### Cost of chains of p(V,Out):
* Chain [19]: 1
  with precondition: [V=0,Out=0] 

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


#### Cost of chains of cond1(V,V1,V6,V2,Out):
* Chain [[25],27]: 8*it(25)+0
  Such that:it(25) =< V6

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

* Chain [[25],26,27]: 8*it(25)+7
  Such that:it(25) =< V6

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

* Chain [[23],27]: 8*it(23)+1*s(3)+0
  Such that:it(23) =< V6-V2
aux(1) =< V2
s(3) =< it(23)*aux(1)

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

* Chain [[23],24,27]: 8*it(23)+1*s(3)+1*s(4)+8
  Such that:it(23) =< V6-V2
aux(2) =< V2
s(4) =< aux(2)
s(3) =< it(23)*aux(2)

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

* Chain [[22],[25],27]: 6*it(22)+8*it(25)+1*s(7)+0
  Such that:it(25) =< V6
aux(5) =< V1
it(22) =< aux(5)
s(7) =< it(22)*aux(5)

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

* Chain [[22],[25],26,27]: 6*it(22)+8*it(25)+1*s(7)+7
  Such that:it(25) =< V6
aux(6) =< V1
it(22) =< aux(6)
s(7) =< it(22)*aux(6)

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

* Chain [[22],27]: 6*it(22)+1*s(7)+0
  Such that:aux(7) =< V1
it(22) =< aux(7)
s(7) =< it(22)*aux(7)

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

* Chain [[22],26,27]: 6*it(22)+1*s(7)+7
  Such that:aux(8) =< V1
it(22) =< aux(8)
s(7) =< it(22)*aux(8)

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

* Chain [[20],[23],27]: 6*it(20)+8*it(23)+1*s(3)+1*s(12)+1*s(13)+0
  Such that:it(23) =< V6-V2
aux(12) =< V1
aux(13) =< V2
it(20) =< aux(12)
s(3) =< it(23)*aux(13)
s(13) =< it(20)*aux(13)
s(12) =< it(20)*aux(12)

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

* Chain [[20],[23],24,27]: 6*it(20)+8*it(23)+1*s(3)+1*s(4)+1*s(12)+1*s(13)+8
  Such that:it(23) =< V6-V2
aux(14) =< V1
aux(15) =< V2
it(20) =< aux(14)
s(4) =< aux(15)
s(3) =< it(23)*aux(15)
s(13) =< it(20)*aux(15)
s(12) =< it(20)*aux(14)

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

* Chain [[20],27]: 6*it(20)+1*s(12)+1*s(13)+0
  Such that:aux(11) =< V1
it(20) =< V1+V6-V2
aux(10) =< V2
it(20) =< aux(11)
s(13) =< it(20)*aux(10)
s(12) =< it(20)*aux(11)

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

* Chain [[20],24,27]: 6*it(20)+1*s(4)+1*s(12)+1*s(13)+8
  Such that:aux(16) =< V1
aux(17) =< V2
it(20) =< aux(16)
s(4) =< aux(17)
s(13) =< it(20)*aux(17)
s(12) =< it(20)*aux(16)

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

* Chain [[20],21,27]: 6*it(20)+1*s(12)+1*s(13)+1*s(14)+1*s(15)+6
  Such that:aux(11) =< V1
it(20) =< V1+V6-V2
s(14) =< -V6+V2
aux(18) =< V2
s(15) =< aux(18)
it(20) =< aux(11)
s(13) =< it(20)*aux(18)
s(12) =< it(20)*aux(11)

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

* Chain [27]: 0
  with precondition: [Out=0,V>=0,V1>=0,V6>=0,V2>=0] 

* Chain [26,27]: 7
  with precondition: [V=1,V1=0,V6=0,Out=0,V2>=0] 

* Chain [24,27]: 1*s(4)+8
  Such that:s(4) =< V6

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

* Chain [21,27]: 1*s(14)+1*s(15)+6
  Such that:s(14) =< V1
s(15) =< V1+V6

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


#### Cost of chains of start(V,V1,V6,V2):
* Chain [39]: 66*s(73)+26*s(75)+64*s(81)+8*s(83)+142*s(84)+21*s(90)+2*s(92)+3*s(97)+24*s(102)+4*s(105)+4*s(106)+9*s(108)+12*s(133)+16*s(134)+2*s(136)+2*s(137)+2*s(141)+1*s(165)+14
  Such that:s(130) =< V1-V2
s(165) =< -V6+V2
s(131) =< -V2
aux(43) =< V1
aux(44) =< V1+V6
aux(45) =< V1+V6-V2
aux(46) =< -V6+V2+1
aux(47) =< V6
aux(48) =< V6-V2
aux(49) =< V2
s(84) =< aux(43)
s(92) =< aux(44)
s(97) =< aux(46)
s(73) =< aux(47)
s(75) =< aux(49)
s(90) =< s(84)*aux(43)
s(102) =< aux(45)
s(81) =< aux(48)
s(102) =< aux(43)
s(105) =< s(102)*aux(49)
s(106) =< s(102)*aux(43)
s(108) =< s(84)*aux(49)
s(83) =< s(81)*aux(49)
s(133) =< s(130)
s(134) =< s(131)
s(133) =< aux(43)
s(136) =< s(133)*aux(49)
s(137) =< s(133)*aux(43)
s(141) =< s(134)*aux(49)

  with precondition: [V=0] 

* Chain [38]: 2*s(179)+1*s(180)+11
  Such that:s(180) =< V1
aux(50) =< V
s(179) =< aux(50)

  with precondition: [V>=1] 

* Chain [37]: 48*s(183)+11
  Such that:aux(51) =< V6
s(183) =< aux(51)

  with precondition: [V>=0,V1>=0,V6>=0,V2>=0] 

* Chain [36]: 9*s(188)+48*s(192)+6*s(194)+12
  Such that:aux(55) =< V6-V2
aux(56) =< V2
s(188) =< aux(56)
s(192) =< aux(55)
s(194) =< s(192)*aux(56)

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

* Chain [35]: 3*s(209)+11
  Such that:aux(57) =< V6
s(209) =< aux(57)

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

* Chain [34]: 76*s(212)+1*s(213)+64*s(215)+12*s(221)+11
  Such that:s(213) =< 1
aux(60) =< V1
aux(61) =< V6
s(212) =< aux(60)
s(215) =< aux(61)
s(221) =< s(212)*aux(60)

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

* Chain [33]: 58*s(234)+17*s(235)+1*s(236)+2*s(241)+36*s(246)+48*s(247)+6*s(249)+6*s(250)+9*s(252)+9*s(253)+6*s(254)+3*s(259)+12
  Such that:s(236) =< 1
aux(69) =< V1
aux(70) =< V1+V6-V2
aux(71) =< -V6+V2
aux(72) =< -V6+V2+1
aux(73) =< V6-V2
aux(74) =< V2
s(234) =< aux(69)
s(241) =< aux(71)
s(259) =< aux(72)
s(235) =< aux(74)
s(246) =< aux(70)
s(247) =< aux(73)
s(246) =< aux(69)
s(249) =< s(246)*aux(74)
s(250) =< s(246)*aux(69)
s(252) =< s(234)*aux(74)
s(253) =< s(234)*aux(69)
s(254) =< s(247)*aux(74)

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

* Chain [32]: 1*s(291)+2*s(292)+16*s(295)+2*s(297)+12
  Such that:s(291) =< 1
s(293) =< V6-V2
aux(75) =< V2
s(292) =< aux(75)
s(295) =< s(293)
s(297) =< s(295)*aux(75)

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

* Chain [31]: 26*s(298)+4*s(304)+11
  Such that:aux(77) =< V1
s(298) =< aux(77)
s(304) =< s(298)*aux(77)

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

* Chain [30]: 5*s(305)+3*s(306)+11
  Such that:aux(79) =< V1
aux(80) =< V1+V6
s(305) =< aux(79)
s(306) =< aux(80)

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

* Chain [29]: 20*s(313)+6*s(314)+12*s(322)+16*s(323)+2*s(325)+2*s(326)+3*s(328)+3*s(329)+2*s(330)+12
  Such that:s(319) =< V1-V2
s(320) =< -V2
aux(83) =< V1
aux(84) =< V2
s(313) =< aux(83)
s(314) =< aux(84)
s(322) =< s(319)
s(323) =< s(320)
s(322) =< aux(83)
s(325) =< s(322)*aux(84)
s(326) =< s(322)*aux(83)
s(328) =< s(313)*aux(84)
s(329) =< s(313)*aux(83)
s(330) =< s(323)*aux(84)

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

* Chain [28]: 1*s(331)+2*s(332)+1*s(333)+10
  Such that:s(333) =< -V6+V2
s(331) =< -V6+V2+1
aux(85) =< V2
s(332) =< aux(85)

  with precondition: [V=1,V1+V6=V2+1,V1>=2,V6>=0] 


Closed-form bounds of start(V,V1,V6,V2): 
-------------------------------------
* Chain [39] with precondition: [V=0] 
    - Upper bound: nat(V1)*142+14+nat(V1)*21*nat(V1)+nat(V1)*9*nat(V2)+nat(V1)*2*nat(V1-V2)+nat(V1)*4*nat(V1+V6-V2)+nat(V6)*66+nat(V2)*26+nat(V2)*2*nat(-V2)+nat(V2)*2*nat(V1-V2)+nat(V2)*8*nat(V6-V2)+nat(V2)*4*nat(V1+V6-V2)+nat(-V2)*16+nat(V1+V6)*2+nat(-V6+V2)+nat(-V6+V2+1)*3+nat(V1-V2)*12+nat(V6-V2)*64+nat(V1+V6-V2)*24 
    - Complexity: n^2 
* Chain [38] with precondition: [V>=1] 
    - Upper bound: 2*V+11+nat(V1) 
    - Complexity: n 
* Chain [37] with precondition: [V>=0,V1>=0,V6>=0,V2>=0] 
    - Upper bound: 48*V6+11 
    - Complexity: n 
* Chain [36] with precondition: [V=1,V1=0,V2>=1,V6>=V2+1] 
    - Upper bound: 48*V6-48*V2+(9*V2+12+(V6-V2)*(6*V2)) 
    - Complexity: n^2 
* Chain [35] with precondition: [V=1,V1=0,V6>=1,V2>=V6] 
    - Upper bound: 3*V6+11 
    - Complexity: n 
* Chain [34] with precondition: [V=1,V2=0,V1>=1,V6>=0] 
    - Upper bound: 76*V1+12+12*V1*V1+64*V6 
    - Complexity: n^2 
* Chain [33] with precondition: [V=1,V1>=1,V6>=0,V2>=1,V1+V6>=V2+1] 
    - Upper bound: 36*V1+36*V6-36*V2+(58*V1+13+9*V1*V1+9*V1*V2+(V1+V6-V2)*(6*V1)+17*V2+6*V2*nat(V6-V2)+(V1+V6-V2)*(6*V2)+nat(-V6+V2)*2+nat(-V6+V2+1)*3+nat(V6-V2)*48) 
    - Complexity: n^2 
* Chain [32] with precondition: [V=1,V1=1,V2>=1,V6>=V2+1] 
    - Upper bound: 16*V6-16*V2+(2*V2+13+(V6-V2)*(2*V2)) 
    - Complexity: n^2 
* Chain [31] with precondition: [V=1,V6=0,V2=0,V1>=1] 
    - Upper bound: 26*V1+11+4*V1*V1 
    - Complexity: n^2 
* Chain [30] with precondition: [V=1,V1>=1,V6>=0,V2>=V1+V6] 
    - Upper bound: 8*V1+3*V6+11 
    - Complexity: n 
* Chain [29] with precondition: [V=1,V6=0,V2>=1,V1>=V2+1] 
    - Upper bound: 12*V1-12*V2+(20*V1+12+3*V1*V1+3*V1*V2+(V1-V2)*(2*V1)+6*V2+(V1-V2)*(2*V2)) 
    - Complexity: n^2 
* Chain [28] with precondition: [V=1,V1+V6=V2+1,V1>=2,V6>=0] 
    - Upper bound: -2*V6+4*V2+11 
    - Complexity: n 

### Maximum cost of start(V,V1,V6,V2): max([max([nat(V6)*48+1,nat(V2)*2+max([nat(-V6+V2+1)+nat(-V6+V2),nat(V2)*2*nat(V6-V2)+2+nat(V6-V2)*16+max([1,nat(V2)*4*nat(V6-V2)+nat(V2)*7+nat(V6-V2)*32])])]),nat(V1)+1+max([2*V,nat(V1)*4+max([nat(V1+V6)*3,nat(V1)*3*nat(V1)+nat(V1)*15+max([nat(V1)*32+1+nat(V1)*5*nat(V1)+max([nat(V1)*9*nat(V2)+1+nat(V1)*6*nat(V1+V6-V2)+nat(V2)*17+nat(V2)*6*nat(V6-V2)+nat(V2)*6*nat(V1+V6-V2)+nat(-V6+V2)*2+nat(-V6+V2+1)*3+nat(V6-V2)*48+nat(V1+V6-V2)*36,nat(V1)*66+2+nat(V1)*9*nat(V1)+nat(V1)*9*nat(V2)+nat(V1)*2*nat(V1-V2)+nat(V1)*4*nat(V1+V6-V2)+nat(V6)*2+nat(V2)*26+nat(V2)*2*nat(-V2)+nat(V2)*2*nat(V1-V2)+nat(V2)*8*nat(V6-V2)+nat(V2)*4*nat(V1+V6-V2)+nat(-V2)*16+nat(V1+V6)*2+nat(-V6+V2)+nat(-V6+V2+1)*3+nat(V1-V2)*12+nat(V6-V2)*64+nat(V1+V6-V2)*24+(nat(V1)*3*nat(V1)+nat(V1)*18+nat(V6)*64)])+(nat(V1)*nat(V1)+nat(V1)*6),nat(V1)*3*nat(V2)+1+nat(V1)*2*nat(V1-V2)+nat(V2)*6+nat(V2)*2*nat(V1-V2)+nat(V1-V2)*12])])])])+10 
Asymptotic class: n^2 
* Total analysis performed in 1395 ms.


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

(10)
BOUNDS(1, n^2)

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

(11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(12)
Obligation:
Analyzing the following TRS for decreasing loops:

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:

   cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z)
   cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z)
   cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z)
   cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z)
   cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z)
   gr(0, x) -> false
   gr(s(x), 0) -> true
   gr(s(x), s(y)) -> gr(x, y)
   add(0, x) -> x
   add(s(x), y) -> s(add(x, y))
   p(0) -> 0
   p(s(x)) -> x

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

(13) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

add(s(x), y) ->^+ s(add(x, y))

gives rise to a decreasing loop by considering the right hand sides subterm at position [0].

The pumping substitution is [x / s(x)].

The result substitution is [ ].




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

(14)
Complex Obligation (BEST)

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

(15)
Obligation:
Proved the lower bound n^1 for the following 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:

   cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z)
   cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z)
   cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z)
   cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z)
   cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z)
   gr(0, x) -> false
   gr(s(x), 0) -> true
   gr(s(x), s(y)) -> gr(x, y)
   add(0, x) -> x
   add(s(x), y) -> s(add(x, y))
   p(0) -> 0
   p(s(x)) -> x

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

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

(17)
BOUNDS(n^1, INF)

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

(18)
Obligation:
Analyzing the following TRS for decreasing loops:

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:

   cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z)
   cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z)
   cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z)
   cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z)
   cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z)
   gr(0, x) -> false
   gr(s(x), 0) -> true
   gr(s(x), s(y)) -> gr(x, y)
   add(0, x) -> x
   add(s(x), y) -> s(add(x, y))
   p(0) -> 0
   p(s(x)) -> x

S is empty.
Rewrite Strategy: INNERMOST