WORST_CASE(?,O(n^1))
* Step 1: Sum WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) -> 0()
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) -> 0()
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
Sum {left = someStrategy, right = someStrategy}
+ Details:
()
* Step 2: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) -> 0()
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) -> 0()
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 0
p(S) = 0
p(f0) = 2
p(f1) = 2 + 2*x2
p(f2) = 2 + 2*x1
p(f3) = 2
p(f4) = 2
p(f5) = 2 + x1 + x3
p(f6) = 2 + x3
Following rules are strictly oriented:
f0(x1,0(),x3,x4,x5) = 2
> 0
= 0()
f0(x1,S(x),x3,0(),x5) = 2
> 0
= 0()
f1(x1,x2,x3,x4,0()) = 2 + 2*x2
> 0
= 0()
f2(x1,x2,0(),x4,x5) = 2 + 2*x1
> 0
= 0()
f2(x1,x2,S(x),0(),0()) = 2 + 2*x1
> 0
= 0()
f2(x1,x2,S(x'),S(x),0()) = 2 + 2*x1
> 0
= 0()
f3(x1,x2,x3,x4,0()) = 2
> 0
= 0()
f4(0(),x2,x3,x4,x5) = 2
> 0
= 0()
f4(S(x),0(),x3,x4,0()) = 2
> 0
= 0()
f4(S(x'),S(x),x3,x4,0()) = 2
> 0
= 0()
f5(x1,x2,x3,x4,0()) = 2 + x1 + x3
> 0
= 0()
f6(x1,x2,x3,x4,0()) = 2 + x3
> 0
= 0()
Following rules are (at-least) weakly oriented:
f0(x1,S(x'),x3,S(x),x5) = 2
>= 2
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,S(x)) = 2 + 2*x2
>= 2 + 2*x2
= f2(x2,x1,x3,x4,x)
f2(x1,x2,S(x'),0(),S(x)) = 2 + 2*x1
>= 2
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x''),S(x'),S(x)) = 2 + 2*x1
>= 2 + x1
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,S(x)) = 2
>= 2
= f4(x1,x2,x4,x3,x)
f4(S(x'),0(),x3,x4,S(x)) = 2
>= 2
= f3(x',0(),x3,x4,x)
f4(S(x''),S(x'),x3,x4,S(x)) = 2
>= 2
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,S(x)) = 2 + x1 + x3
>= 2 + x3
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) = 2 + x3
>= 2
= f0(x1,x2,x4,x3,x)
* Step 3: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f1(x1,x2,x3,x4,0()) -> 0()
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),S(x),0()) -> 0()
f3(x1,x2,x3,x4,0()) -> 0()
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),S(x),x3,x4,0()) -> 0()
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 0
p(S) = 4 + x1
p(f0) = 2*x4
p(f1) = 2*x3
p(f2) = 2*x3
p(f3) = 2*x3 + 2*x4
p(f4) = 2*x3 + 2*x4
p(f5) = 2*x3
p(f6) = 2*x3
Following rules are strictly oriented:
f0(x1,S(x'),x3,S(x),x5) = 8 + 2*x
> 2*x
= f1(x',S(x'),x,S(x),S(x))
f2(x1,x2,S(x'),0(),S(x)) = 8 + 2*x'
> 2*x'
= f3(x1,x2,x',0(),x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 2*x4
>= 0
= 0()
f0(x1,S(x),x3,0(),x5) = 0
>= 0
= 0()
f1(x1,x2,x3,x4,0()) = 2*x3
>= 0
= 0()
f1(x1,x2,x3,x4,S(x)) = 2*x3
>= 2*x3
= f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) = 0
>= 0
= 0()
f2(x1,x2,S(x),0(),0()) = 8 + 2*x
>= 0
= 0()
f2(x1,x2,S(x'),S(x),0()) = 8 + 2*x'
>= 0
= 0()
f2(x1,x2,S(x''),S(x'),S(x)) = 8 + 2*x''
>= 8 + 2*x''
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) = 2*x3 + 2*x4
>= 0
= 0()
f3(x1,x2,x3,x4,S(x)) = 2*x3 + 2*x4
>= 2*x3 + 2*x4
= f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) = 2*x3 + 2*x4
>= 0
= 0()
f4(S(x),0(),x3,x4,0()) = 2*x3 + 2*x4
>= 0
= 0()
f4(S(x'),0(),x3,x4,S(x)) = 2*x3 + 2*x4
>= 2*x3 + 2*x4
= f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) = 2*x3 + 2*x4
>= 0
= 0()
f4(S(x''),S(x'),x3,x4,S(x)) = 2*x3 + 2*x4
>= 2*x3
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) = 2*x3
>= 0
= 0()
f5(x1,x2,x3,x4,S(x)) = 2*x3
>= 2*x3
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) = 2*x3
>= 0
= 0()
f6(x1,x2,x3,x4,S(x)) = 2*x3
>= 2*x3
= f0(x1,x2,x4,x3,x)
* Step 4: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f3(x1,x2,x3,x4,0()) -> 0()
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),S(x),x3,x4,0()) -> 0()
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 2
p(S) = 4 + x1
p(f0) = 3 + 2*x2
p(f1) = 3 + 2*x2
p(f2) = 3 + 2*x1
p(f3) = 3 + 2*x1
p(f4) = 3 + 2*x1
p(f5) = 3 + 2*x1
p(f6) = 3 + 2*x2
Following rules are strictly oriented:
f4(S(x'),0(),x3,x4,S(x)) = 11 + 2*x'
> 3 + 2*x'
= f3(x',0(),x3,x4,x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 7
>= 2
= 0()
f0(x1,S(x),x3,0(),x5) = 11 + 2*x
>= 2
= 0()
f0(x1,S(x'),x3,S(x),x5) = 11 + 2*x'
>= 11 + 2*x'
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) = 3 + 2*x2
>= 2
= 0()
f1(x1,x2,x3,x4,S(x)) = 3 + 2*x2
>= 3 + 2*x2
= f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) = 3 + 2*x1
>= 2
= 0()
f2(x1,x2,S(x),0(),0()) = 3 + 2*x1
>= 2
= 0()
f2(x1,x2,S(x'),0(),S(x)) = 3 + 2*x1
>= 3 + 2*x1
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) = 3 + 2*x1
>= 2
= 0()
f2(x1,x2,S(x''),S(x'),S(x)) = 3 + 2*x1
>= 3 + 2*x1
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) = 3 + 2*x1
>= 2
= 0()
f3(x1,x2,x3,x4,S(x)) = 3 + 2*x1
>= 3 + 2*x1
= f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) = 7
>= 2
= 0()
f4(S(x),0(),x3,x4,0()) = 11 + 2*x
>= 2
= 0()
f4(S(x'),S(x),x3,x4,0()) = 11 + 2*x'
>= 2
= 0()
f4(S(x''),S(x'),x3,x4,S(x)) = 11 + 2*x''
>= 11 + 2*x''
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) = 3 + 2*x1
>= 2
= 0()
f5(x1,x2,x3,x4,S(x)) = 3 + 2*x1
>= 3 + 2*x1
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) = 3 + 2*x2
>= 2
= 0()
f6(x1,x2,x3,x4,S(x)) = 3 + 2*x2
>= 3 + 2*x2
= f0(x1,x2,x4,x3,x)
* Step 5: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f3(x1,x2,x3,x4,0()) -> 0()
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 0
p(S) = 1 + x1
p(f0) = 4*x4
p(f1) = 4 + 4*x3
p(f2) = 4*x3
p(f3) = 4*x3 + 4*x4
p(f4) = 4*x3 + 4*x4
p(f5) = 4*x3
p(f6) = 4*x3
Following rules are strictly oriented:
f1(x1,x2,x3,x4,S(x)) = 4 + 4*x3
> 4*x3
= f2(x2,x1,x3,x4,x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 4*x4
>= 0
= 0()
f0(x1,S(x),x3,0(),x5) = 0
>= 0
= 0()
f0(x1,S(x'),x3,S(x),x5) = 4 + 4*x
>= 4 + 4*x
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) = 4 + 4*x3
>= 0
= 0()
f2(x1,x2,0(),x4,x5) = 0
>= 0
= 0()
f2(x1,x2,S(x),0(),0()) = 4 + 4*x
>= 0
= 0()
f2(x1,x2,S(x'),0(),S(x)) = 4 + 4*x'
>= 4*x'
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) = 4 + 4*x'
>= 0
= 0()
f2(x1,x2,S(x''),S(x'),S(x)) = 4 + 4*x''
>= 4 + 4*x''
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) = 4*x3 + 4*x4
>= 0
= 0()
f3(x1,x2,x3,x4,S(x)) = 4*x3 + 4*x4
>= 4*x3 + 4*x4
= f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) = 4*x3 + 4*x4
>= 0
= 0()
f4(S(x),0(),x3,x4,0()) = 4*x3 + 4*x4
>= 0
= 0()
f4(S(x'),0(),x3,x4,S(x)) = 4*x3 + 4*x4
>= 4*x3 + 4*x4
= f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) = 4*x3 + 4*x4
>= 0
= 0()
f4(S(x''),S(x'),x3,x4,S(x)) = 4*x3 + 4*x4
>= 4*x3
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) = 4*x3
>= 0
= 0()
f5(x1,x2,x3,x4,S(x)) = 4*x3
>= 4*x3
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) = 4*x3
>= 0
= 0()
f6(x1,x2,x3,x4,S(x)) = 4*x3
>= 4*x3
= f0(x1,x2,x4,x3,x)
* Step 6: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f3(x1,x2,x3,x4,0()) -> 0()
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 0
p(S) = 2 + x1
p(f0) = 4*x4
p(f1) = 4*x3
p(f2) = 4*x3
p(f3) = 6 + 4*x3 + 4*x4
p(f4) = 6 + 4*x3 + 4*x4
p(f5) = 4*x3
p(f6) = 4*x3
Following rules are strictly oriented:
f4(S(x''),S(x'),x3,x4,S(x)) = 6 + 4*x3 + 4*x4
> 4*x3
= f2(S(x''),x',x3,x4,x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 4*x4
>= 0
= 0()
f0(x1,S(x),x3,0(),x5) = 0
>= 0
= 0()
f0(x1,S(x'),x3,S(x),x5) = 8 + 4*x
>= 4*x
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) = 4*x3
>= 0
= 0()
f1(x1,x2,x3,x4,S(x)) = 4*x3
>= 4*x3
= f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) = 0
>= 0
= 0()
f2(x1,x2,S(x),0(),0()) = 8 + 4*x
>= 0
= 0()
f2(x1,x2,S(x'),0(),S(x)) = 8 + 4*x'
>= 6 + 4*x'
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) = 8 + 4*x'
>= 0
= 0()
f2(x1,x2,S(x''),S(x'),S(x)) = 8 + 4*x''
>= 8 + 4*x''
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) = 6 + 4*x3 + 4*x4
>= 0
= 0()
f3(x1,x2,x3,x4,S(x)) = 6 + 4*x3 + 4*x4
>= 6 + 4*x3 + 4*x4
= f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) = 6 + 4*x3 + 4*x4
>= 0
= 0()
f4(S(x),0(),x3,x4,0()) = 6 + 4*x3 + 4*x4
>= 0
= 0()
f4(S(x'),0(),x3,x4,S(x)) = 6 + 4*x3 + 4*x4
>= 6 + 4*x3 + 4*x4
= f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) = 6 + 4*x3 + 4*x4
>= 0
= 0()
f5(x1,x2,x3,x4,0()) = 4*x3
>= 0
= 0()
f5(x1,x2,x3,x4,S(x)) = 4*x3
>= 4*x3
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) = 4*x3
>= 0
= 0()
f6(x1,x2,x3,x4,S(x)) = 4*x3
>= 4*x3
= f0(x1,x2,x4,x3,x)
* Step 7: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f3(x1,x2,x3,x4,0()) -> 0()
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 2
p(S) = 2 + x1
p(f0) = 2 + 4*x4
p(f1) = 4 + 4*x3
p(f2) = 3 + 4*x3
p(f3) = 3 + 4*x3 + 4*x4
p(f4) = 3 + 4*x3 + 4*x4
p(f5) = 2 + 4*x3
p(f6) = 2 + 4*x3
Following rules are strictly oriented:
f2(x1,x2,S(x''),S(x'),S(x)) = 11 + 4*x''
> 10 + 4*x''
= f5(x1,x2,S(x''),x',x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 2 + 4*x4
>= 2
= 0()
f0(x1,S(x),x3,0(),x5) = 10
>= 2
= 0()
f0(x1,S(x'),x3,S(x),x5) = 10 + 4*x
>= 4 + 4*x
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) = 4 + 4*x3
>= 2
= 0()
f1(x1,x2,x3,x4,S(x)) = 4 + 4*x3
>= 3 + 4*x3
= f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) = 11
>= 2
= 0()
f2(x1,x2,S(x),0(),0()) = 11 + 4*x
>= 2
= 0()
f2(x1,x2,S(x'),0(),S(x)) = 11 + 4*x'
>= 11 + 4*x'
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) = 11 + 4*x'
>= 2
= 0()
f3(x1,x2,x3,x4,0()) = 3 + 4*x3 + 4*x4
>= 2
= 0()
f3(x1,x2,x3,x4,S(x)) = 3 + 4*x3 + 4*x4
>= 3 + 4*x3 + 4*x4
= f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) = 3 + 4*x3 + 4*x4
>= 2
= 0()
f4(S(x),0(),x3,x4,0()) = 3 + 4*x3 + 4*x4
>= 2
= 0()
f4(S(x'),0(),x3,x4,S(x)) = 3 + 4*x3 + 4*x4
>= 3 + 4*x3 + 4*x4
= f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) = 3 + 4*x3 + 4*x4
>= 2
= 0()
f4(S(x''),S(x'),x3,x4,S(x)) = 3 + 4*x3 + 4*x4
>= 3 + 4*x3
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) = 2 + 4*x3
>= 2
= 0()
f5(x1,x2,x3,x4,S(x)) = 2 + 4*x3
>= 2 + 4*x3
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) = 2 + 4*x3
>= 2
= 0()
f6(x1,x2,x3,x4,S(x)) = 2 + 4*x3
>= 2 + 4*x3
= f0(x1,x2,x4,x3,x)
* Step 8: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) -> 0()
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 0
p(S) = 1 + x1
p(f0) = 4*x2 + 4*x4
p(f1) = 4*x2 + 4*x3
p(f2) = 4*x1 + 4*x3
p(f3) = 4 + 4*x1 + 4*x3 + 4*x4
p(f4) = 4*x1 + 4*x3 + 4*x4
p(f5) = 4*x1 + 4*x3
p(f6) = 4*x2 + 4*x3
Following rules are strictly oriented:
f3(x1,x2,x3,x4,S(x)) = 4 + 4*x1 + 4*x3 + 4*x4
> 4*x1 + 4*x3 + 4*x4
= f4(x1,x2,x4,x3,x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 4*x4
>= 0
= 0()
f0(x1,S(x),x3,0(),x5) = 4 + 4*x
>= 0
= 0()
f0(x1,S(x'),x3,S(x),x5) = 8 + 4*x + 4*x'
>= 4 + 4*x + 4*x'
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) = 4*x2 + 4*x3
>= 0
= 0()
f1(x1,x2,x3,x4,S(x)) = 4*x2 + 4*x3
>= 4*x2 + 4*x3
= f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) = 4*x1
>= 0
= 0()
f2(x1,x2,S(x),0(),0()) = 4 + 4*x + 4*x1
>= 0
= 0()
f2(x1,x2,S(x'),0(),S(x)) = 4 + 4*x' + 4*x1
>= 4 + 4*x' + 4*x1
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) = 4 + 4*x' + 4*x1
>= 0
= 0()
f2(x1,x2,S(x''),S(x'),S(x)) = 4 + 4*x'' + 4*x1
>= 4 + 4*x'' + 4*x1
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) = 4 + 4*x1 + 4*x3 + 4*x4
>= 0
= 0()
f4(0(),x2,x3,x4,x5) = 4*x3 + 4*x4
>= 0
= 0()
f4(S(x),0(),x3,x4,0()) = 4 + 4*x + 4*x3 + 4*x4
>= 0
= 0()
f4(S(x'),0(),x3,x4,S(x)) = 4 + 4*x' + 4*x3 + 4*x4
>= 4 + 4*x' + 4*x3 + 4*x4
= f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) = 4 + 4*x' + 4*x3 + 4*x4
>= 0
= 0()
f4(S(x''),S(x'),x3,x4,S(x)) = 4 + 4*x'' + 4*x3 + 4*x4
>= 4 + 4*x'' + 4*x3
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) = 4*x1 + 4*x3
>= 0
= 0()
f5(x1,x2,x3,x4,S(x)) = 4*x1 + 4*x3
>= 4*x1 + 4*x3
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) = 4*x2 + 4*x3
>= 0
= 0()
f6(x1,x2,x3,x4,S(x)) = 4*x2 + 4*x3
>= 4*x2 + 4*x3
= f0(x1,x2,x4,x3,x)
* Step 9: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) -> 0()
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 0
p(S) = 1 + x1
p(f0) = 3 + x4
p(f1) = 4 + x3
p(f2) = 4 + x3
p(f3) = 4 + x3 + x4
p(f4) = 4 + x3 + x4
p(f5) = 4 + x3
p(f6) = 4 + x3
Following rules are strictly oriented:
f6(x1,x2,x3,x4,S(x)) = 4 + x3
> 3 + x3
= f0(x1,x2,x4,x3,x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 3 + x4
>= 0
= 0()
f0(x1,S(x),x3,0(),x5) = 3
>= 0
= 0()
f0(x1,S(x'),x3,S(x),x5) = 4 + x
>= 4 + x
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) = 4 + x3
>= 0
= 0()
f1(x1,x2,x3,x4,S(x)) = 4 + x3
>= 4 + x3
= f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) = 4
>= 0
= 0()
f2(x1,x2,S(x),0(),0()) = 5 + x
>= 0
= 0()
f2(x1,x2,S(x'),0(),S(x)) = 5 + x'
>= 4 + x'
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) = 5 + x'
>= 0
= 0()
f2(x1,x2,S(x''),S(x'),S(x)) = 5 + x''
>= 5 + x''
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) = 4 + x3 + x4
>= 0
= 0()
f3(x1,x2,x3,x4,S(x)) = 4 + x3 + x4
>= 4 + x3 + x4
= f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) = 4 + x3 + x4
>= 0
= 0()
f4(S(x),0(),x3,x4,0()) = 4 + x3 + x4
>= 0
= 0()
f4(S(x'),0(),x3,x4,S(x)) = 4 + x3 + x4
>= 4 + x3 + x4
= f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) = 4 + x3 + x4
>= 0
= 0()
f4(S(x''),S(x'),x3,x4,S(x)) = 4 + x3 + x4
>= 4 + x3
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) = 4 + x3
>= 0
= 0()
f5(x1,x2,x3,x4,S(x)) = 4 + x3
>= 4 + x3
= f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) = 4 + x3
>= 0
= 0()
* Step 10: NaturalPI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) -> 0()
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules}
+ Details:
We apply a polynomial interpretation of kind constructor-based(linear):
The following argument positions are considered usable:
none
Following symbols are considered usable:
{f0,f1,f2,f3,f4,f5,f6}
TcT has computed the following interpretation:
p(0) = 0
p(S) = 2 + x1
p(f0) = 2*x4
p(f1) = 1 + 2*x3
p(f2) = 1 + 2*x3
p(f3) = 4 + 2*x3 + 2*x4
p(f4) = 4 + 2*x3 + 2*x4
p(f5) = 1 + 2*x3
p(f6) = 2*x3
Following rules are strictly oriented:
f5(x1,x2,x3,x4,S(x)) = 1 + 2*x3
> 2*x3
= f6(x2,x1,x3,x4,x)
Following rules are (at-least) weakly oriented:
f0(x1,0(),x3,x4,x5) = 2*x4
>= 0
= 0()
f0(x1,S(x),x3,0(),x5) = 0
>= 0
= 0()
f0(x1,S(x'),x3,S(x),x5) = 4 + 2*x
>= 1 + 2*x
= f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) = 1 + 2*x3
>= 0
= 0()
f1(x1,x2,x3,x4,S(x)) = 1 + 2*x3
>= 1 + 2*x3
= f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) = 1
>= 0
= 0()
f2(x1,x2,S(x),0(),0()) = 5 + 2*x
>= 0
= 0()
f2(x1,x2,S(x'),0(),S(x)) = 5 + 2*x'
>= 4 + 2*x'
= f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) = 5 + 2*x'
>= 0
= 0()
f2(x1,x2,S(x''),S(x'),S(x)) = 5 + 2*x''
>= 5 + 2*x''
= f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) = 4 + 2*x3 + 2*x4
>= 0
= 0()
f3(x1,x2,x3,x4,S(x)) = 4 + 2*x3 + 2*x4
>= 4 + 2*x3 + 2*x4
= f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) = 4 + 2*x3 + 2*x4
>= 0
= 0()
f4(S(x),0(),x3,x4,0()) = 4 + 2*x3 + 2*x4
>= 0
= 0()
f4(S(x'),0(),x3,x4,S(x)) = 4 + 2*x3 + 2*x4
>= 4 + 2*x3 + 2*x4
= f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) = 4 + 2*x3 + 2*x4
>= 0
= 0()
f4(S(x''),S(x'),x3,x4,S(x)) = 4 + 2*x3 + 2*x4
>= 1 + 2*x3
= f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) = 1 + 2*x3
>= 0
= 0()
f6(x1,x2,x3,x4,0()) = 2*x3
>= 0
= 0()
f6(x1,x2,x3,x4,S(x)) = 2*x3
>= 2*x3
= f0(x1,x2,x4,x3,x)
* Step 11: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
f0(x1,0(),x3,x4,x5) -> 0()
f0(x1,S(x),x3,0(),x5) -> 0()
f0(x1,S(x'),x3,S(x),x5) -> f1(x',S(x'),x,S(x),S(x))
f1(x1,x2,x3,x4,0()) -> 0()
f1(x1,x2,x3,x4,S(x)) -> f2(x2,x1,x3,x4,x)
f2(x1,x2,0(),x4,x5) -> 0()
f2(x1,x2,S(x),0(),0()) -> 0()
f2(x1,x2,S(x'),0(),S(x)) -> f3(x1,x2,x',0(),x)
f2(x1,x2,S(x'),S(x),0()) -> 0()
f2(x1,x2,S(x''),S(x'),S(x)) -> f5(x1,x2,S(x''),x',x)
f3(x1,x2,x3,x4,0()) -> 0()
f3(x1,x2,x3,x4,S(x)) -> f4(x1,x2,x4,x3,x)
f4(0(),x2,x3,x4,x5) -> 0()
f4(S(x),0(),x3,x4,0()) -> 0()
f4(S(x'),0(),x3,x4,S(x)) -> f3(x',0(),x3,x4,x)
f4(S(x'),S(x),x3,x4,0()) -> 0()
f4(S(x''),S(x'),x3,x4,S(x)) -> f2(S(x''),x',x3,x4,x)
f5(x1,x2,x3,x4,0()) -> 0()
f5(x1,x2,x3,x4,S(x)) -> f6(x2,x1,x3,x4,x)
f6(x1,x2,x3,x4,0()) -> 0()
f6(x1,x2,x3,x4,S(x)) -> f0(x1,x2,x4,x3,x)
- Signature:
{f0/5,f1/5,f2/5,f3/5,f4/5,f5/5,f6/5} / {0/0,S/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {f0,f1,f2,f3,f4,f5,f6} and constructors {0,S}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(?,O(n^1))