* Step 1: Bounds WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
active(c(X)) -> mark(d(X))
active(f(X)) -> f(active(X))
active(f(f(X))) -> mark(c(f(g(f(X)))))
active(h(X)) -> h(active(X))
active(h(X)) -> mark(c(d(X)))
c(ok(X)) -> ok(c(X))
d(ok(X)) -> ok(d(X))
f(mark(X)) -> mark(f(X))
f(ok(X)) -> ok(f(X))
g(ok(X)) -> ok(g(X))
h(mark(X)) -> mark(h(X))
h(ok(X)) -> ok(h(X))
proper(c(X)) -> c(proper(X))
proper(d(X)) -> d(proper(X))
proper(f(X)) -> f(proper(X))
proper(g(X)) -> g(proper(X))
proper(h(X)) -> h(proper(X))
top(mark(X)) -> top(proper(X))
top(ok(X)) -> top(active(X))
- Signature:
{active/1,c/1,d/1,f/1,g/1,h/1,proper/1,top/1} / {mark/1,ok/1}
- Obligation:
runtime complexity wrt. defined symbols {active,c,d,f,g,h,proper,top} and constructors {mark,ok}
+ Applied Processor:
Bounds {initialAutomaton = perSymbol, enrichment = match}
+ Details:
The problem is match-bounded by 1.
The enriched problem is compatible with follwoing automaton.
active_0(7) -> 1
active_0(8) -> 1
active_1(7) -> 16
active_1(8) -> 16
c_0(7) -> 2
c_0(8) -> 2
c_1(7) -> 11
c_1(8) -> 11
d_0(7) -> 3
d_0(8) -> 3
d_1(7) -> 12
d_1(8) -> 12
f_0(7) -> 4
f_0(8) -> 4
f_1(7) -> 13
f_1(8) -> 13
g_0(7) -> 5
g_0(8) -> 5
g_1(7) -> 14
g_1(8) -> 14
h_0(7) -> 6
h_0(8) -> 6
h_1(7) -> 15
h_1(8) -> 15
mark_0(7) -> 7
mark_0(8) -> 7
mark_1(13) -> 4
mark_1(13) -> 13
mark_1(15) -> 6
mark_1(15) -> 15
ok_0(7) -> 8
ok_0(8) -> 8
ok_1(11) -> 2
ok_1(11) -> 11
ok_1(12) -> 3
ok_1(12) -> 12
ok_1(13) -> 4
ok_1(13) -> 13
ok_1(14) -> 5
ok_1(14) -> 14
ok_1(15) -> 6
ok_1(15) -> 15
proper_0(7) -> 9
proper_0(8) -> 9
proper_1(7) -> 16
proper_1(8) -> 16
top_0(7) -> 10
top_0(8) -> 10
top_1(16) -> 10
* Step 2: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
active(c(X)) -> mark(d(X))
active(f(X)) -> f(active(X))
active(f(f(X))) -> mark(c(f(g(f(X)))))
active(h(X)) -> h(active(X))
active(h(X)) -> mark(c(d(X)))
c(ok(X)) -> ok(c(X))
d(ok(X)) -> ok(d(X))
f(mark(X)) -> mark(f(X))
f(ok(X)) -> ok(f(X))
g(ok(X)) -> ok(g(X))
h(mark(X)) -> mark(h(X))
h(ok(X)) -> ok(h(X))
proper(c(X)) -> c(proper(X))
proper(d(X)) -> d(proper(X))
proper(f(X)) -> f(proper(X))
proper(g(X)) -> g(proper(X))
proper(h(X)) -> h(proper(X))
top(mark(X)) -> top(proper(X))
top(ok(X)) -> top(active(X))
- Signature:
{active/1,c/1,d/1,f/1,g/1,h/1,proper/1,top/1} / {mark/1,ok/1}
- Obligation:
runtime complexity wrt. defined symbols {active,c,d,f,g,h,proper,top} and constructors {mark,ok}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(?,O(n^1))