/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, 370 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:

   p(0) -> 0
   p(s(x)) -> x
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   minus(x, 0) -> x
   minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y)))))
   if(true, x, y) -> x
   if(false, x, y) -> y

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:

   p(0) -> 0 [1]
   p(s(x)) -> x [1]
   le(0, y) -> true [1]
   le(s(x), 0) -> false [1]
   le(s(x), s(y)) -> le(x, y) [1]
   minus(x, 0) -> x [1]
   minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y))))) [1]
   if(true, x, y) -> x [1]
   if(false, x, y) -> y [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:

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

The TRS has the following type information:
p :: 0:s -> 0:s
0 :: 0:s
s :: 0:s -> 0:s
le :: 0:s -> 0:s -> true:false
true :: true:false
false :: true:false
minus :: 0:s -> 0:s -> 0:s
if :: true:false -> 0: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:
none

And the following fresh constants: none

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

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

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

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

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

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

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

   if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
   if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0, z = 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 }-> if(le(x, 1 + y), 0, p(minus(x, p(1 + y)))) :|: z' = 1 + y, x >= 0, y >= 0, z = x
   p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x
   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, V2, V11),0,[p(V, Out)],[V >= 0]).
eq(start(V, V2, V11),0,[le(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2, V11),0,[minus(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2, V11),0,[if(V, V2, V11, Out)],[V >= 0,V2 >= 0,V11 >= 0]).
eq(p(V, Out),1,[],[Out = 0,V = 0]).
eq(p(V, Out),1,[],[Out = V1,V1 >= 0,V = 1 + V1]).
eq(le(V, V2, Out),1,[],[Out = 1,V3 >= 0,V = 0,V2 = V3]).
eq(le(V, V2, Out),1,[],[Out = 0,V4 >= 0,V = 1 + V4,V2 = 0]).
eq(le(V, V2, Out),1,[le(V5, V6, Ret)],[Out = Ret,V2 = 1 + V6,V5 >= 0,V6 >= 0,V = 1 + V5]).
eq(minus(V, V2, Out),1,[],[Out = V7,V7 >= 0,V = V7,V2 = 0]).
eq(minus(V, V2, Out),1,[le(V8, 1 + V9, Ret0),p(1 + V9, Ret201),minus(V8, Ret201, Ret20),p(Ret20, Ret2),if(Ret0, 0, Ret2, Ret1)],[Out = Ret1,V2 = 1 + V9,V8 >= 0,V9 >= 0,V = V8]).
eq(if(V, V2, V11, Out),1,[],[Out = V12,V2 = V12,V11 = V10,V = 1,V12 >= 0,V10 >= 0]).
eq(if(V, V2, V11, Out),1,[],[Out = V13,V2 = V14,V11 = V13,V14 >= 0,V13 >= 0,V = 0]).
input_output_vars(p(V,Out),[V],[Out]).
input_output_vars(le(V,V2,Out),[V,V2],[Out]).
input_output_vars(minus(V,V2,Out),[V,V2],[Out]).
input_output_vars(if(V,V2,V11,Out),[V,V2,V11],[Out]).


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

#### Computed strongly connected components 
0. non_recursive  : [if/4]
1. recursive  : [le/3]
2. non_recursive  : [p/2]
3. recursive [non_tail] : [minus/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 le/3
2. SCC is partially evaluated into p/2
3. SCC is partially evaluated into minus/3
4. SCC is partially evaluated into start/3

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

### Specialization of cost equations if/4 
* CE 12 is refined into CE [14] 
* CE 13 is refined into CE [15] 


### Cost equations --> "Loop" of if/4 
* CEs [14] --> Loop 11 
* CEs [15] --> Loop 12 

### Ranking functions of CR if(V,V2,V11,Out) 

#### Partial ranking functions of CR if(V,V2,V11,Out) 


### Specialization of cost equations le/3 
* CE 9 is refined into CE [16] 
* CE 8 is refined into CE [17] 
* CE 7 is refined into CE [18] 


### Cost equations --> "Loop" of le/3 
* CEs [17] --> Loop 13 
* CEs [18] --> Loop 14 
* CEs [16] --> Loop 15 

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

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


### Specialization of cost equations p/2 
* CE 6 is refined into CE [19] 
* CE 5 is refined into CE [20] 


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

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

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


### Specialization of cost equations minus/3 
* CE 11 is refined into CE [21,22,23,24,25,26] 
* CE 10 is refined into CE [27] 


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

### Ranking functions of CR minus(V,V2,Out) 
* RF of phase [19]: [V2]
* RF of phase [21]: [-V+V2+1,V2]
* RF of phase [22]: [V2]
* RF of phase [24]: [V2]

#### Partial ranking functions of CR minus(V,V2,Out) 
* Partial RF of phase [19]:
  - RF of loop [19:1]:
    V2
* Partial RF of phase [21]:
  - RF of loop [21:1]:
    -V+V2+1
    V2
* Partial RF of phase [22]:
  - RF of loop [22:1]:
    V2
* Partial RF of phase [24]:
  - RF of loop [24:1]:
    V2


### Specialization of cost equations start/3 
* CE 1 is refined into CE [28,29] 
* CE 2 is refined into CE [30,31,32,33] 
* CE 3 is refined into CE [34,35,36,37,38,39,40] 
* CE 4 is refined into CE [41,42] 


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

### Ranking functions of CR start(V,V2,V11) 

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


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

#### Cost of chains of if(V,V2,V11,Out):
* Chain [12]: 1
  with precondition: [V=0,V11=Out,V2>=0,V11>=0] 

* Chain [11]: 1
  with precondition: [V=1,V2=Out,V2>=0,V11>=0] 


#### Cost of chains of le(V,V2,Out):
* Chain [[15],14]: 1*it(15)+1
  Such that:it(15) =< V

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

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

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

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

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


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

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


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

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

* Chain [[21],20,[19],18]: 6*it(19)+5*it(21)+1*s(3)+1*s(7)+6
  Such that:it(21) =< -V+V2
aux(6) =< V
it(19) =< aux(6)
s(3) =< it(19)*aux(6)
s(7) =< it(21)*aux(6)

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

* Chain [[21],20,18]: 5*it(21)+1*s(4)+1*s(7)+6
  Such that:it(21) =< V2
aux(7) =< 1
s(4) =< aux(7)
s(7) =< it(21)*aux(7)

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

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

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

* Chain [20,[19],18]: 6*it(19)+1*s(3)+6
  Such that:aux(4) =< V2
it(19) =< aux(4)
s(3) =< it(19)*aux(4)

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

* Chain [20,18]: 1*s(4)+6
  Such that:s(4) =< 1

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

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


#### Cost of chains of start(V,V2,V11):
* Chain [30]: 5*s(8)+1
  Such that:s(8) =< V2

  with precondition: [V=0] 

* Chain [29]: 6*s(9)+7*s(10)+1*s(11)+5*s(12)+1*s(15)+1*s(16)+1*s(19)+6
  Such that:s(11) =< 1
s(12) =< -V+V2
aux(8) =< V
aux(9) =< V2
s(10) =< aux(8)
s(9) =< aux(9)
s(15) =< s(10)*aux(8)
s(16) =< s(12)*aux(8)
s(19) =< s(9)*aux(9)

  with precondition: [V>=1] 

* Chain [28]: 1
  with precondition: [V=1,V2>=0,V11>=0] 

* Chain [27]: 5*s(20)+1*s(22)+1*s(23)+6
  Such that:s(21) =< 1
s(20) =< V2
s(22) =< s(21)
s(23) =< s(20)*s(21)

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

* Chain [26]: 1
  with precondition: [V2=0,V>=0] 

* Chain [25]: 6*s(25)+1*s(26)+6
  Such that:s(24) =< V2
s(25) =< s(24)
s(26) =< s(25)*s(24)

  with precondition: [V=V2,V>=2] 


Closed-form bounds of start(V,V2,V11): 
-------------------------------------
* Chain [30] with precondition: [V=0] 
    - Upper bound: nat(V2)*5+1 
    - Complexity: n 
* Chain [29] with precondition: [V>=1] 
    - Upper bound: 7*V+7+V*V+nat(-V+V2)*V+nat(V2)*6+nat(V2)*nat(V2)+nat(-V+V2)*5 
    - Complexity: n^2 
* Chain [28] with precondition: [V=1,V2>=0,V11>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [27] with precondition: [V=1,V2>=2] 
    - Upper bound: 6*V2+7 
    - Complexity: n 
* Chain [26] with precondition: [V2=0,V>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [25] with precondition: [V=V2,V>=2] 
    - Upper bound: 6*V2+6+V2*V2 
    - Complexity: n^2 

### Maximum cost of start(V,V2,V11): nat(V2)+5+max([1,7*V+1+V*V+nat(-V+V2)*V+nat(-V+V2)*5+nat(V2)*nat(V2)])+nat(V2)*5+1 
Asymptotic class: n^2 
* Total analysis performed in 288 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:

   p(0) -> 0
   p(s(x)) -> x
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   minus(x, 0) -> x
   minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y)))))
   if(true, x, y) -> x
   if(false, x, y) -> y

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

le(s(x), s(y)) ->^+ le(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 [ ].




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

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

   p(0) -> 0
   p(s(x)) -> x
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   minus(x, 0) -> x
   minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y)))))
   if(true, x, y) -> x
   if(false, x, y) -> y

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:

   p(0) -> 0
   p(s(x)) -> x
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   minus(x, 0) -> x
   minus(x, s(y)) -> if(le(x, s(y)), 0, p(minus(x, p(s(y)))))
   if(true, x, y) -> x
   if(false, x, y) -> y

S is empty.
Rewrite Strategy: INNERMOST