* Step 1: Sum WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f(0(),y,0(),u) -> true()
f(0(),y,s(z),u) -> false()
f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
perfectp(0()) -> false()
perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
- Signature:
{f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
+ Applied Processor:
Sum {left = someStrategy, right = someStrategy}
+ Details:
()
* Step 2: WeightGap WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f(0(),y,0(),u) -> true()
f(0(),y,s(z),u) -> false()
f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
perfectp(0()) -> false()
perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
- Signature:
{f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
+ Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
+ Details:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(if) = {3}
Following symbols are considered usable:
all
TcT has computed the following interpretation:
p(0) = [1]
p(f) = [6] x4 + [6]
p(false) = [0]
p(if) = [1] x1 + [1] x3 + [4]
p(le) = [0]
p(minus) = [4]
p(perfectp) = [8] x1 + [4]
p(s) = [0]
p(true) = [1]
Following rules are strictly oriented:
f(0(),y,0(),u) = [6] u + [6]
> [1]
= true()
f(0(),y,s(z),u) = [6] u + [6]
> [0]
= false()
perfectp(0()) = [12]
> [0]
= false()
Following rules are (at-least) weakly oriented:
f(s(x),0(),z,u) = [6] u + [6]
>= [6] u + [6]
= f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) = [6] u + [6]
>= [6] u + [10]
= if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
perfectp(s(x)) = [4]
>= [6]
= f(x,s(0()),s(x),s(x))
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 3: WeightGap WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
- Weak TRS:
f(0(),y,0(),u) -> true()
f(0(),y,s(z),u) -> false()
perfectp(0()) -> false()
- Signature:
{f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
+ Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
+ Details:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(if) = {3}
Following symbols are considered usable:
all
TcT has computed the following interpretation:
p(0) = [0]
p(f) = [4] x3 + [8]
p(false) = [1]
p(if) = [1] x3 + [12]
p(le) = [1] x2 + [0]
p(minus) = [1] x1 + [5]
p(perfectp) = [8] x1 + [8]
p(s) = [1]
p(true) = [1]
Following rules are strictly oriented:
perfectp(s(x)) = [16]
> [12]
= f(x,s(0()),s(x),s(x))
Following rules are (at-least) weakly oriented:
f(0(),y,0(),u) = [8]
>= [1]
= true()
f(0(),y,s(z),u) = [12]
>= [1]
= false()
f(s(x),0(),z,u) = [4] z + [8]
>= [4] z + [28]
= f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) = [4] z + [8]
>= [4] z + [20]
= if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
perfectp(0()) = [8]
>= [1]
= false()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 4: WeightGap WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
- Weak TRS:
f(0(),y,0(),u) -> true()
f(0(),y,s(z),u) -> false()
perfectp(0()) -> false()
perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
- Signature:
{f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
+ Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny}
+ Details:
The weightgap principle applies using the following nonconstant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(if) = {3}
Following symbols are considered usable:
all
TcT has computed the following interpretation:
p(0) = [0]
p(f) = [2] x1 + [1] x3 + [2]
p(false) = [1]
p(if) = [1] x1 + [1] x3 + [13]
p(le) = [1]
p(minus) = [12]
p(perfectp) = [3] x1 + [1]
p(s) = [1] x1 + [8]
p(true) = [1]
Following rules are strictly oriented:
f(s(x),0(),z,u) = [2] x + [1] z + [18]
> [2] x + [14]
= f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) = [2] x + [1] z + [18]
> [2] x + [1] z + [16]
= if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
Following rules are (at-least) weakly oriented:
f(0(),y,0(),u) = [2]
>= [1]
= true()
f(0(),y,s(z),u) = [1] z + [10]
>= [1]
= false()
perfectp(0()) = [1]
>= [1]
= false()
perfectp(s(x)) = [3] x + [25]
>= [3] x + [10]
= f(x,s(0()),s(x),s(x))
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 5: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
f(0(),y,0(),u) -> true()
f(0(),y,s(z),u) -> false()
f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
perfectp(0()) -> false()
perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
- Signature:
{f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(?,O(n^1))