/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


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


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


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

(0) CpxTRS
(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 12 ms]
(2) CpxTRS
    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxWeightedTrs
    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxTypedWeightedTrs
    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
    (8) CpxTypedWeightedCompleteTrs
    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (10) CpxRNTS
    (11) CompleteCoflocoProof [FINISHED, 1193 ms]
    (12) BOUNDS(1, n^2)
(13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(14) TRS for Loop Detection
    (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (16) BEST
        (17) proven lower bound
            (18) LowerBoundPropagationProof [FINISHED, 0 ms]
            (19) BOUNDS(n^1, INF)
        (20) TRS for Loop Detection


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

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


The TRS R consists of the following rules:

   le(0, y, z) -> greater(y, z)
   le(s(x), 0, z) -> false
   le(s(x), s(y), 0) -> false
   le(s(x), s(y), s(z)) -> le(x, y, z)
   greater(x, 0) -> first
   greater(0, s(y)) -> second
   greater(s(x), s(y)) -> greater(x, y)
   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   triple(x) -> if(le(x, x, double(x)), x, 0, 0)
   if(false, x, y, z) -> true
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z))
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z)

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

(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

The duplicating contexts are:
triple([])
if(first, [], y, z)
if(first, x, [], z)
if(first, x, y, [])
if(second, [], y, z)
if(second, x, [], z)
if(second, x, y, [])


The defined contexts are:
if([], s(x1), x2, s(x3))
if([], s(x1), s(x2), x3)
if([], x1, 0, 0)
le(x0, x1, [])
greater(x0, [])


[] just represents basic- or constructor-terms in the following defined contexts:
if([], s(x1), x2, s(x3))
if([], s(x1), s(x2), x3)


As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   le(0, y, z) -> greater(y, z)
   le(s(x), 0, z) -> false
   le(s(x), s(y), 0) -> false
   le(s(x), s(y), s(z)) -> le(x, y, z)
   greater(x, 0) -> first
   greater(0, s(y)) -> second
   greater(s(x), s(y)) -> greater(x, y)
   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   triple(x) -> if(le(x, x, double(x)), x, 0, 0)
   if(false, x, y, z) -> true
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z))
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z)

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

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

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

   le(0, y, z) -> greater(y, z) [1]
   le(s(x), 0, z) -> false [1]
   le(s(x), s(y), 0) -> false [1]
   le(s(x), s(y), s(z)) -> le(x, y, z) [1]
   greater(x, 0) -> first [1]
   greater(0, s(y)) -> second [1]
   greater(s(x), s(y)) -> greater(x, y) [1]
   double(0) -> 0 [1]
   double(s(x)) -> s(s(double(x))) [1]
   triple(x) -> if(le(x, x, double(x)), x, 0, 0) [1]
   if(false, x, y, z) -> true [1]
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z)) [1]
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z) [1]

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

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

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

   le(0, y, z) -> greater(y, z) [1]
   le(s(x), 0, z) -> false [1]
   le(s(x), s(y), 0) -> false [1]
   le(s(x), s(y), s(z)) -> le(x, y, z) [1]
   greater(x, 0) -> first [1]
   greater(0, s(y)) -> second [1]
   greater(s(x), s(y)) -> greater(x, y) [1]
   double(0) -> 0 [1]
   double(s(x)) -> s(s(double(x))) [1]
   triple(x) -> if(le(x, x, double(x)), x, 0, 0) [1]
   if(false, x, y, z) -> true [1]
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z)) [1]
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z) [1]

The TRS has the following type information:
le :: 0:s -> 0:s -> 0:s -> false:first:second
0 :: 0:s
greater :: 0:s -> 0:s -> false:first:second
s :: 0:s -> 0:s
false :: false:first:second
first :: false:first:second
second :: false:first:second
double :: 0:s -> 0:s
triple :: 0:s -> true
if :: false:first:second -> 0:s -> 0:s -> 0:s -> true
true :: true

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

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

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

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

   le(0, y, z) -> greater(y, z) [1]
   le(s(x), 0, z) -> false [1]
   le(s(x), s(y), 0) -> false [1]
   le(s(x), s(y), s(z)) -> le(x, y, z) [1]
   greater(x, 0) -> first [1]
   greater(0, s(y)) -> second [1]
   greater(s(x), s(y)) -> greater(x, y) [1]
   double(0) -> 0 [1]
   double(s(x)) -> s(s(double(x))) [1]
   triple(x) -> if(le(x, x, double(x)), x, 0, 0) [1]
   if(false, x, y, z) -> true [1]
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z)) [1]
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z) [1]

The TRS has the following type information:
le :: 0:s -> 0:s -> 0:s -> false:first:second
0 :: 0:s
greater :: 0:s -> 0:s -> false:first:second
s :: 0:s -> 0:s
false :: false:first:second
first :: false:first:second
second :: false:first:second
double :: 0:s -> 0:s
triple :: 0:s -> true
if :: false:first:second -> 0:s -> 0:s -> 0:s -> true
true :: true

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

(9) 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
   false => 0
   first => 1
   second => 2
   true => 0

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

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

   double(z') -{ 1 }-> 0 :|: z' = 0
   double(z') -{ 1 }-> 1 + (1 + double(x)) :|: z' = 1 + x, x >= 0
   greater(z', z'') -{ 1 }-> greater(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y
   greater(z', z'') -{ 1 }-> 2 :|: y >= 0, z'' = 1 + y, z' = 0
   greater(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = x, x >= 0
   if(z', z'', z1, z2) -{ 1 }-> if(le(1 + x, y, 1 + z), 1 + x, y, 1 + z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1
   if(z', z'', z1, z2) -{ 1 }-> if(le(1 + x, 1 + y, z), 1 + x, 1 + y, z) :|: z1 = y, z >= 0, z' = 2, z2 = z, x >= 0, y >= 0, z'' = x
   if(z', z'', z1, z2) -{ 1 }-> 0 :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 0
   le(z', z'', z1) -{ 1 }-> le(x, y, z) :|: z' = 1 + x, z >= 0, x >= 0, y >= 0, z'' = 1 + y, z1 = 1 + z
   le(z', z'', z1) -{ 1 }-> greater(y, z) :|: z1 = z, z >= 0, z'' = y, y >= 0, z' = 0
   le(z', z'', z1) -{ 1 }-> 0 :|: z'' = 0, z' = 1 + x, z1 = z, z >= 0, x >= 0
   le(z', z'', z1) -{ 1 }-> 0 :|: z' = 1 + x, z1 = 0, x >= 0, y >= 0, z'' = 1 + y
   triple(z') -{ 1 }-> if(le(x, x, double(x)), x, 0, 0) :|: z' = x, x >= 0

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V, V1, V4, V21),0,[le(V, V1, V4, Out)],[V >= 0,V1 >= 0,V4 >= 0]).
eq(start(V, V1, V4, V21),0,[greater(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1, V4, V21),0,[double(V, Out)],[V >= 0]).
eq(start(V, V1, V4, V21),0,[triple(V, Out)],[V >= 0]).
eq(start(V, V1, V4, V21),0,[if(V, V1, V4, V21, Out)],[V >= 0,V1 >= 0,V4 >= 0,V21 >= 0]).
eq(le(V, V1, V4, Out),1,[greater(V2, V3, Ret)],[Out = Ret,V4 = V3,V3 >= 0,V1 = V2,V2 >= 0,V = 0]).
eq(le(V, V1, V4, Out),1,[],[Out = 0,V1 = 0,V = 1 + V6,V4 = V5,V5 >= 0,V6 >= 0]).
eq(le(V, V1, V4, Out),1,[],[Out = 0,V = 1 + V7,V4 = 0,V7 >= 0,V8 >= 0,V1 = 1 + V8]).
eq(le(V, V1, V4, Out),1,[le(V10, V9, V11, Ret1)],[Out = Ret1,V = 1 + V10,V11 >= 0,V10 >= 0,V9 >= 0,V1 = 1 + V9,V4 = 1 + V11]).
eq(greater(V, V1, Out),1,[],[Out = 1,V1 = 0,V = V12,V12 >= 0]).
eq(greater(V, V1, Out),1,[],[Out = 2,V13 >= 0,V1 = 1 + V13,V = 0]).
eq(greater(V, V1, Out),1,[greater(V15, V14, Ret2)],[Out = Ret2,V = 1 + V15,V15 >= 0,V14 >= 0,V1 = 1 + V14]).
eq(double(V, Out),1,[],[Out = 0,V = 0]).
eq(double(V, Out),1,[double(V16, Ret11)],[Out = 2 + Ret11,V = 1 + V16,V16 >= 0]).
eq(triple(V, Out),1,[double(V17, Ret02),le(V17, V17, Ret02, Ret0),if(Ret0, V17, 0, 0, Ret3)],[Out = Ret3,V = V17,V17 >= 0]).
eq(if(V, V1, V4, V21, Out),1,[],[Out = 0,V4 = V19,V18 >= 0,V21 = V18,V20 >= 0,V19 >= 0,V1 = V20,V = 0]).
eq(if(V, V1, V4, V21, Out),1,[le(1 + V23, V24, 1 + V22, Ret01),if(Ret01, 1 + V23, V24, 1 + V22, Ret4)],[Out = Ret4,V4 = V24,V22 >= 0,V21 = V22,V23 >= 0,V24 >= 0,V1 = V23,V = 1]).
eq(if(V, V1, V4, V21, Out),1,[le(1 + V27, 1 + V26, V25, Ret03),if(Ret03, 1 + V27, 1 + V26, V25, Ret5)],[Out = Ret5,V4 = V26,V25 >= 0,V = 2,V21 = V25,V27 >= 0,V26 >= 0,V1 = V27]).
input_output_vars(le(V,V1,V4,Out),[V,V1,V4],[Out]).
input_output_vars(greater(V,V1,Out),[V,V1],[Out]).
input_output_vars(double(V,Out),[V],[Out]).
input_output_vars(triple(V,Out),[V],[Out]).
input_output_vars(if(V,V1,V4,V21,Out),[V,V1,V4,V21],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [double/2]
1. recursive  : [greater/3]
2. recursive  : [le/4]
3. recursive  : [if/5]
4. non_recursive  : [triple/2]
5. non_recursive  : [start/4]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into double/2
1. SCC is partially evaluated into greater/3
2. SCC is partially evaluated into le/4
3. SCC is partially evaluated into if/5
4. SCC is partially evaluated into triple/2
5. SCC is partially evaluated into start/4

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

### Specialization of cost equations double/2 
* CE 14 is refined into CE [19] 
* CE 13 is refined into CE [20] 


### Cost equations --> "Loop" of double/2 
* CEs [20] --> Loop 15 
* CEs [19] --> Loop 16 

### Ranking functions of CR double(V,Out) 
* RF of phase [16]: [V]

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


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


### Cost equations --> "Loop" of greater/3 
* CEs [22] --> Loop 17 
* CEs [23] --> Loop 18 
* CEs [21] --> Loop 19 

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

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


### Specialization of cost equations le/4 
* CE 9 is refined into CE [24] 
* CE 8 is refined into CE [25] 
* CE 7 is refined into CE [26] 
* CE 6 is refined into CE [27,28,29,30] 


### Cost equations --> "Loop" of le/4 
* CEs [25] --> Loop 20 
* CEs [26] --> Loop 21 
* CEs [30] --> Loop 22 
* CEs [29] --> Loop 23 
* CEs [28] --> Loop 24 
* CEs [27] --> Loop 25 
* CEs [24] --> Loop 26 

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

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


### Specialization of cost equations if/5 
* CE 18 is refined into CE [31,32,33,34,35,36,37] 
* CE 17 is refined into CE [38,39,40,41,42,43,44] 
* CE 16 is refined into CE [45] 


### Cost equations --> "Loop" of if/5 
* CEs [45] --> Loop 27 
* CEs [37] --> Loop 28 
* CEs [36] --> Loop 29 
* CEs [35] --> Loop 30 
* CEs [34] --> Loop 31 
* CEs [32] --> Loop 32 
* CEs [33] --> Loop 33 
* CEs [31] --> Loop 34 
* CEs [44] --> Loop 35 
* CEs [43] --> Loop 36 
* CEs [42] --> Loop 37 
* CEs [41] --> Loop 38 
* CEs [40] --> Loop 39 
* CEs [39] --> Loop 40 
* CEs [38] --> Loop 41 

### Ranking functions of CR if(V,V1,V4,V21,Out) 
* RF of phase [28,30,35,37]: [-2*V1+V4+V21-2]
* RF of phase [29]: [-V1+V21-1,-V4+V21-1]
* RF of phase [38]: [-V1+V4,V4-V21]

#### Partial ranking functions of CR if(V,V1,V4,V21,Out) 
* Partial RF of phase [28,30,35,37]:
  - RF of loop [28:1]:
    -V1+V21-2
    -V4+V21-1 depends on loops [35:1,37:1] 
  - RF of loop [30:1]:
    V-1 depends on loops [35:1] 
    -V1+V21-1
  - RF of loop [35:1]:
    -V+2 depends on loops [30:1] 
  - RF of loop [35:1,37:1]:
    -V1+V4-1
  - RF of loop [37:1]:
    V4-V21 depends on loops [28:1,30:1] 
* Partial RF of phase [29]:
  - RF of loop [29:1]:
    -V1+V21-1
    -V4+V21-1
* Partial RF of phase [38]:
  - RF of loop [38:1]:
    -V1+V4
    V4-V21


### Specialization of cost equations triple/2 
* CE 15 is refined into CE [46,47] 


### Cost equations --> "Loop" of triple/2 
* CEs [47] --> Loop 42 
* CEs [46] --> Loop 43 

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

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


### Specialization of cost equations start/4 
* CE 1 is refined into CE [48,49,50,51,52,53,54,55,56,57,58,59] 
* CE 2 is refined into CE [60,61,62,63] 
* CE 3 is refined into CE [64,65] 
* CE 4 is refined into CE [66,67] 
* CE 5 is refined into CE [68,69,70,71,72,73,74,75,76,77,78,79,80,81] 


### Cost equations --> "Loop" of start/4 
* CEs [81] --> Loop 44 
* CEs [56] --> Loop 45 
* CEs [58] --> Loop 46 
* CEs [53] --> Loop 47 
* CEs [52,61] --> Loop 48 
* CEs [80] --> Loop 49 
* CEs [79] --> Loop 50 
* CEs [78] --> Loop 51 
* CEs [76] --> Loop 52 
* CEs [77] --> Loop 53 
* CEs [75] --> Loop 54 
* CEs [74] --> Loop 55 
* CEs [73] --> Loop 56 
* CEs [72] --> Loop 57 
* CEs [70] --> Loop 58 
* CEs [71] --> Loop 59 
* CEs [54,55,57,59,62,63,65,67,69] --> Loop 60 
* CEs [48,49,50,51,60,64,66,68] --> Loop 61 

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

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


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

#### Cost of chains of double(V,Out):
* Chain [[16],15]: 1*it(16)+1
  Such that:it(16) =< Out/2

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

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


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

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

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

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

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

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


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

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

* Chain [[26],24]: 1*it(26)+2
  Such that:it(26) =< V

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

* Chain [[26],23]: 1*it(26)+1*s(1)+2
  Such that:s(1) =< -V+V4
it(26) =< V

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

* Chain [[26],22]: 1*it(26)+1*s(2)+2
  Such that:s(2) =< -V+V1
it(26) =< V

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

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

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

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

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

* Chain [25]: 2
  with precondition: [V=0,V1=0,Out=2,V4>=1] 

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

* Chain [23]: 1*s(1)+2
  Such that:s(1) =< V4

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

* Chain [22]: 1*s(2)+2
  Such that:s(2) =< V1

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

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

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


#### Cost of chains of if(V,V1,V4,V21,Out):
* Chain [[38],40,27]: 3*it(38)+1*s(3)+1*s(6)+3
  Such that:it(38) =< V4-V21
aux(2) =< V4
s(3) =< aux(2)
s(6) =< it(38)*aux(2)

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

* Chain [[29],31,40,27]: 3*it(29)+2*s(3)+1*s(10)+6
  Such that:it(29) =< -V1+V21
aux(5) =< V21
s(3) =< aux(5)
s(10) =< it(29)*aux(5)

  with precondition: [V=2,Out=0,V1=V4,V1>=0,V21>=V1+2] 

* Chain [[28,30,35,37],36,31,40,27]: 6*it(28)+6*it(35)+3*s(3)+1*s(28)+1*s(29)+1*s(30)+1*s(31)+1*s(32)+2*s(33)+1*s(34)+9
  Such that:aux(28) =< -2*V1+V4+V21
aux(29) =< -V1+V4
aux(30) =< -V1+V4+V21
aux(31) =< -V1+V21
s(3) =< aux(30)
it(28) =< aux(28)
it(35) =< aux(28)
it(35) =< aux(29)
it(28) =< aux(31)
aux(13) =< aux(30)
aux(20) =< aux(31)+1
aux(16) =< aux(29)-1
s(33) =< it(35)*aux(13)
s(34) =< it(35)*aux(20)
s(32) =< it(35)*aux(16)
s(31) =< it(28)*aux(13)
s(30) =< it(28)*aux(31)
s(29) =< it(28)*aux(30)
s(28) =< it(28)*aux(29)

  with precondition: [Out=0,2>=V,V>=1,V1>=0,V21>=V+V1,V+V4>=V1+3] 

* Chain [41,27]: 3
  with precondition: [V=1,V4=0,Out=0,V1>=0,V21>=0] 

* Chain [40,27]: 1*s(3)+3
  Such that:s(3) =< V4

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

* Chain [39,27]: 1*s(36)+3
  Such that:s(36) =< V21+1

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

* Chain [36,[29],31,40,27]: 3*it(29)+2*s(3)+1*s(10)+1*s(11)+9
  Such that:it(29) =< -V1+V21
s(11) =< V1+1
aux(5) =< V21+1
s(3) =< aux(5)
s(10) =< it(29)*aux(5)

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

* Chain [36,31,40,27]: 2*s(3)+1*s(11)+9
  Such that:s(11) =< V21
aux(3) =< V21+1
s(3) =< aux(3)

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

* Chain [34,27]: 3
  with precondition: [V=2,V21=0,Out=0,V1>=0,V4>=0] 

* Chain [33,27]: 1*s(37)+3
  Such that:s(37) =< V21

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

* Chain [32,27]: 1*s(38)+3
  Such that:s(38) =< V4+1

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

* Chain [31,[38],40,27]: 3*it(38)+1*s(3)+1*s(6)+1*s(7)+6
  Such that:aux(2) =< V4+1
it(38) =< V4-V21+1
s(7) =< V21
s(3) =< aux(2)
s(6) =< it(38)*aux(2)

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

* Chain [31,40,27]: 2*s(3)+6
  Such that:aux(3) =< V21
s(3) =< aux(3)

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

* Chain [27]: 1
  with precondition: [V=0,Out=0,V1>=0,V4>=0,V21>=0] 


#### Cost of chains of triple(V,Out):
* Chain [43]: 7
  with precondition: [V=0,Out=0] 

* Chain [42]: 2*s(39)+7
  Such that:aux(32) =< V
s(39) =< aux(32)

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


#### Cost of chains of start(V,V1,V4,V21):
* Chain [61]: 1*s(41)+1*s(42)+7
  Such that:s(42) =< V1
s(41) =< V4

  with precondition: [V=0] 

* Chain [60]: 2*s(43)+1*s(44)+1*s(45)+6*s(46)+1*s(47)+7
  Such that:s(47) =< -V+V1
s(45) =< -V+V4
s(44) =< V4
aux(33) =< V
aux(34) =< V1
s(46) =< aux(33)
s(43) =< aux(34)

  with precondition: [V>=1] 

* Chain [59]: 1*s(54)+2*s(56)+9
  Such that:s(54) =< V21
s(55) =< V21+1
s(56) =< s(55)

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

* Chain [58]: 3*s(57)+1*s(58)+2*s(60)+1*s(61)+9
  Such that:s(57) =< -V4+V21+1
s(58) =< V4
s(59) =< V21+1
s(60) =< s(59)
s(61) =< s(57)*s(59)

  with precondition: [V=1,V1+1=V4,V1>=0,V21>=V1+2] 

* Chain [57]: 3*s(62)+1*s(64)+1*s(65)+3
  Such that:s(63) =< V4
s(62) =< V4-V21
s(64) =< s(63)
s(65) =< s(62)*s(63)

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

* Chain [56]: 1*s(66)+3
  Such that:s(66) =< V4

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

* Chain [55]: 1*s(67)+3
  Such that:s(67) =< V21+1

  with precondition: [V=1,V21>=0,V1>=V21+1,V4>=V21+2] 

* Chain [54]: 3
  with precondition: [V=2,V21=0,V1>=0,V4>=0] 

* Chain [53]: 3*s(69)+1*s(70)+1*s(71)+1*s(72)+6
  Such that:s(68) =< V4+1
s(69) =< V4-V21+1
s(70) =< V21
s(71) =< s(68)
s(72) =< s(69)*s(68)

  with precondition: [V=2,V1+1=V21,V1>=0,V4>=V1+1] 

* Chain [52]: 2*s(74)+6
  Such that:s(73) =< V21
s(74) =< s(73)

  with precondition: [V=2,V1=V4,V1+1=V21,V1>=0] 

* Chain [51]: 3*s(75)+2*s(77)+1*s(78)+6
  Such that:s(75) =< -V1+V21
s(76) =< V21
s(77) =< s(76)
s(78) =< s(75)*s(76)

  with precondition: [V=2,V1=V4,V1>=0,V21>=V1+2] 

* Chain [50]: 1*s(79)+3
  Such that:s(79) =< V4+1

  with precondition: [V=2,V4>=0,V1>=V4+1,V21>=V4+1] 

* Chain [49]: 1*s(80)+3
  Such that:s(80) =< V21

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

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

* Chain [47]: 1
  with precondition: [V4=0,V>=1,V1>=1] 

* Chain [46]: 1*s(81)+2
  Such that:s(81) =< V1

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

* Chain [45]: 1*s(82)+2
  Such that:s(82) =< V4

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

* Chain [44]: 3*s(87)+6*s(88)+6*s(89)+2*s(93)+1*s(94)+1*s(95)+1*s(96)+1*s(97)+1*s(98)+1*s(99)+9
  Such that:s(83) =< -2*V1+V4+V21
s(84) =< -V1+V4
s(85) =< -V1+V4+V21
s(86) =< -V1+V21
s(87) =< s(85)
s(88) =< s(83)
s(89) =< s(83)
s(89) =< s(84)
s(88) =< s(86)
s(90) =< s(85)
s(91) =< s(86)+1
s(92) =< s(84)-1
s(93) =< s(89)*s(90)
s(94) =< s(89)*s(91)
s(95) =< s(89)*s(92)
s(96) =< s(88)*s(90)
s(97) =< s(88)*s(86)
s(98) =< s(88)*s(85)
s(99) =< s(88)*s(84)

  with precondition: [2>=V,V>=1,V1>=0,V21>=V+V1,V+V4>=V1+3] 


Closed-form bounds of start(V,V1,V4,V21): 
-------------------------------------
* Chain [61] with precondition: [V=0] 
    - Upper bound: nat(V1)+7+nat(V4) 
    - Complexity: n 
* Chain [60] with precondition: [V>=1] 
    - Upper bound: 6*V+7+nat(V1)*2+nat(V4)+nat(-V+V1)+nat(-V+V4) 
    - Complexity: n 
* Chain [59] with precondition: [V=1,V1+1=V4,V1+1=V21,V1>=0] 
    - Upper bound: 3*V21+11 
    - Complexity: n 
* Chain [58] with precondition: [V=1,V1+1=V4,V1>=0,V21>=V1+2] 
    - Upper bound: V4+2*V21+11+(-V4+V21+1)*(V21+1)+(-3*V4+3*V21+3) 
    - Complexity: n^2 
* Chain [57] with precondition: [V=1,V1=V21,V1>=0,V4>=V1+1] 
    - Upper bound: 3*V4-3*V21+(V4+3+(V4-V21)*V4) 
    - Complexity: n^2 
* Chain [56] with precondition: [V=1,V4>=1,V1>=V4,V21+1>=V4] 
    - Upper bound: V4+3 
    - Complexity: n 
* Chain [55] with precondition: [V=1,V21>=0,V1>=V21+1,V4>=V21+2] 
    - Upper bound: V21+4 
    - Complexity: n 
* Chain [54] with precondition: [V=2,V21=0,V1>=0,V4>=0] 
    - Upper bound: 3 
    - Complexity: constant 
* Chain [53] with precondition: [V=2,V1+1=V21,V1>=0,V4>=V1+1] 
    - Upper bound: 3*V4-3*V21+3+(V4+V21+7+(V4-V21+1)*(V4+1)) 
    - Complexity: n^2 
* Chain [52] with precondition: [V=2,V1=V4,V1+1=V21,V1>=0] 
    - Upper bound: 2*V21+6 
    - Complexity: n 
* Chain [51] with precondition: [V=2,V1=V4,V1>=0,V21>=V1+2] 
    - Upper bound: 2*V21+6+(-V1+V21)*V21+(-3*V1+3*V21) 
    - Complexity: n^2 
* Chain [50] with precondition: [V=2,V4>=0,V1>=V4+1,V21>=V4+1] 
    - Upper bound: V4+4 
    - Complexity: n 
* Chain [49] with precondition: [V=2,V21>=1,V1>=V21,V4>=V21] 
    - Upper bound: V21+3 
    - Complexity: n 
* Chain [48] with precondition: [V1=0,V>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [47] with precondition: [V4=0,V>=1,V1>=1] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [46] with precondition: [V=V1,V>=1,V4>=V+1] 
    - Upper bound: V1+2 
    - Complexity: n 
* Chain [45] with precondition: [V=V4,V>=1,V1>=V] 
    - Upper bound: V4+2 
    - Complexity: n 
* Chain [44] with precondition: [2>=V,V>=1,V1>=0,V21>=V+V1,V+V4>=V1+3] 
    - Upper bound: (-V1+V4-1)*(-2*V1+V4+V21)+9+(-2*V1+V4+V21)*(-V1+V4)+(-2*V1+V4+V21)*(-2*V1+2*V21)+(-3*V1+3*V4+3*V21)+(-2*V1+V4+V21)*(-4*V1+4*V4+4*V21)+(-26*V1+13*V4+13*V21) 
    - Complexity: n^2 

### Maximum cost of start(V,V1,V4,V21): max([max([max([2,nat(V1)+1,nat(V4+1)+2,nat(V21+1)+2,nat(-2*V1+V4+V21)*nat(nat(-V1+V4)+ -1)+8+nat(-2*V1+V4+V21)*nat(-V1+V4)+nat(-V1+V21)*2*nat(-2*V1+V4+V21)+nat(-V1+V4+V21)*3+nat(-V1+V4+V21)*4*nat(-2*V1+V4+V21)+nat(-2*V1+V4+V21)*13]),nat(V21)+2+max([max([nat(V21+1)*2+6,nat(V4+1)+3+nat(V4-V21+1)*nat(V4+1)+nat(V4-V21+1)*3]),nat(-V1+V21)*nat(V21)+nat(-V1+V21)*3+(nat(V21)+3)])]),nat(V4)+1+max([max([1,nat(V4-V21)*nat(V4)+1+nat(V4-V21)*3,nat(V21+1)*2+7+nat(-V4+V21+1)*nat(V21+1)+nat(-V4+V21+1)*3]),6*V+nat(V1)+nat(-V+V1)+nat(-V+V4)+(nat(V1)+5)])])+1 
Asymptotic class: n^2 
* Total analysis performed in 1053 ms.


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

(12)
BOUNDS(1, n^2)

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

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

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

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


The TRS R consists of the following rules:

   le(0, y, z) -> greater(y, z)
   le(s(x), 0, z) -> false
   le(s(x), s(y), 0) -> false
   le(s(x), s(y), s(z)) -> le(x, y, z)
   greater(x, 0) -> first
   greater(0, s(y)) -> second
   greater(s(x), s(y)) -> greater(x, y)
   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   triple(x) -> if(le(x, x, double(x)), x, 0, 0)
   if(false, x, y, z) -> true
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z))
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z)

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

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

The rewrite sequence

double(s(x)) ->^+ s(s(double(x)))

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

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

The result substitution is [ ].




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

(16)
Complex Obligation (BEST)

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

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

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


The TRS R consists of the following rules:

   le(0, y, z) -> greater(y, z)
   le(s(x), 0, z) -> false
   le(s(x), s(y), 0) -> false
   le(s(x), s(y), s(z)) -> le(x, y, z)
   greater(x, 0) -> first
   greater(0, s(y)) -> second
   greater(s(x), s(y)) -> greater(x, y)
   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   triple(x) -> if(le(x, x, double(x)), x, 0, 0)
   if(false, x, y, z) -> true
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z))
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z)

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

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

(19)
BOUNDS(n^1, INF)

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

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

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


The TRS R consists of the following rules:

   le(0, y, z) -> greater(y, z)
   le(s(x), 0, z) -> false
   le(s(x), s(y), 0) -> false
   le(s(x), s(y), s(z)) -> le(x, y, z)
   greater(x, 0) -> first
   greater(0, s(y)) -> second
   greater(s(x), s(y)) -> greater(x, y)
   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   triple(x) -> if(le(x, x, double(x)), x, 0, 0)
   if(false, x, y, z) -> true
   if(first, x, y, z) -> if(le(s(x), y, s(z)), s(x), y, s(z))
   if(second, x, y, z) -> if(le(s(x), s(y), z), s(x), s(y), z)

S is empty.
Rewrite Strategy: FULL