* Step 1: Bounds WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
f(x,h1(y,z)) -> h2(0(),x,h1(y,z))
f(j(x,y),y) -> g(f(x,k(y)))
g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u))
h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u))
k(h(x)) -> h1(0(),x)
k(h1(x,y)) -> h1(s(x),y)
- Signature:
{f/2,g/1,h2/3,k/1} / {0/0,h/1,h1/2,j/2,s/1}
- Obligation:
runtime complexity wrt. defined symbols {f,g,h2,k} and constructors {0,h,h1,j,s}
+ Applied Processor:
Bounds {initialAutomaton = minimal, enrichment = match}
+ Details:
The problem is match-bounded by 2.
The enriched problem is compatible with follwoing automaton.
0_0() -> 2
0_1() -> 3
0_2() -> 7
f_0(2,2) -> 1
f_1(2,6) -> 5
g_0(2) -> 1
g_1(5) -> 1
g_1(5) -> 5
h_0(2) -> 2
h1_0(2,2) -> 2
h1_1(2,2) -> 4
h1_1(3,2) -> 1
h1_1(3,2) -> 6
h1_2(3,2) -> 8
h2_0(2,2,2) -> 1
h2_1(3,2,4) -> 1
h2_1(3,2,6) -> 5
h2_1(10,2,6) -> 5
h2_2(7,2,8) -> 5
h2_2(9,2,8) -> 1
h2_2(9,2,8) -> 5
j_0(2,2) -> 2
k_0(2) -> 1
k_1(2) -> 6
s_0(2) -> 2
s_1(2) -> 2
s_1(2) -> 3
s_1(3) -> 3
s_1(7) -> 10
s_1(9) -> 3
s_1(10) -> 3
s_2(3) -> 9
s_2(7) -> 9
s_2(9) -> 9
s_2(10) -> 9
* Step 2: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
f(x,h1(y,z)) -> h2(0(),x,h1(y,z))
f(j(x,y),y) -> g(f(x,k(y)))
g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u))
h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u))
k(h(x)) -> h1(0(),x)
k(h1(x,y)) -> h1(s(x),y)
- Signature:
{f/2,g/1,h2/3,k/1} / {0/0,h/1,h1/2,j/2,s/1}
- Obligation:
runtime complexity wrt. defined symbols {f,g,h2,k} and constructors {0,h,h1,j,s}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(?,O(n^1))