/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^1))
proof of /export/starexec/sandbox/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^1).

(0) CpxTRS
(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxWeightedTrs
    (3) CpxWeightedTrsRenamingProof [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, 159 ms]
    (12) BOUNDS(1, n^1)
(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 (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).


The TRS R consists of the following rules:

   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))
   double(x) -> +(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^1).


The TRS R consists of the following rules:

   double(0) -> 0 [1]
   double(s(x)) -> s(s(double(x))) [1]
   +(x, 0) -> x [1]
   +(x, s(y)) -> s(+(x, y)) [1]
   +(s(x), y) -> s(+(x, y)) [1]
   double(x) -> +(x, x) [1]

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

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

+ => plus

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

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


The TRS R consists of the following rules:

   double(0) -> 0 [1]
   double(s(x)) -> s(s(double(x))) [1]
   plus(x, 0) -> x [1]
   plus(x, s(y)) -> s(plus(x, y)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   double(x) -> plus(x, x) [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:

   double(0) -> 0 [1]
   double(s(x)) -> s(s(double(x))) [1]
   plus(x, 0) -> x [1]
   plus(x, s(y)) -> s(plus(x, y)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   double(x) -> plus(x, x) [1]

The TRS has the following type information:
double :: 0:s -> 0:s
0 :: 0:s
s :: 0:s -> 0:s
plus :: 0:s -> 0:s -> 0:s

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:

   double(0) -> 0 [1]
   double(s(x)) -> s(s(double(x))) [1]
   plus(x, 0) -> x [1]
   plus(x, s(y)) -> s(plus(x, y)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   double(x) -> plus(x, x) [1]

The TRS has the following type information:
double :: 0:s -> 0:s
0 :: 0:s
s :: 0:s -> 0:s
plus :: 0:s -> 0:s -> 0:s

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

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

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

   double(z) -{ 1 }-> plus(x, x) :|: x >= 0, z = x
   double(z) -{ 1 }-> 0 :|: z = 0
   double(z) -{ 1 }-> 1 + (1 + double(x)) :|: x >= 0, z = 1 + x
   plus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = x
   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y

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, V2),0,[double(V, Out)],[V >= 0]).
eq(start(V, V2),0,[plus(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(double(V, Out),1,[],[Out = 0,V = 0]).
eq(double(V, Out),1,[double(V1, Ret11)],[Out = 2 + Ret11,V1 >= 0,V = 1 + V1]).
eq(plus(V, V2, Out),1,[],[Out = V3,V3 >= 0,V = V3,V2 = 0]).
eq(plus(V, V2, Out),1,[plus(V4, V5, Ret1)],[Out = 1 + Ret1,V2 = 1 + V5,V4 >= 0,V5 >= 0,V = V4]).
eq(plus(V, V2, Out),1,[plus(V6, V7, Ret12)],[Out = 1 + Ret12,V6 >= 0,V7 >= 0,V = 1 + V6,V2 = V7]).
eq(double(V, Out),1,[plus(V8, V8, Ret)],[Out = Ret,V8 >= 0,V = V8]).
input_output_vars(double(V,Out),[V],[Out]).
input_output_vars(plus(V,V2,Out),[V,V2],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [plus/3]
1. recursive  : [double/2]
2. non_recursive  : [start/2]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into plus/3
1. SCC is partially evaluated into double/2
2. SCC is partially evaluated into start/2

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

### Specialization of cost equations plus/3 
* CE 7 is refined into CE [9] 
* CE 8 is refined into CE [10] 
* CE 6 is refined into CE [11] 


### Cost equations --> "Loop" of plus/3 
* CEs [11] --> Loop 7 
* CEs [9] --> Loop 8 
* CEs [10] --> Loop 9 

### Ranking functions of CR plus(V,V2,Out) 
* RF of phase [8,9]: [V+V2]

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


### Specialization of cost equations double/2 
* CE 3 is refined into CE [12] 
* CE 5 is refined into CE [13,14] 
* CE 4 is refined into CE [15] 


### Cost equations --> "Loop" of double/2 
* CEs [15] --> Loop 10 
* CEs [14] --> Loop 11 
* CEs [12,13] --> Loop 12 

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

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [16,17] 
* CE 2 is refined into CE [18,19] 


### Cost equations --> "Loop" of start/2 
* CEs [17] --> Loop 13 
* CEs [19] --> Loop 14 
* CEs [18] --> Loop 15 
* CEs [16] --> Loop 16 

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

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


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

#### Cost of chains of plus(V,V2,Out):
* Chain [[8,9],7]: 1*it(8)+1*it(9)+1
  Such that:it(9) =< -V2+Out
it(8) =< V2
aux(3) =< Out
it(8) =< aux(3)
it(9) =< aux(3)

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

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


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

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

* Chain [[10],11]: 1*it(10)+2*s(1)+2
  Such that:aux(4) =< Out/2
aux(5) =< Out
it(10) =< aux(5)
s(1) =< aux(4)
s(1) =< aux(5)

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

* Chain [12]: 2
  with precondition: [V=0,Out=0] 

* Chain [11]: 2*s(1)+2
  Such that:s(3) =< 2*V
aux(4) =< V
s(1) =< aux(4)
s(1) =< s(3)

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


#### Cost of chains of start(V,V2):
* Chain [16]: 2
  with precondition: [V=0] 

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

* Chain [14]: 1*s(12)+1*s(13)+1
  Such that:s(12) =< V
s(14) =< V+V2
s(13) =< V2
s(13) =< s(14)
s(12) =< s(14)

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

* Chain [13]: 1*s(19)+4*s(20)+1*s(21)+2
  Such that:aux(7) =< V
aux(8) =< 2*V
s(19) =< aux(7)
s(20) =< aux(7)
s(20) =< aux(8)
s(21) =< aux(8)

  with precondition: [2*V>=1] 


Closed-form bounds of start(V,V2): 
-------------------------------------
* Chain [16] with precondition: [V=0] 
    - Upper bound: 2 
    - Complexity: constant 
* Chain [15] with precondition: [V2=0,V>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [14] with precondition: [V>=0,V2>=0,V+V2>=1] 
    - Upper bound: V+V2+1 
    - Complexity: n 
* Chain [13] with precondition: [2*V>=1] 
    - Upper bound: 7*V+2 
    - Complexity: n 

### Maximum cost of start(V,V2): max([1,max([6*V+1,nat(V2)])+V])+1 
Asymptotic class: n 
* Total analysis performed in 112 ms.


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

(12)
BOUNDS(1, n^1)

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

(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 (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).


The TRS R consists of the following rules:

   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))
   double(x) -> +(x, x)

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

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

The rewrite sequence

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

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

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

The result substitution is [ ].




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

(16)
Complex Obligation (BEST)

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

(17)
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^1).


The TRS R consists of the following rules:

   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))
   double(x) -> +(x, x)

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

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

(19)
BOUNDS(n^1, INF)

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

(20)
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^1).


The TRS R consists of the following rules:

   double(0) -> 0
   double(s(x)) -> s(s(double(x)))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))
   double(x) -> +(x, x)

S is empty.
Rewrite Strategy: INNERMOST