* Step 1: Sum WORST_CASE(Omega(n^1),O(n^1))
+ Considered Problem:
- Strict TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
if(false(),X,Y) -> activate(Y)
if(true(),X,Y) -> activate(X)
leq(0(),Y) -> true()
leq(s(X),0()) -> false()
leq(s(X),s(Y)) -> leq(X,Y)
p(X) -> n__p(X)
p(0()) -> 0()
p(s(X)) -> X
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1} / {false/0,n__0/0,n__diff/2,n__p/1,n__s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0,activate,diff,if,leq,p,s} and constructors {false,n__0
,n__diff,n__p,n__s,true}
+ Applied Processor:
Sum {left = someStrategy, right = someStrategy}
+ Details:
()
** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?)
+ Considered Problem:
- Strict TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
if(false(),X,Y) -> activate(Y)
if(true(),X,Y) -> activate(X)
leq(0(),Y) -> true()
leq(s(X),0()) -> false()
leq(s(X),s(Y)) -> leq(X,Y)
p(X) -> n__p(X)
p(0()) -> 0()
p(s(X)) -> X
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1} / {false/0,n__0/0,n__diff/2,n__p/1,n__s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0,activate,diff,if,leq,p,s} and constructors {false,n__0
,n__diff,n__p,n__s,true}
+ Applied Processor:
DecreasingLoops {bound = AnyLoop, narrow = 10}
+ Details:
The system has following decreasing Loops:
activate(x){x -> n__diff(x,y)} =
activate(n__diff(x,y)) ->^+ diff(activate(x),activate(y))
= C[activate(x) = activate(x){}]
** Step 1.b:1: InnermostRuleRemoval WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
if(false(),X,Y) -> activate(Y)
if(true(),X,Y) -> activate(X)
leq(0(),Y) -> true()
leq(s(X),0()) -> false()
leq(s(X),s(Y)) -> leq(X,Y)
p(X) -> n__p(X)
p(0()) -> 0()
p(s(X)) -> X
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1} / {false/0,n__0/0,n__diff/2,n__p/1,n__s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0,activate,diff,if,leq,p,s} and constructors {false,n__0
,n__diff,n__p,n__s,true}
+ Applied Processor:
InnermostRuleRemoval
+ Details:
Arguments of following rules are not normal-forms.
leq(0(),Y) -> true()
leq(s(X),0()) -> false()
leq(s(X),s(Y)) -> leq(X,Y)
p(0()) -> 0()
p(s(X)) -> X
All above mentioned rules can be savely removed.
** Step 1.b:2: DependencyPairs WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
if(false(),X,Y) -> activate(Y)
if(true(),X,Y) -> activate(X)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1} / {false/0,n__0/0,n__diff/2,n__p/1,n__s/1,true/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0,activate,diff,if,leq,p,s} and constructors {false,n__0
,n__diff,n__p,n__s,true}
+ Applied Processor:
DependencyPairs {dpKind_ = WIDP}
+ Details:
We add the following weak innermost dependency pairs:
Strict DPs
0#() -> c_1()
activate#(X) -> c_2()
activate#(n__0()) -> c_3(0#())
activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) -> c_5(p#(activate(X)))
activate#(n__s(X)) -> c_6(s#(activate(X)))
diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) -> c_8()
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
p#(X) -> c_11()
s#(X) -> c_12()
Weak DPs
and mark the set of starting terms.
** Step 1.b:3: UsableRules WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
0#() -> c_1()
activate#(X) -> c_2()
activate#(n__0()) -> c_3(0#())
activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) -> c_5(p#(activate(X)))
activate#(n__s(X)) -> c_6(s#(activate(X)))
diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) -> c_8()
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
p#(X) -> c_11()
s#(X) -> c_12()
- Strict TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
if(false(),X,Y) -> activate(Y)
if(true(),X,Y) -> activate(X)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
UsableRules
+ Details:
We replace rewrite rules by usable rules:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
0#() -> c_1()
activate#(X) -> c_2()
activate#(n__0()) -> c_3(0#())
activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) -> c_5(p#(activate(X)))
activate#(n__s(X)) -> c_6(s#(activate(X)))
diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) -> c_8()
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
p#(X) -> c_11()
s#(X) -> c_12()
** Step 1.b:4: WeightGap WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
0#() -> c_1()
activate#(X) -> c_2()
activate#(n__0()) -> c_3(0#())
activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) -> c_5(p#(activate(X)))
activate#(n__s(X)) -> c_6(s#(activate(X)))
diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) -> c_8()
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
p#(X) -> c_11()
s#(X) -> c_12()
- Strict TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnTrs}
+ Details:
The weightgap principle applies using the following constant growth matrix-interpretation:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(diff) = {1,2},
uargs(p) = {1},
uargs(s) = {1},
uargs(diff#) = {1,2},
uargs(p#) = {1},
uargs(s#) = {1},
uargs(c_3) = {1},
uargs(c_4) = {1},
uargs(c_5) = {1},
uargs(c_6) = {1},
uargs(c_9) = {1},
uargs(c_10) = {1}
Following symbols are considered usable:
all
TcT has computed the following interpretation:
p(0) = [2]
p(activate) = [3] x1 + [1]
p(diff) = [1] x1 + [1] x2 + [3]
p(false) = [0]
p(if) = [0]
p(leq) = [4]
p(n__0) = [1]
p(n__diff) = [1] x1 + [1] x2 + [2]
p(n__p) = [1] x1 + [1]
p(n__s) = [1] x1 + [1]
p(p) = [1] x1 + [2]
p(s) = [1] x1 + [2]
p(true) = [1]
p(0#) = [3]
p(activate#) = [3] x1 + [6]
p(diff#) = [1] x1 + [1] x2 + [7]
p(if#) = [3] x2 + [3] x3 + [0]
p(leq#) = [2] x2 + [0]
p(p#) = [1] x1 + [0]
p(s#) = [1] x1 + [3]
p(c_1) = [0]
p(c_2) = [2]
p(c_3) = [1] x1 + [6]
p(c_4) = [1] x1 + [2]
p(c_5) = [1] x1 + [3]
p(c_6) = [1] x1 + [2]
p(c_7) = [3]
p(c_8) = [0]
p(c_9) = [1] x1 + [6]
p(c_10) = [1] x1 + [3]
p(c_11) = [1]
p(c_12) = [1]
Following rules are strictly oriented:
0#() = [3]
> [0]
= c_1()
activate#(X) = [3] X + [6]
> [2]
= c_2()
activate#(n__diff(X1,X2)) = [3] X1 + [3] X2 + [12]
> [3] X1 + [3] X2 + [11]
= c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) = [3] X + [9]
> [3] X + [4]
= c_5(p#(activate(X)))
activate#(n__s(X)) = [3] X + [9]
> [3] X + [6]
= c_6(s#(activate(X)))
diff#(X,Y) = [1] X + [1] Y + [7]
> [3]
= c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) = [1] X1 + [1] X2 + [7]
> [0]
= c_8()
s#(X) = [1] X + [3]
> [1]
= c_12()
0() = [2]
> [1]
= n__0()
activate(X) = [3] X + [1]
> [1] X + [0]
= X
activate(n__0()) = [4]
> [2]
= 0()
activate(n__diff(X1,X2)) = [3] X1 + [3] X2 + [7]
> [3] X1 + [3] X2 + [5]
= diff(activate(X1),activate(X2))
activate(n__p(X)) = [3] X + [4]
> [3] X + [3]
= p(activate(X))
activate(n__s(X)) = [3] X + [4]
> [3] X + [3]
= s(activate(X))
diff(X,Y) = [1] X + [1] Y + [3]
> [0]
= if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) = [1] X1 + [1] X2 + [3]
> [1] X1 + [1] X2 + [2]
= n__diff(X1,X2)
p(X) = [1] X + [2]
> [1] X + [1]
= n__p(X)
s(X) = [1] X + [2]
> [1] X + [1]
= n__s(X)
Following rules are (at-least) weakly oriented:
activate#(n__0()) = [9]
>= [9]
= c_3(0#())
if#(false(),X,Y) = [3] X + [3] Y + [0]
>= [3] Y + [12]
= c_9(activate#(Y))
if#(true(),X,Y) = [3] X + [3] Y + [0]
>= [3] X + [9]
= c_10(activate#(X))
p#(X) = [1] X + [0]
>= [1]
= c_11()
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
** Step 1.b:5: PredecessorEstimation WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
activate#(n__0()) -> c_3(0#())
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
p#(X) -> c_11()
- Weak DPs:
0#() -> c_1()
activate#(X) -> c_2()
activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) -> c_5(p#(activate(X)))
activate#(n__s(X)) -> c_6(s#(activate(X)))
diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) -> c_8()
s#(X) -> c_12()
- Weak TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{1}
by application of
Pre({1}) = {2,3}.
Here rules are labelled as follows:
1: activate#(n__0()) -> c_3(0#())
2: if#(false(),X,Y) -> c_9(activate#(Y))
3: if#(true(),X,Y) -> c_10(activate#(X))
4: p#(X) -> c_11()
5: 0#() -> c_1()
6: activate#(X) -> c_2()
7: activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
8: activate#(n__p(X)) -> c_5(p#(activate(X)))
9: activate#(n__s(X)) -> c_6(s#(activate(X)))
10: diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
11: diff#(X1,X2) -> c_8()
12: s#(X) -> c_12()
** Step 1.b:6: PredecessorEstimation WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
p#(X) -> c_11()
- Weak DPs:
0#() -> c_1()
activate#(X) -> c_2()
activate#(n__0()) -> c_3(0#())
activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) -> c_5(p#(activate(X)))
activate#(n__s(X)) -> c_6(s#(activate(X)))
diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) -> c_8()
s#(X) -> c_12()
- Weak TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{1,2}
by application of
Pre({1,2}) = {}.
Here rules are labelled as follows:
1: if#(false(),X,Y) -> c_9(activate#(Y))
2: if#(true(),X,Y) -> c_10(activate#(X))
3: p#(X) -> c_11()
4: 0#() -> c_1()
5: activate#(X) -> c_2()
6: activate#(n__0()) -> c_3(0#())
7: activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
8: activate#(n__p(X)) -> c_5(p#(activate(X)))
9: activate#(n__s(X)) -> c_6(s#(activate(X)))
10: diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
11: diff#(X1,X2) -> c_8()
12: s#(X) -> c_12()
** Step 1.b:7: RemoveWeakSuffixes WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
p#(X) -> c_11()
- Weak DPs:
0#() -> c_1()
activate#(X) -> c_2()
activate#(n__0()) -> c_3(0#())
activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
activate#(n__p(X)) -> c_5(p#(activate(X)))
activate#(n__s(X)) -> c_6(s#(activate(X)))
diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
diff#(X1,X2) -> c_8()
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
s#(X) -> c_12()
- Weak TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
RemoveWeakSuffixes
+ Details:
Consider the dependency graph
1:S:p#(X) -> c_11()
2:W:0#() -> c_1()
3:W:activate#(X) -> c_2()
4:W:activate#(n__0()) -> c_3(0#())
-->_1 0#() -> c_1():2
5:W:activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
-->_1 diff#(X1,X2) -> c_8():9
-->_1 diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))):8
6:W:activate#(n__p(X)) -> c_5(p#(activate(X)))
-->_1 p#(X) -> c_11():1
7:W:activate#(n__s(X)) -> c_6(s#(activate(X)))
-->_1 s#(X) -> c_12():12
8:W:diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
9:W:diff#(X1,X2) -> c_8()
10:W:if#(false(),X,Y) -> c_9(activate#(Y))
-->_1 activate#(n__s(X)) -> c_6(s#(activate(X))):7
-->_1 activate#(n__p(X)) -> c_5(p#(activate(X))):6
-->_1 activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2))):5
-->_1 activate#(n__0()) -> c_3(0#()):4
-->_1 activate#(X) -> c_2():3
11:W:if#(true(),X,Y) -> c_10(activate#(X))
-->_1 activate#(n__s(X)) -> c_6(s#(activate(X))):7
-->_1 activate#(n__p(X)) -> c_5(p#(activate(X))):6
-->_1 activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2))):5
-->_1 activate#(n__0()) -> c_3(0#()):4
-->_1 activate#(X) -> c_2():3
12:W:s#(X) -> c_12()
The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed.
7: activate#(n__s(X)) -> c_6(s#(activate(X)))
12: s#(X) -> c_12()
5: activate#(n__diff(X1,X2)) -> c_4(diff#(activate(X1),activate(X2)))
8: diff#(X,Y) -> c_7(if#(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y))))
9: diff#(X1,X2) -> c_8()
4: activate#(n__0()) -> c_3(0#())
3: activate#(X) -> c_2()
2: 0#() -> c_1()
** Step 1.b:8: RemoveHeads WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
p#(X) -> c_11()
- Weak DPs:
activate#(n__p(X)) -> c_5(p#(activate(X)))
if#(false(),X,Y) -> c_9(activate#(Y))
if#(true(),X,Y) -> c_10(activate#(X))
- Weak TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
RemoveHeads
+ Details:
Consider the dependency graph
1:S:p#(X) -> c_11()
6:W:activate#(n__p(X)) -> c_5(p#(activate(X)))
-->_1 p#(X) -> c_11():1
10:W:if#(false(),X,Y) -> c_9(activate#(Y))
-->_1 activate#(n__p(X)) -> c_5(p#(activate(X))):6
11:W:if#(true(),X,Y) -> c_10(activate#(X))
-->_1 activate#(n__p(X)) -> c_5(p#(activate(X))):6
Following roots of the dependency graph are removed, as the considered set of starting terms is closed under reduction with respect to these rules (modulo compound contexts).
[(10,if#(false(),X,Y) -> c_9(activate#(Y))),(11,if#(true(),X,Y) -> c_10(activate#(X)))]
** Step 1.b:9: Trivial WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
p#(X) -> c_11()
- Weak DPs:
activate#(n__p(X)) -> c_5(p#(activate(X)))
- Weak TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
Trivial
+ Details:
Consider the dependency graph
1:S:p#(X) -> c_11()
6:W:activate#(n__p(X)) -> c_5(p#(activate(X)))
-->_1 p#(X) -> c_11():1
The dependency graph contains no loops, we remove all dependency pairs.
** Step 1.b:10: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
0() -> n__0()
activate(X) -> X
activate(n__0()) -> 0()
activate(n__diff(X1,X2)) -> diff(activate(X1),activate(X2))
activate(n__p(X)) -> p(activate(X))
activate(n__s(X)) -> s(activate(X))
diff(X,Y) -> if(leq(X,Y),n__0(),n__s(n__diff(n__p(X),Y)))
diff(X1,X2) -> n__diff(X1,X2)
p(X) -> n__p(X)
s(X) -> n__s(X)
- Signature:
{0/0,activate/1,diff/2,if/3,leq/2,p/1,s/1,0#/0,activate#/1,diff#/2,if#/3,leq#/2,p#/1,s#/1} / {false/0,n__0/0
,n__diff/2,n__p/1,n__s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/1,c_5/1,c_6/1,c_7/1,c_8/0,c_9/1,c_10/1,c_11/0,c_12/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {0#,activate#,diff#,if#,leq#,p#
,s#} and constructors {false,n__0,n__diff,n__p,n__s,true}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(Omega(n^1),O(n^1))