/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


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


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

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 157 ms]
(4) CpxRelTRS
(5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
(6) CpxRelTRS
(7) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(8) CpxRelTRS
(9) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(10) CpxWeightedTrs
(11) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(12) CpxWeightedTrs
(13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(14) CpxTypedWeightedTrs
(15) CompletionProof [UPPER BOUND(ID), 0 ms]
(16) CpxTypedWeightedCompleteTrs
(17) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
(18) CpxRNTS
(19) CompleteCoflocoProof [FINISHED, 463 ms]
(20) BOUNDS(1, n^2)


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

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


The TRS R consists of the following rules:

   *(x, *(y, z)) -> *(*(x, y), z)
   *(x, x) -> x

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

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))


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

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


The TRS R consists of the following rules:

   *(x, *(y, z)) -> *(*(x, y), z)
   *(x, x) -> x

The (relative) TRS S consists of the following rules:

   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))

Rewrite Strategy: FULL
----------------------------------------

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

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


The TRS R consists of the following rules:

   *(x, *(y, z)) -> *(*(x, y), z)
   *(x, x) -> x

The (relative) TRS S consists of the following rules:

   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))

Rewrite Strategy: FULL
----------------------------------------

(5) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

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


The TRS R consists of the following rules:

   *(x, x) -> x
   *(x, c_*(y, z)) -> *(*(x, y), z)

The (relative) TRS S consists of the following rules:

   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   *(x0, x1) -> c_*(x0, x1)

Rewrite Strategy: FULL
----------------------------------------

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

As the TRS is a non-duplicating overlay system, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   *(x, x) -> x
   *(x, c_*(y, z)) -> *(*(x, y), z)

The (relative) TRS S consists of the following rules:

   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   *(x0, x1) -> c_*(x0, x1)

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

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

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

   *(x, x) -> x [1]
   *(x, c_*(y, z)) -> *(*(x, y), z) [1]
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2)) [0]
   *(x0, x1) -> c_*(x0, x1) [0]

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

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

* => times

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

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

   times(x, x) -> x [1]
   times(x, c_*(y, z)) -> times(times(x, y), z) [1]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   times(x0, x1) -> c_*(x0, x1) [0]

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

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

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

   times(x, x) -> x [1]
   times(x, c_*(y, z)) -> times(times(x, y), z) [1]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   times(x0, x1) -> c_*(x0, x1) [0]

The TRS has the following type information:
times :: c_* -> c_* -> c_*
c_* :: c_* -> c_* -> c_*
encArg :: cons_* -> c_*
cons_* :: cons_* -> cons_* -> cons_*
encode_* :: cons_* -> cons_* -> c_*

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

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

   encArg(v0) -> null_encArg [0]
   encode_*(v0, v1) -> null_encode_* [0]
   times(v0, v1) -> null_times [0]

And the following fresh constants:    null_encArg, null_encode_*, null_times, const

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

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

   times(x, x) -> x [1]
   times(x, c_*(y, z)) -> times(times(x, y), z) [1]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   times(x0, x1) -> c_*(x0, x1) [0]
   encArg(v0) -> null_encArg [0]
   encode_*(v0, v1) -> null_encode_* [0]
   times(v0, v1) -> null_times [0]

The TRS has the following type information:
times :: c_*:null_encArg:null_encode_*:null_times -> c_*:null_encArg:null_encode_*:null_times -> c_*:null_encArg:null_encode_*:null_times
c_* :: c_*:null_encArg:null_encode_*:null_times -> c_*:null_encArg:null_encode_*:null_times -> c_*:null_encArg:null_encode_*:null_times
encArg :: cons_* -> c_*:null_encArg:null_encode_*:null_times
cons_* :: cons_* -> cons_* -> cons_*
encode_* :: cons_* -> cons_* -> c_*:null_encArg:null_encode_*:null_times
null_encArg :: c_*:null_encArg:null_encode_*:null_times
null_encode_* :: c_*:null_encArg:null_encode_*:null_times
null_times :: c_*:null_encArg:null_encode_*:null_times
const :: cons_*

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

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

   null_encArg => 0
   null_encode_* => 0
   null_times => 0
   const => 0

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

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

   encArg(z') -{ 0 }-> times(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encode_*(z', z'') -{ 0 }-> times(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   encode_*(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   times(z', z'') -{ 1 }-> x :|: z' = x, x >= 0, z'' = x
   times(z', z'') -{ 1 }-> times(times(x, y), z) :|: z >= 0, z' = x, x >= 0, y >= 0, z'' = 1 + y + z
   times(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   times(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z'' = x1, x0 >= 0, x1 >= 0, z' = x0

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V, V2),0,[times(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2),0,[encArg(V, Out)],[V >= 0]).
eq(start(V, V2),0,[fun(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(times(V, V2, Out),1,[],[Out = V1,V = V1,V1 >= 0,V2 = V1]).
eq(times(V, V2, Out),1,[times(V3, V4, Ret0),times(Ret0, V5, Ret)],[Out = Ret,V5 >= 0,V = V3,V3 >= 0,V4 >= 0,V2 = 1 + V4 + V5]).
eq(encArg(V, Out),0,[encArg(V7, Ret01),encArg(V6, Ret1),times(Ret01, Ret1, Ret2)],[Out = Ret2,V7 >= 0,V6 >= 0,V = 1 + V6 + V7]).
eq(fun(V, V2, Out),0,[encArg(V8, Ret02),encArg(V9, Ret11),times(Ret02, Ret11, Ret3)],[Out = Ret3,V8 >= 0,V = V8,V9 >= 0,V2 = V9]).
eq(times(V, V2, Out),0,[],[Out = 1 + V10 + V11,V2 = V10,V11 >= 0,V10 >= 0,V = V11]).
eq(encArg(V, Out),0,[],[Out = 0,V12 >= 0,V = V12]).
eq(fun(V, V2, Out),0,[],[Out = 0,V14 >= 0,V13 >= 0,V2 = V13,V = V14]).
eq(times(V, V2, Out),0,[],[Out = 0,V16 >= 0,V15 >= 0,V2 = V15,V = V16]).
input_output_vars(times(V,V2,Out),[V,V2],[Out]).
input_output_vars(encArg(V,Out),[V],[Out]).
input_output_vars(fun(V,V2,Out),[V,V2],[Out]).


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

#### Computed strongly connected components 
0. recursive [multiple] : [times/3]
1. recursive [non_tail,multiple] : [encArg/2]
2. non_recursive  : [fun/3]
3. non_recursive  : [start/2]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into times/3
1. SCC is partially evaluated into encArg/2
2. SCC is partially evaluated into fun/3
3. SCC is partially evaluated into start/2

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

### Specialization of cost equations times/3 
* CE 6 is refined into CE [12] 
* CE 4 is refined into CE [13] 
* CE 7 is refined into CE [14] 
* CE 5 is refined into CE [15] 


### Cost equations --> "Loop" of times/3 
* CEs [15] --> Loop 9 
* CEs [12] --> Loop 10 
* CEs [13] --> Loop 11 
* CEs [14] --> Loop 12 

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

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


### Specialization of cost equations encArg/2 
* CE 9 is refined into CE [16] 
* CE 8 is refined into CE [17,18,19,20] 


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

### Ranking functions of CR encArg(V,Out) 
* RF of phase [13,14,15,16]: [V]

#### Partial ranking functions of CR encArg(V,Out) 
* Partial RF of phase [13,14,15,16]:
  - RF of loop [13:1,13:2,14:1,14:2,15:1,15:2,16:1,16:2]:
    V


### Specialization of cost equations fun/3 
* CE 10 is refined into CE [21,22,23,24,25,26,27,28,29,30,31,32,33,34] 
* CE 11 is refined into CE [35] 


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

### Ranking functions of CR fun(V,V2,Out) 

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [36,37,38,39] 
* CE 2 is refined into CE [40,41] 
* CE 3 is refined into CE [42,43,44,45,46] 


### Cost equations --> "Loop" of start/2 
* CEs [36,37,38,39,40,41,42,43,44,45,46] --> Loop 23 

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

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


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

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

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

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

* Chain [multiple([9],[[12],[11],[10]])]: 1*it(9)+1*it([11])+0
  Such that:it(9) =< V2
aux(1) =< V2+1
it([11]) =< aux(1)

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


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

* Chain [multiple([13,14,15,16],[[17]])]: 1*it(15)+1*s(7)+1*s(8)+0
  Such that:aux(4) =< V
aux(5) =< 2*V+1
it(15) =< aux(4)
it(13) =< aux(5)
it(15) =< aux(5)
aux(3) =< aux(4)+1
s(7) =< it(13)*aux(4)
s(9) =< it(13)*aux(3)
s(8) =< s(9)

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


#### Cost of chains of fun(V,V2,Out):
* Chain [22]: 3*s(12)+3*s(15)+3*s(17)+3*s(28)+3*s(31)+3*s(33)+1
  Such that:aux(6) =< V
aux(7) =< 2*V+1
aux(8) =< V2
aux(9) =< 2*V2+1
s(28) =< aux(6)
s(28) =< aux(7)
s(30) =< aux(6)+1
s(31) =< aux(7)*aux(6)
s(32) =< aux(7)*s(30)
s(33) =< s(32)
s(12) =< aux(8)
s(12) =< aux(9)
s(14) =< aux(8)+1
s(15) =< aux(9)*aux(8)
s(16) =< aux(9)*s(14)
s(17) =< s(16)

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

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

* Chain [20]: 3*s(60)+3*s(63)+3*s(65)+1*s(74)+1*s(76)+1*s(79)+1*s(82)+1*s(84)+1
  Such that:s(77) =< V
s(78) =< 2*V+1
s(75) =< V2+1
aux(11) =< V2
aux(12) =< 2*V2+1
s(60) =< aux(11)
s(60) =< aux(12)
s(62) =< aux(11)+1
s(63) =< aux(12)*aux(11)
s(64) =< aux(12)*s(62)
s(65) =< s(64)
s(79) =< s(77)
s(79) =< s(78)
s(81) =< s(77)+1
s(82) =< s(78)*s(77)
s(83) =< s(78)*s(81)
s(84) =< s(83)
s(74) =< aux(11)
s(76) =< s(75)

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

* Chain [19]: 1*s(95)+1*s(98)+1*s(100)+0
  Such that:s(93) =< V
s(94) =< 2*V+1
s(95) =< s(93)
s(95) =< s(94)
s(97) =< s(93)+1
s(98) =< s(94)*s(93)
s(99) =< s(94)*s(97)
s(100) =< s(99)

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

* Chain [18]: 2*s(103)+2*s(106)+2*s(108)+2*s(111)+2*s(114)+2*s(116)+1*s(133)+1*s(135)+0
  Such that:s(134) =< V2+1
aux(14) =< V
aux(15) =< 2*V+1
aux(16) =< V2
aux(17) =< 2*V2+1
s(111) =< aux(16)
s(111) =< aux(17)
s(113) =< aux(16)+1
s(114) =< aux(17)*aux(16)
s(115) =< aux(17)*s(113)
s(116) =< s(115)
s(103) =< aux(14)
s(103) =< aux(15)
s(105) =< aux(14)+1
s(106) =< aux(15)*aux(14)
s(107) =< aux(15)*s(105)
s(108) =< s(107)
s(133) =< aux(16)
s(135) =< s(134)

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


#### Cost of chains of start(V,V2):
* Chain [23]: 3*s(136)+3*s(138)+8*s(141)+8*s(144)+8*s(146)+8*s(156)+8*s(158)+8*s(160)+1
  Such that:aux(18) =< V
aux(19) =< 2*V+1
aux(20) =< V2
aux(21) =< V2+1
aux(22) =< 2*V2+1
s(136) =< aux(20)
s(141) =< aux(18)
s(141) =< aux(19)
s(143) =< aux(18)+1
s(144) =< aux(19)*aux(18)
s(145) =< aux(19)*s(143)
s(146) =< s(145)
s(156) =< aux(20)
s(156) =< aux(22)
s(157) =< aux(20)+1
s(158) =< aux(22)*aux(20)
s(159) =< aux(22)*s(157)
s(160) =< s(159)
s(138) =< aux(21)

  with precondition: [V>=0] 


Closed-form bounds of start(V,V2): 
-------------------------------------
* Chain [23] with precondition: [V>=0] 
    - Upper bound: 8*V+1+(2*V+1)*(16*V)+nat(V2)*11+nat(V2)*16*nat(2*V2+1)+nat(V2+1)*3+(16*V+8)+nat(2*V2+1)*8 
    - Complexity: n^2 

### Maximum cost of start(V,V2): 8*V+1+(2*V+1)*(16*V)+nat(V2)*11+nat(V2)*16*nat(2*V2+1)+nat(V2+1)*3+(16*V+8)+nat(2*V2+1)*8 
Asymptotic class: n^2 
* Total analysis performed in 373 ms.


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

(20)
BOUNDS(1, n^2)