/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), 0 ms]
(2) CpxTRS
    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxWeightedTrs
    (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxWeightedTrs
    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxTypedWeightedTrs
    (9) CompletionProof [UPPER BOUND(ID), 0 ms]
    (10) CpxTypedWeightedCompleteTrs
    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (12) CpxRNTS
    (13) CompleteCoflocoProof [FINISHED, 640 ms]
    (14) BOUNDS(1, n^2)
(15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(16) TRS for Loop Detection
    (17) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (18) BEST
        (19) proven lower bound
            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
            (21) BOUNDS(n^1, INF)
        (22) 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:

   leq(0, y) -> true
   leq(s(x), 0) -> false
   leq(s(x), s(y)) -> leq(x, y)
   if(true, x, y) -> x
   if(false, x, y) -> y
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, y)
   mod(0, y) -> 0
   mod(s(x), 0) -> 0
   mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x))

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

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

The duplicating contexts are:
mod(s(x), s([]))
mod(s([]), s(y))


The defined contexts are:
if([], x1, s(x2))
if(x0, [], s(x2))
mod([], s(x1))
leq(x0, [])
-(s([]), s(x1))
if(x0, x1, s([]))
-([], x1)


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


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:

   leq(0, y) -> true
   leq(s(x), 0) -> false
   leq(s(x), s(y)) -> leq(x, y)
   if(true, x, y) -> x
   if(false, x, y) -> y
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, y)
   mod(0, y) -> 0
   mod(s(x), 0) -> 0
   mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x))

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:

   leq(0, y) -> true [1]
   leq(s(x), 0) -> false [1]
   leq(s(x), s(y)) -> leq(x, y) [1]
   if(true, x, y) -> x [1]
   if(false, x, y) -> y [1]
   -(x, 0) -> x [1]
   -(s(x), s(y)) -> -(x, y) [1]
   mod(0, y) -> 0 [1]
   mod(s(x), 0) -> 0 [1]
   mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) [1]

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

(5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
Renamed defined symbols to avoid conflicts with arithmetic symbols:

- => minus

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

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


The TRS R consists of the following rules:

   leq(0, y) -> true [1]
   leq(s(x), 0) -> false [1]
   leq(s(x), s(y)) -> leq(x, y) [1]
   if(true, x, y) -> x [1]
   if(false, x, y) -> y [1]
   minus(x, 0) -> x [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   mod(0, y) -> 0 [1]
   mod(s(x), 0) -> 0 [1]
   mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1]

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

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

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

   leq(0, y) -> true [1]
   leq(s(x), 0) -> false [1]
   leq(s(x), s(y)) -> leq(x, y) [1]
   if(true, x, y) -> x [1]
   if(false, x, y) -> y [1]
   minus(x, 0) -> x [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   mod(0, y) -> 0 [1]
   mod(s(x), 0) -> 0 [1]
   mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1]

The TRS has the following type information:
leq :: 0:s -> 0:s -> true:false
0 :: 0:s
true :: true:false
s :: 0:s -> 0:s
false :: true:false
if :: true:false -> 0:s -> 0:s -> 0:s
minus :: 0:s -> 0:s -> 0:s
mod :: 0:s -> 0:s -> 0:s

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

(9) CompletionProof (UPPER BOUND(ID))
The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:

   minus(v0, v1) -> null_minus [0]
   leq(v0, v1) -> null_leq [0]
   mod(v0, v1) -> null_mod [0]
   if(v0, v1, v2) -> null_if [0]

And the following fresh constants:    null_minus, null_leq, null_mod, null_if

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

(10)
Obligation:
Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   leq(0, y) -> true [1]
   leq(s(x), 0) -> false [1]
   leq(s(x), s(y)) -> leq(x, y) [1]
   if(true, x, y) -> x [1]
   if(false, x, y) -> y [1]
   minus(x, 0) -> x [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   mod(0, y) -> 0 [1]
   mod(s(x), 0) -> 0 [1]
   mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1]
   minus(v0, v1) -> null_minus [0]
   leq(v0, v1) -> null_leq [0]
   mod(v0, v1) -> null_mod [0]
   if(v0, v1, v2) -> null_if [0]

The TRS has the following type information:
leq :: 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if -> true:false:null_leq
0 :: 0:s:null_minus:null_mod:null_if
true :: true:false:null_leq
s :: 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if
false :: true:false:null_leq
if :: true:false:null_leq -> 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if
minus :: 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if
mod :: 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if -> 0:s:null_minus:null_mod:null_if
null_minus :: 0:s:null_minus:null_mod:null_if
null_leq :: true:false:null_leq
null_mod :: 0:s:null_minus:null_mod:null_if
null_if :: 0:s:null_minus:null_mod:null_if

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

(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   0 => 0
   true => 2
   false => 1
   null_minus => 0
   null_leq => 0
   null_mod => 0
   null_if => 0

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

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

   if(z, z', z'') -{ 1 }-> x :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0
   if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
   if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   leq(z, z') -{ 1 }-> leq(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   leq(z, z') -{ 1 }-> 2 :|: y >= 0, z = 0, z' = y
   leq(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0
   leq(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   mod(z, z') -{ 1 }-> if(leq(y, x), mod(minus(1 + x, 1 + y), 1 + y), 1 + x) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   mod(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y
   mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0
   mod(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V1, V, V8),0,[leq(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V8),0,[if(V1, V, V8, Out)],[V1 >= 0,V >= 0,V8 >= 0]).
eq(start(V1, V, V8),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V8),0,[mod(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(leq(V1, V, Out),1,[],[Out = 2,V2 >= 0,V1 = 0,V = V2]).
eq(leq(V1, V, Out),1,[],[Out = 1,V3 >= 0,V1 = 1 + V3,V = 0]).
eq(leq(V1, V, Out),1,[leq(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]).
eq(if(V1, V, V8, Out),1,[],[Out = V7,V1 = 2,V = V7,V8 = V6,V7 >= 0,V6 >= 0]).
eq(if(V1, V, V8, Out),1,[],[Out = V10,V = V9,V8 = V10,V1 = 1,V9 >= 0,V10 >= 0]).
eq(minus(V1, V, Out),1,[],[Out = V11,V11 >= 0,V1 = V11,V = 0]).
eq(minus(V1, V, Out),1,[minus(V13, V12, Ret1)],[Out = Ret1,V = 1 + V12,V13 >= 0,V12 >= 0,V1 = 1 + V13]).
eq(mod(V1, V, Out),1,[],[Out = 0,V14 >= 0,V1 = 0,V = V14]).
eq(mod(V1, V, Out),1,[],[Out = 0,V15 >= 0,V1 = 1 + V15,V = 0]).
eq(mod(V1, V, Out),1,[leq(V17, V16, Ret0),minus(1 + V16, 1 + V17, Ret10),mod(Ret10, 1 + V17, Ret11),if(Ret0, Ret11, 1 + V16, Ret2)],[Out = Ret2,V = 1 + V17,V16 >= 0,V17 >= 0,V1 = 1 + V16]).
eq(minus(V1, V, Out),0,[],[Out = 0,V19 >= 0,V18 >= 0,V1 = V19,V = V18]).
eq(leq(V1, V, Out),0,[],[Out = 0,V21 >= 0,V20 >= 0,V1 = V21,V = V20]).
eq(mod(V1, V, Out),0,[],[Out = 0,V23 >= 0,V22 >= 0,V1 = V23,V = V22]).
eq(if(V1, V, V8, Out),0,[],[Out = 0,V24 >= 0,V8 = V26,V25 >= 0,V1 = V24,V = V25,V26 >= 0]).
input_output_vars(leq(V1,V,Out),[V1,V],[Out]).
input_output_vars(if(V1,V,V8,Out),[V1,V,V8],[Out]).
input_output_vars(minus(V1,V,Out),[V1,V],[Out]).
input_output_vars(mod(V1,V,Out),[V1,V],[Out]).


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

#### Computed strongly connected components 
0. non_recursive  : [if/4]
1. recursive  : [leq/3]
2. recursive  : [minus/3]
3. recursive [non_tail] : [(mod)/3]
4. non_recursive  : [start/3]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into if/4
1. SCC is partially evaluated into leq/3
2. SCC is partially evaluated into minus/3
3. SCC is partially evaluated into (mod)/3
4. SCC is partially evaluated into start/3

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

### Specialization of cost equations if/4 
* CE 11 is refined into CE [19] 
* CE 9 is refined into CE [20] 
* CE 10 is refined into CE [21] 


### Cost equations --> "Loop" of if/4 
* CEs [19] --> Loop 15 
* CEs [20] --> Loop 16 
* CEs [21] --> Loop 17 

### Ranking functions of CR if(V1,V,V8,Out) 

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


### Specialization of cost equations leq/3 
* CE 8 is refined into CE [22] 
* CE 6 is refined into CE [23] 
* CE 5 is refined into CE [24] 
* CE 7 is refined into CE [25] 


### Cost equations --> "Loop" of leq/3 
* CEs [25] --> Loop 18 
* CEs [22] --> Loop 19 
* CEs [23] --> Loop 20 
* CEs [24] --> Loop 21 

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

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


### Specialization of cost equations minus/3 
* CE 14 is refined into CE [26] 
* CE 12 is refined into CE [27] 
* CE 13 is refined into CE [28] 


### Cost equations --> "Loop" of minus/3 
* CEs [28] --> Loop 22 
* CEs [26] --> Loop 23 
* CEs [27] --> Loop 24 

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

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


### Specialization of cost equations (mod)/3 
* CE 16 is refined into CE [29] 
* CE 15 is refined into CE [30] 
* CE 18 is refined into CE [31] 
* CE 17 is refined into CE [32,33,34,35,36,37,38,39,40,41,42,43,44,45] 


### Cost equations --> "Loop" of (mod)/3 
* CEs [44] --> Loop 25 
* CEs [42] --> Loop 26 
* CEs [40] --> Loop 27 
* CEs [34] --> Loop 28 
* CEs [32] --> Loop 29 
* CEs [35,39,45] --> Loop 30 
* CEs [33] --> Loop 31 
* CEs [36] --> Loop 32 
* CEs [37,38,41,43] --> Loop 33 
* CEs [29] --> Loop 34 
* CEs [30,31] --> Loop 35 

### Ranking functions of CR mod(V1,V,Out) 
* RF of phase [25,28,30]: [V1,V1-V+1]

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


### Specialization of cost equations start/3 
* CE 1 is refined into CE [46,47,48,49,50] 
* CE 2 is refined into CE [51,52,53] 
* CE 3 is refined into CE [54,55,56] 
* CE 4 is refined into CE [57,58,59,60,61,62] 


### Cost equations --> "Loop" of start/3 
* CEs [59] --> Loop 36 
* CEs [47,54] --> Loop 37 
* CEs [52] --> Loop 38 
* CEs [57] --> Loop 39 
* CEs [51] --> Loop 40 
* CEs [46,48,49,50,53,55,56,58,60,61,62] --> Loop 41 

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

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


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

#### Cost of chains of if(V1,V,V8,Out):
* Chain [17]: 1
  with precondition: [V1=1,V8=Out,V>=0,V8>=0] 

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

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


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

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

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

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

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

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

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

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

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


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

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

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

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

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

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


#### Cost of chains of mod(V1,V,Out):
* Chain [[25,28,30],35]: 11*it(25)+5*s(19)+2*s(21)+1*s(23)+1
  Such that:aux(7) =< V1-V+1
aux(10) =< V1
aux(3) =< aux(10)
it(25) =< aux(10)
s(19) =< aux(10)
aux(3) =< aux(7)
it(25) =< aux(7)
s(23) =< it(25)*aux(10)
s(21) =< aux(3)

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

* Chain [[25,28,30],33,35]: 11*it(25)+7*s(19)+2*s(21)+1*s(23)+5*s(27)+3
  Such that:aux(7) =< V1-V+1
aux(13) =< V
aux(14) =< V1
s(19) =< aux(14)
s(27) =< aux(13)
aux(3) =< aux(14)
it(25) =< aux(14)
aux(3) =< aux(7)
it(25) =< aux(7)
s(23) =< it(25)*aux(14)
s(21) =< aux(3)

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

* Chain [[25,28,30],32,35]: 11*it(25)+5*s(19)+2*s(21)+1*s(23)+1*s(34)+4
  Such that:aux(7) =< V1-V+1
s(34) =< V
aux(15) =< V1
aux(3) =< aux(15)
it(25) =< aux(15)
s(19) =< aux(15)
aux(3) =< aux(7)
it(25) =< aux(7)
s(23) =< it(25)*aux(15)
s(21) =< aux(3)

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

* Chain [[25,28,30],31,35]: 18*it(25)+1*s(23)+1*s(35)+3
  Such that:s(35) =< 1
aux(16) =< V1
it(25) =< aux(16)
s(23) =< it(25)*aux(16)

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

* Chain [[25,28,30],29,35]: 18*it(25)+1*s(23)+1*s(36)+4
  Such that:s(36) =< 1
aux(17) =< V1
it(25) =< aux(17)
s(23) =< it(25)*aux(17)

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

* Chain [[25,28,30],27,35]: 11*it(25)+6*s(19)+2*s(21)+1*s(23)+1*s(38)+4
  Such that:aux(7) =< V1-V+1
s(38) =< V
aux(18) =< V1
s(19) =< aux(18)
aux(3) =< aux(18)
it(25) =< aux(18)
aux(3) =< aux(7)
it(25) =< aux(7)
s(23) =< it(25)*aux(18)
s(21) =< aux(3)

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

* Chain [[25,28,30],26,35]: 11*it(25)+4*s(19)+2*s(21)+1*s(23)+1*s(24)+2*s(39)+4
  Such that:aux(6) =< V1
aux(7) =< V1-V+1
aux(19) =< V
aux(20) =< V1-V
s(39) =< aux(19)
aux(3) =< aux(6)
it(25) =< aux(6)
s(20) =< aux(6)
s(24) =< aux(6)
aux(3) =< aux(7)
it(25) =< aux(7)
aux(3) =< aux(20)
it(25) =< aux(20)
s(20) =< aux(20)
s(24) =< aux(20)
s(23) =< it(25)*aux(6)
s(21) =< aux(3)
s(19) =< s(20)

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

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

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

* Chain [33,35]: 5*s(27)+2*s(28)+3
  Such that:aux(12) =< V1
aux(13) =< V
s(28) =< aux(12)
s(27) =< aux(13)

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

* Chain [32,35]: 1*s(34)+4
  Such that:s(34) =< V

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

* Chain [31,35]: 1*s(35)+3
  Such that:s(35) =< 1

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

* Chain [29,35]: 1*s(36)+4
  Such that:s(36) =< 1

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

* Chain [27,35]: 1*s(37)+1*s(38)+4
  Such that:s(38) =< V
s(37) =< Out

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

* Chain [26,35]: 2*s(39)+4
  Such that:aux(19) =< V
s(39) =< aux(19)

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


#### Cost of chains of start(V1,V,V8):
* Chain [41]: 21*s(85)+27*s(87)+11*s(97)+1*s(99)+1*s(100)+2*s(101)+4*s(102)+44*s(104)+4*s(105)+8*s(106)+4
  Such that:s(90) =< V1-V
aux(26) =< V1
aux(27) =< V1-V+1
aux(28) =< V
s(87) =< aux(26)
s(85) =< aux(28)
s(96) =< aux(26)
s(97) =< aux(26)
s(98) =< aux(26)
s(99) =< aux(26)
s(96) =< aux(27)
s(97) =< aux(27)
s(96) =< s(90)
s(97) =< s(90)
s(98) =< s(90)
s(99) =< s(90)
s(100) =< s(97)*aux(26)
s(101) =< s(96)
s(102) =< s(98)
s(103) =< aux(26)
s(104) =< aux(26)
s(103) =< aux(27)
s(104) =< aux(27)
s(105) =< s(104)*aux(26)
s(106) =< s(103)

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

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

* Chain [39]: 1*s(125)+4
  Such that:s(125) =< V

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

* Chain [38]: 1
  with precondition: [V1=2,V>=0,V8>=0] 

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

* Chain [36]: 4*s(128)+36*s(129)+2*s(130)+4
  Such that:s(126) =< 1
s(127) =< V1
s(128) =< s(126)
s(129) =< s(127)
s(130) =< s(129)*s(127)

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


Closed-form bounds of start(V1,V,V8): 
-------------------------------------
* Chain [41] with precondition: [V1>=0,V>=0] 
    - Upper bound: 97*V1+4+5*V1*V1+21*V 
    - Complexity: n^2 
* Chain [40] with precondition: [V1=1,V>=0,V8>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [39] with precondition: [V1=1,V>=2] 
    - Upper bound: V+4 
    - Complexity: n 
* Chain [38] with precondition: [V1=2,V>=0,V8>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [37] with precondition: [V=0,V1>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [36] with precondition: [V=1,V1>=1] 
    - Upper bound: 36*V1+8+2*V1*V1 
    - Complexity: n^2 

### Maximum cost of start(V1,V,V8): max([V+3,36*V1+3+2*V1*V1+max([4,3*V1*V1+61*V1+21*V])])+1 
Asymptotic class: n^2 
* Total analysis performed in 535 ms.


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

(14)
BOUNDS(1, n^2)

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

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

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

   leq(0, y) -> true
   leq(s(x), 0) -> false
   leq(s(x), s(y)) -> leq(x, y)
   if(true, x, y) -> x
   if(false, x, y) -> y
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, y)
   mod(0, y) -> 0
   mod(s(x), 0) -> 0
   mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x))

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

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

The rewrite sequence

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

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

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

The result substitution is [ ].




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

(18)
Complex Obligation (BEST)

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

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

   leq(0, y) -> true
   leq(s(x), 0) -> false
   leq(s(x), s(y)) -> leq(x, y)
   if(true, x, y) -> x
   if(false, x, y) -> y
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, y)
   mod(0, y) -> 0
   mod(s(x), 0) -> 0
   mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x))

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

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

(21)
BOUNDS(n^1, INF)

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

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

   leq(0, y) -> true
   leq(s(x), 0) -> false
   leq(s(x), s(y)) -> leq(x, y)
   if(true, x, y) -> x
   if(false, x, y) -> y
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, y)
   mod(0, y) -> 0
   mod(s(x), 0) -> 0
   mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x))

S is empty.
Rewrite Strategy: FULL