* Step 1: Sum WORST_CASE(Omega(n^1),O(n^1))
+ Considered Problem:
- Strict TRS:
a__c(X) -> c(X)
a__c(X) -> d(X)
a__f(X) -> f(X)
a__f(f(X)) -> a__c(f(g(f(X))))
a__h(X) -> a__c(d(X))
a__h(X) -> h(X)
mark(c(X)) -> a__c(X)
mark(d(X)) -> d(X)
mark(f(X)) -> a__f(mark(X))
mark(g(X)) -> g(X)
mark(h(X)) -> a__h(mark(X))
- Signature:
{a__c/1,a__f/1,a__h/1,mark/1} / {c/1,d/1,f/1,g/1,h/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {a__c,a__f,a__h,mark} and constructors {c,d,f,g,h}
+ Applied Processor:
Sum {left = someStrategy, right = someStrategy}
+ Details:
()
** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?)
+ Considered Problem:
- Strict TRS:
a__c(X) -> c(X)
a__c(X) -> d(X)
a__f(X) -> f(X)
a__f(f(X)) -> a__c(f(g(f(X))))
a__h(X) -> a__c(d(X))
a__h(X) -> h(X)
mark(c(X)) -> a__c(X)
mark(d(X)) -> d(X)
mark(f(X)) -> a__f(mark(X))
mark(g(X)) -> g(X)
mark(h(X)) -> a__h(mark(X))
- Signature:
{a__c/1,a__f/1,a__h/1,mark/1} / {c/1,d/1,f/1,g/1,h/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {a__c,a__f,a__h,mark} and constructors {c,d,f,g,h}
+ Applied Processor:
DecreasingLoops {bound = AnyLoop, narrow = 10}
+ Details:
The system has following decreasing Loops:
mark(x){x -> f(x)} =
mark(f(x)) ->^+ a__f(mark(x))
= C[mark(x) = mark(x){}]
** Step 1.b:1: Bounds WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
a__c(X) -> c(X)
a__c(X) -> d(X)
a__f(X) -> f(X)
a__f(f(X)) -> a__c(f(g(f(X))))
a__h(X) -> a__c(d(X))
a__h(X) -> h(X)
mark(c(X)) -> a__c(X)
mark(d(X)) -> d(X)
mark(f(X)) -> a__f(mark(X))
mark(g(X)) -> g(X)
mark(h(X)) -> a__h(mark(X))
- Signature:
{a__c/1,a__f/1,a__h/1,mark/1} / {c/1,d/1,f/1,g/1,h/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {a__c,a__f,a__h,mark} and constructors {c,d,f,g,h}
+ Applied Processor:
Bounds {initialAutomaton = perSymbol, enrichment = match}
+ Details:
The problem is match-bounded by 3.
The enriched problem is compatible with follwoing automaton.
a__c_0(4) -> 1
a__c_0(5) -> 1
a__c_0(6) -> 1
a__c_0(7) -> 1
a__c_0(8) -> 1
a__c_1(1) -> 3
a__c_1(4) -> 9
a__c_1(4) -> 12
a__c_1(5) -> 9
a__c_1(5) -> 12
a__c_1(6) -> 9
a__c_1(6) -> 12
a__c_1(7) -> 9
a__c_1(7) -> 12
a__c_1(8) -> 9
a__c_1(8) -> 12
a__c_1(10) -> 2
a__c_2(13) -> 9
a__c_2(13) -> 12
a__f_0(4) -> 2
a__f_0(5) -> 2
a__f_0(6) -> 2
a__f_0(7) -> 2
a__f_0(8) -> 2
a__f_1(12) -> 9
a__f_1(12) -> 12
a__h_0(4) -> 3
a__h_0(5) -> 3
a__h_0(6) -> 3
a__h_0(7) -> 3
a__h_0(8) -> 3
a__h_1(12) -> 9
a__h_1(12) -> 12
c_0(4) -> 4
c_0(5) -> 4
c_0(6) -> 4
c_0(7) -> 4
c_0(8) -> 4
c_1(4) -> 1
c_1(5) -> 1
c_1(6) -> 1
c_1(7) -> 1
c_1(8) -> 1
c_2(1) -> 3
c_2(4) -> 9
c_2(4) -> 12
c_2(5) -> 9
c_2(5) -> 12
c_2(6) -> 9
c_2(6) -> 12
c_2(7) -> 9
c_2(7) -> 12
c_2(8) -> 9
c_2(8) -> 12
c_2(10) -> 2
c_3(13) -> 9
c_3(13) -> 12
d_0(4) -> 5
d_0(5) -> 5
d_0(6) -> 5
d_0(7) -> 5
d_0(8) -> 5
d_1(4) -> 1
d_1(4) -> 9
d_1(4) -> 12
d_1(5) -> 1
d_1(5) -> 9
d_1(5) -> 12
d_1(6) -> 1
d_1(6) -> 9
d_1(6) -> 12
d_1(7) -> 1
d_1(7) -> 9
d_1(7) -> 12
d_1(8) -> 1
d_1(8) -> 9
d_1(8) -> 12
d_2(1) -> 3
d_2(4) -> 9
d_2(4) -> 12
d_2(5) -> 9
d_2(5) -> 12
d_2(6) -> 9
d_2(6) -> 12
d_2(7) -> 9
d_2(7) -> 12
d_2(8) -> 9
d_2(8) -> 12
d_2(10) -> 2
d_2(12) -> 13
d_3(13) -> 9
d_3(13) -> 12
f_0(4) -> 6
f_0(5) -> 6
f_0(6) -> 6
f_0(7) -> 6
f_0(8) -> 6
f_1(4) -> 2
f_1(5) -> 2
f_1(6) -> 2
f_1(7) -> 2
f_1(8) -> 2
f_1(11) -> 10
f_2(12) -> 9
f_2(12) -> 12
f_2(14) -> 13
g_0(4) -> 7
g_0(5) -> 7
g_0(6) -> 7
g_0(7) -> 7
g_0(8) -> 7
g_1(2) -> 11
g_1(4) -> 9
g_1(4) -> 12
g_1(5) -> 9
g_1(5) -> 12
g_1(6) -> 9
g_1(6) -> 12
g_1(7) -> 9
g_1(7) -> 12
g_1(8) -> 9
g_1(8) -> 12
g_2(12) -> 14
h_0(4) -> 8
h_0(5) -> 8
h_0(6) -> 8
h_0(7) -> 8
h_0(8) -> 8
h_1(4) -> 3
h_1(5) -> 3
h_1(6) -> 3
h_1(7) -> 3
h_1(8) -> 3
h_2(12) -> 9
h_2(12) -> 12
mark_0(4) -> 9
mark_0(5) -> 9
mark_0(6) -> 9
mark_0(7) -> 9
mark_0(8) -> 9
mark_1(4) -> 12
mark_1(5) -> 12
mark_1(6) -> 12
mark_1(7) -> 12
mark_1(8) -> 12
** Step 1.b:2: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
a__c(X) -> c(X)
a__c(X) -> d(X)
a__f(X) -> f(X)
a__f(f(X)) -> a__c(f(g(f(X))))
a__h(X) -> a__c(d(X))
a__h(X) -> h(X)
mark(c(X)) -> a__c(X)
mark(d(X)) -> d(X)
mark(f(X)) -> a__f(mark(X))
mark(g(X)) -> g(X)
mark(h(X)) -> a__h(mark(X))
- Signature:
{a__c/1,a__f/1,a__h/1,mark/1} / {c/1,d/1,f/1,g/1,h/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {a__c,a__f,a__h,mark} and constructors {c,d,f,g,h}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(Omega(n^1),O(n^1))