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

(0) Obligation:

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


The TRS R consists of the following rules:

fact(X) → if(zero(X), n__s(n__0), n__prod(X, n__fact(n__p(X))))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
prod(0, X) → 0
prod(s(X), Y) → add(Y, prod(X, Y))
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
zero(0) → true
zero(s(X)) → false
p(s(X)) → X
s(X) → n__s(X)
0 → n__0
prod(X1, X2) → n__prod(X1, X2)
fact(X) → n__fact(X)
p(X) → n__p(X)
activate(n__s(X)) → s(activate(X))
activate(n__0) → 0
activate(n__prod(X1, X2)) → prod(activate(X1), activate(X2))
activate(n__fact(X)) → fact(activate(X))
activate(n__p(X)) → p(activate(X))
activate(X) → X

Rewrite Strategy: INNERMOST

(1) TrsToWeightedTrsProof (BOTH BOUNDS(ID, ID) transformation)

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

fact(X) → if(zero(X), n__s(n__0), n__prod(X, n__fact(n__p(X)))) [1]
add(0, X) → X [1]
add(s(X), Y) → s(add(X, Y)) [1]
prod(0, X) → 0 [1]
prod(s(X), Y) → add(Y, prod(X, Y)) [1]
if(true, X, Y) → activate(X) [1]
if(false, X, Y) → activate(Y) [1]
zero(0) → true [1]
zero(s(X)) → false [1]
p(s(X)) → X [1]
s(X) → n__s(X) [1]
0 → n__0 [1]
prod(X1, X2) → n__prod(X1, X2) [1]
fact(X) → n__fact(X) [1]
p(X) → n__p(X) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(n__0) → 0 [1]
activate(n__prod(X1, X2)) → prod(activate(X1), activate(X2)) [1]
activate(n__fact(X)) → fact(activate(X)) [1]
activate(n__p(X)) → p(activate(X)) [1]
activate(X) → X [1]

Rewrite Strategy: INNERMOST

(3) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID) transformation)

Renamed defined symbols to avoid conflicts with arithmetic symbols:

0 => 0'

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

fact(X) → if(zero(X), n__s(n__0), n__prod(X, n__fact(n__p(X)))) [1]
add(0', X) → X [1]
add(s(X), Y) → s(add(X, Y)) [1]
prod(0', X) → 0' [1]
prod(s(X), Y) → add(Y, prod(X, Y)) [1]
if(true, X, Y) → activate(X) [1]
if(false, X, Y) → activate(Y) [1]
zero(0') → true [1]
zero(s(X)) → false [1]
p(s(X)) → X [1]
s(X) → n__s(X) [1]
0' → n__0 [1]
prod(X1, X2) → n__prod(X1, X2) [1]
fact(X) → n__fact(X) [1]
p(X) → n__p(X) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(n__0) → 0' [1]
activate(n__prod(X1, X2)) → prod(activate(X1), activate(X2)) [1]
activate(n__fact(X)) → fact(activate(X)) [1]
activate(n__p(X)) → p(activate(X)) [1]
activate(X) → X [1]

Rewrite Strategy: INNERMOST

(5) InnermostUnusableRulesProof (BOTH BOUNDS(ID, ID) transformation)

Removed the following rules with non-basic left-hand side, as they cannot be used in innermost rewriting:

add(0', X) → X [1]
add(s(X), Y) → s(add(X, Y)) [1]
prod(0', X) → 0' [1]
prod(s(X), Y) → add(Y, prod(X, Y)) [1]
zero(0') → true [1]
zero(s(X)) → false [1]
p(s(X)) → X [1]

Due to the following rules that have to be used instead:

0' → n__0 [1]
s(X) → n__s(X) [1]

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

fact(X) → if(zero(X), n__s(n__0), n__prod(X, n__fact(n__p(X)))) [1]
if(true, X, Y) → activate(X) [1]
if(false, X, Y) → activate(Y) [1]
s(X) → n__s(X) [1]
0' → n__0 [1]
prod(X1, X2) → n__prod(X1, X2) [1]
fact(X) → n__fact(X) [1]
p(X) → n__p(X) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(n__0) → 0' [1]
activate(n__prod(X1, X2)) → prod(activate(X1), activate(X2)) [1]
activate(n__fact(X)) → fact(activate(X)) [1]
activate(n__p(X)) → p(activate(X)) [1]
activate(X) → X [1]

Rewrite Strategy: INNERMOST

(7) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(8) Obligation:

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

fact(X) → if(zero(X), n__s(n__0), n__prod(X, n__fact(n__p(X)))) [1]
if(true, X, Y) → activate(X) [1]
if(false, X, Y) → activate(Y) [1]
s(X) → n__s(X) [1]
0' → n__0 [1]
prod(X1, X2) → n__prod(X1, X2) [1]
fact(X) → n__fact(X) [1]
p(X) → n__p(X) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(n__0) → 0' [1]
activate(n__prod(X1, X2)) → prod(activate(X1), activate(X2)) [1]
activate(n__fact(X)) → fact(activate(X)) [1]
activate(n__p(X)) → p(activate(X)) [1]
activate(X) → X [1]

The TRS has the following type information:

fact :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod if :: zero:true:false → n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod zero :: n__0:n__s:n__p:n__fact:n__prod → zero:true:false n__s :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod n__0 :: n__0:n__s:n__p:n__fact:n__prod n__prod :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod n__fact :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod n__p :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod true :: zero:true:false activate :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod false :: zero:true:false s :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod 0' :: n__0:n__s:n__p:n__fact:n__prod prod :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod p :: n__0:n__s:n__p:n__fact:n__prod → n__0:n__s:n__p:n__fact:n__prod

Rewrite Strategy: INNERMOST

(9) CompletionProof (UPPER BOUND(ID) transformation)

The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:

if(v0, v1, v2) → null_if [0]

And the following fresh constants:

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: fact(X) → if(zero(X), n__s(n__0), n__prod(X, n__fact(n__p(X)))) [1] if(true, X, Y) → activate(X) [1] if(false, X, Y) → activate(Y) [1] s(X) → n__s(X) [1] 0' → n__0 [1] prod(X1, X2) → n__prod(X1, X2) [1] fact(X) → n__fact(X) [1] p(X) → n__p(X) [1] activate(n__s(X)) → s(activate(X)) [1] activate(n__0) → 0' [1] activate(n__prod(X1, X2)) → prod(activate(X1), activate(X2)) [1] activate(n__fact(X)) → fact(activate(X)) [1] activate(n__p(X)) → p(activate(X)) [1] activate(X) → X [1] if(v0, v1, v2) → null_if [0] The TRS has the following type information: fact :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if if :: zero:true:false → n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if zero :: n__0:n__s:n__p:n__fact:n__prod:null_if → zero:true:false n__s :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if n__0 :: n__0:n__s:n__p:n__fact:n__prod:null_if n__prod :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if n__fact :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if n__p :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if true :: zero:true:false activate :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if false :: zero:true:false s :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if 0' :: n__0:n__s:n__p:n__fact:n__prod:null_if prod :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if p :: n__0:n__s:n__p:n__fact:n__prod:null_if → n__0:n__s:n__p:n__fact:n__prod:null_if null_if :: n__0:n__s:n__p:n__fact:n__prod:null_if Rewrite Strategy: INNERMOST

(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID) transformation)

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

n__0 => 0
true => 1
false => 0
null_if => 0

(12) Obligation:

Complexity RNTS consisting of the following rules:

0' -{ 1 }→ 0 :|:
activate(z) -{ 1 }→ X :|: X >= 0, z = X
activate(z) -{ 1 }→ s(activate(X)) :|: z = 1 + X, X >= 0
activate(z) -{ 1 }→ prod(activate(X1), activate(X2)) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
activate(z) -{ 1 }→ p(activate(X)) :|: z = 1 + X, X >= 0
activate(z) -{ 1 }→ fact(activate(X)) :|: z = 1 + X, X >= 0
activate(z) -{ 1 }→ 0' :|: z = 0
fact(z) -{ 1 }→ if(1 + X, 1 + 0, 1 + X + (1 + (1 + X))) :|: X >= 0, z = X
fact(z) -{ 1 }→ 1 + X :|: X >= 0, z = X
if(z, z', z'') -{ 1 }→ activate(X) :|: z' = X, Y >= 0, z = 1, z'' = Y, X >= 0
if(z, z', z'') -{ 1 }→ activate(Y) :|: z' = X, Y >= 0, z'' = Y, X >= 0, z = 0
if(z, z', z'') -{ 0 }→ 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
p(z) -{ 1 }→ 1 + X :|: X >= 0, z = X
prod(z, z') -{ 1 }→ 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
s(z) -{ 1 }→ 1 + X :|: X >= 0, z = X

Only complete derivations are relevant for the runtime complexity.

(13) CompleteCoflocoProof (EQUIVALENT transformation)

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

eq(start(V, V1, V2),0,[fact(V, Out)],[V >= 0]). eq(start(V, V1, V2),0,[if(V, V1, V2, Out)],[V >= 0,V1 >= 0,V2 >= 0]). eq(start(V, V1, V2),0,[s(V, Out)],[V >= 0]). eq(start(V, V1, V2),0,[fun(Out)],[]). eq(start(V, V1, V2),0,[prod(V, V1, Out)],[V >= 0,V1 >= 0]). eq(start(V, V1, V2),0,[p(V, Out)],[V >= 0]). eq(start(V, V1, V2),0,[activate(V, Out)],[V >= 0]). eq(fact(V, Out),1,[if(1 + X3, 1 + 0, 1 + X3 + (1 + (1 + X3)), Ret)],[Out = Ret,X3 >= 0,V = X3]). eq(if(V, V1, V2, Out),1,[activate(X4, Ret1)],[Out = Ret1,V1 = X4,Y1 >= 0,V = 1,V2 = Y1,X4 >= 0]). eq(if(V, V1, V2, Out),1,[activate(Y2, Ret2)],[Out = Ret2,V1 = X5,Y2 >= 0,V2 = Y2,X5 >= 0,V = 0]). eq(s(V, Out),1,[],[Out = 1 + X6,X6 >= 0,V = X6]). eq(fun(Out),1,[],[Out = 0]). eq(prod(V, V1, Out),1,[],[Out = 1 + X11 + X21,X11 >= 0,X21 >= 0,V = X11,V1 = X21]). eq(fact(V, Out),1,[],[Out = 1 + X7,X7 >= 0,V = X7]). eq(p(V, Out),1,[],[Out = 1 + X8,X8 >= 0,V = X8]). eq(activate(V, Out),1,[activate(X9, Ret0),s(Ret0, Ret3)],[Out = Ret3,V = 1 + X9,X9 >= 0]). eq(activate(V, Out),1,[fun(Ret4)],[Out = Ret4,V = 0]). eq(activate(V, Out),1,[activate(X12, Ret01),activate(X22, Ret11),prod(Ret01, Ret11, Ret5)],[Out = Ret5,X12 >= 0,X22 >= 0,V = 1 + X12 + X22]). eq(activate(V, Out),1,[activate(X10, Ret02),fact(Ret02, Ret6)],[Out = Ret6,V = 1 + X10,X10 >= 0]). eq(activate(V, Out),1,[activate(X13, Ret03),p(Ret03, Ret7)],[Out = Ret7,V = 1 + X13,X13 >= 0]). eq(activate(V, Out),1,[],[Out = X14,X14 >= 0,V = X14]). eq(if(V, V1, V2, Out),0,[],[Out = 0,V3 >= 0,V2 = V4,V5 >= 0,V = V3,V1 = V5,V4 >= 0]). input_output_vars(fact(V,Out),[V],[Out]). input_output_vars(if(V,V1,V2,Out),[V,V1,V2],[Out]). input_output_vars(s(V,Out),[V],[Out]). input_output_vars(fun(Out),[],[Out]). input_output_vars(prod(V,V1,Out),[V,V1],[Out]). input_output_vars(p(V,Out),[V],[Out]). input_output_vars(activate(V,Out),[V],[Out]).

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

#### Computed strongly connected components
0. non_recursive : [fun/1]
1. non_recursive : [p/2]
2. non_recursive : [prod/3]
3. non_recursive : [s/2]
4. recursive [non_tail,multiple] : [activate/2,fact/2,if/4]
5. non_recursive : [start/3]

#### Obtained direct recursion through partial evaluation
0. SCC is completely evaluated into other SCCs
1. SCC is completely evaluated into other SCCs
2. SCC is completely evaluated into other SCCs
3. SCC is completely evaluated into other SCCs
4. SCC is partially evaluated into activate/2
5. SCC is partially evaluated into start/3

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

### Specialization of cost equations activate/2
* CE 11 is refined into CE [14]
* CE 13 is refined into CE [15]
* CE 12 is refined into CE [16]
* CE 9 is refined into CE [17]
* CE 10 is refined into CE [18]
* CE 8 is refined into CE [19]


### Cost equations --> "Loop" of activate/2
* CEs [18] --> Loop 7
* CEs [19] --> Loop 8
* CEs [16] --> Loop 9
* CEs [17] --> Loop 10
* CEs [14,15] --> Loop 11

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

#### Partial ranking functions of CR activate(V,Out)
* Partial RF of phase [7,8,9,10]:
- RF of loop [7:1,8:1,9:1,9:2,10:1]:
V


### Specialization of cost equations start/3
* CE 2 is refined into CE [20]
* CE 3 is refined into CE [21]
* CE 4 is refined into CE [22,23]
* CE 5 is refined into CE [24,25]
* CE 6 is refined into CE [26,27]
* CE 7 is refined into CE [28,29]


### Cost equations --> "Loop" of start/3
* CEs [27,29] --> Loop 12
* CEs [23,25] --> Loop 13
* CEs [20,21,22,24,26,28] --> Loop 14

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

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


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

#### Cost of chains of activate(V,Out):
* Chain [multiple([7,8,9,10],[[],[11]])]...: 6*it(7)+3*it(10)+2*it([11])+0
Such that:aux(1) =< 1
it(10) =< 2*V
aux(2) =< V
it(7) =< aux(2)
it([11]) =< it(10)+it(7)+aux(1)

with precondition: [V>=1]

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


#### Cost of chains of start(V,V1,V2):
* Chain [14]: 4
with precondition: []

* Chain [13]...: 3*s(2)+6*s(4)+2*s(5)+3*s(7)+6*s(9)+2*s(10)+2
Such that:s(7) =< 2
s(3) =< V2
s(2) =< 2*V2
aux(4) =< 1
s(4) =< s(3)
s(5) =< s(2)+s(4)+aux(4)
s(9) =< aux(4)
s(10) =< s(7)+s(9)+aux(4)

with precondition: [V=0]

* Chain [12]...: 3*s(12)+6*s(14)+2*s(15)+3*s(17)+6*s(19)+2*s(20)+1
Such that:s(18) =< V
s(17) =< 2*V
s(13) =< V1
s(12) =< 2*V1
aux(5) =< 1
s(14) =< s(13)
s(15) =< s(12)+s(14)+aux(5)
s(19) =< s(18)
s(20) =< s(17)+s(19)+aux(5)

with precondition: [V>=1]


Closed-form bounds of start(V,V1,V2):
-------------------------------------
* Chain [14] with precondition: []
- Upper bound: 4
- Complexity: constant
* Chain [13]... with precondition: [V=0]
- Upper bound: nat(V2)*8+24+nat(2*V2)*5
- Complexity: n
* Chain [12]... with precondition: [V>=1]
- Upper bound: 8*V+5+nat(V1)*8+10*V+nat(2*V1)*5
- Complexity: n

### Maximum cost of start(V,V1,V2): max([nat(V2)*8+20+nat(2*V2)*5,nat(V)*8+1+nat(V1)*8+nat(2*V)*5+nat(2*V1)*5])+4
Asymptotic class: n
* Total analysis performed in 157 ms.

(14) BOUNDS(1, n^1)