WORST_CASE(?,O(n^1)) * Step 1: InnermostRuleRemoval WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(X) -> X a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) a(nt(X)) -> t(a(X)) d(0()) -> 0() d(s(X)) -> s(s(d(X))) f(X1,X2) -> nf(X1,X2) f(0(),X) -> nil() f(s(X),cs(Y,Z)) -> cs(Y,nf(X,a(Z))) p(X,0()) -> X p(0(),X) -> X p(s(X),s(Y)) -> s(s(p(X,Y))) q(0()) -> 0() q(s(X)) -> s(p(q(X),d(X))) s(X) -> ns(X) t(N) -> cs(r(q(N)),nt(ns(N))) t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: InnermostRuleRemoval + Details: Arguments of following rules are not normal-forms. d(s(X)) -> s(s(d(X))) f(s(X),cs(Y,Z)) -> cs(Y,nf(X,a(Z))) p(s(X),s(Y)) -> s(s(p(X,Y))) q(s(X)) -> s(p(q(X),d(X))) All above mentioned rules can be savely removed. * Step 2: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(X) -> X a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) a(nt(X)) -> t(a(X)) d(0()) -> 0() f(X1,X2) -> nf(X1,X2) f(0(),X) -> nil() p(X,0()) -> X p(0(),X) -> X q(0()) -> 0() s(X) -> ns(X) t(N) -> cs(r(q(N)),nt(ns(N))) t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(cs) = {1}, uargs(f) = {1,2}, uargs(r) = {1}, uargs(s) = {1}, uargs(t) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [4] p(a) = [1] x1 + [14] p(cs) = [1] x1 + [6] p(d) = [0] p(f) = [1] x1 + [1] x2 + [0] p(nf) = [1] x1 + [1] x2 + [0] p(nil) = [0] p(ns) = [1] x1 + [0] p(nt) = [1] x1 + [0] p(p) = [4] x1 + [6] x2 + [0] p(q) = [0] p(r) = [1] x1 + [0] p(s) = [1] x1 + [0] p(t) = [1] x1 + [1] Following rules are strictly oriented: a(X) = [1] X + [14] > [1] X + [0] = X f(0(),X) = [1] X + [4] > [0] = nil() p(X,0()) = [4] X + [24] > [1] X + [0] = X p(0(),X) = [6] X + [16] > [1] X + [0] = X t(X) = [1] X + [1] > [1] X + [0] = nt(X) Following rules are (at-least) weakly oriented: a(nf(X1,X2)) = [1] X1 + [1] X2 + [14] >= [1] X1 + [1] X2 + [28] = f(a(X1),a(X2)) a(ns(X)) = [1] X + [14] >= [1] X + [14] = s(a(X)) a(nt(X)) = [1] X + [14] >= [1] X + [15] = t(a(X)) d(0()) = [0] >= [4] = 0() f(X1,X2) = [1] X1 + [1] X2 + [0] >= [1] X1 + [1] X2 + [0] = nf(X1,X2) q(0()) = [0] >= [4] = 0() s(X) = [1] X + [0] >= [1] X + [0] = ns(X) t(N) = [1] N + [1] >= [6] = cs(r(q(N)),nt(ns(N))) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) a(nt(X)) -> t(a(X)) d(0()) -> 0() f(X1,X2) -> nf(X1,X2) q(0()) -> 0() s(X) -> ns(X) t(N) -> cs(r(q(N)),nt(ns(N))) - Weak TRS: a(X) -> X f(0(),X) -> nil() p(X,0()) -> X p(0(),X) -> X t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(cs) = {1}, uargs(f) = {1,2}, uargs(r) = {1}, uargs(s) = {1}, uargs(t) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [4] p(a) = [8] x1 + [3] p(cs) = [1] x1 + [0] p(d) = [0] p(f) = [1] x1 + [1] x2 + [2] p(nf) = [1] x1 + [1] x2 + [0] p(nil) = [1] p(ns) = [1] x1 + [0] p(nt) = [1] x1 + [0] p(p) = [4] x1 + [1] x2 + [7] p(q) = [0] p(r) = [1] x1 + [0] p(s) = [1] x1 + [0] p(t) = [1] x1 + [0] Following rules are strictly oriented: f(X1,X2) = [1] X1 + [1] X2 + [2] > [1] X1 + [1] X2 + [0] = nf(X1,X2) Following rules are (at-least) weakly oriented: a(X) = [8] X + [3] >= [1] X + [0] = X a(nf(X1,X2)) = [8] X1 + [8] X2 + [3] >= [8] X1 + [8] X2 + [8] = f(a(X1),a(X2)) a(ns(X)) = [8] X + [3] >= [8] X + [3] = s(a(X)) a(nt(X)) = [8] X + [3] >= [8] X + [3] = t(a(X)) d(0()) = [0] >= [4] = 0() f(0(),X) = [1] X + [6] >= [1] = nil() p(X,0()) = [4] X + [11] >= [1] X + [0] = X p(0(),X) = [1] X + [23] >= [1] X + [0] = X q(0()) = [0] >= [4] = 0() s(X) = [1] X + [0] >= [1] X + [0] = ns(X) t(N) = [1] N + [0] >= [0] = cs(r(q(N)),nt(ns(N))) t(X) = [1] X + [0] >= [1] X + [0] = nt(X) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 4: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) a(nt(X)) -> t(a(X)) d(0()) -> 0() q(0()) -> 0() s(X) -> ns(X) t(N) -> cs(r(q(N)),nt(ns(N))) - Weak TRS: a(X) -> X f(X1,X2) -> nf(X1,X2) f(0(),X) -> nil() p(X,0()) -> X p(0(),X) -> X t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(cs) = {1}, uargs(f) = {1,2}, uargs(r) = {1}, uargs(s) = {1}, uargs(t) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [2] p(a) = [2] x1 + [0] p(cs) = [1] x1 + [9] p(d) = [0] p(f) = [1] x1 + [1] x2 + [10] p(nf) = [1] x1 + [1] x2 + [4] p(nil) = [1] p(ns) = [1] x1 + [0] p(nt) = [1] x1 + [8] p(p) = [1] x1 + [8] x2 + [8] p(q) = [1] x1 + [4] p(r) = [1] x1 + [8] p(s) = [1] x1 + [0] p(t) = [1] x1 + [9] Following rules are strictly oriented: a(nt(X)) = [2] X + [16] > [2] X + [9] = t(a(X)) q(0()) = [6] > [2] = 0() Following rules are (at-least) weakly oriented: a(X) = [2] X + [0] >= [1] X + [0] = X a(nf(X1,X2)) = [2] X1 + [2] X2 + [8] >= [2] X1 + [2] X2 + [10] = f(a(X1),a(X2)) a(ns(X)) = [2] X + [0] >= [2] X + [0] = s(a(X)) d(0()) = [0] >= [2] = 0() f(X1,X2) = [1] X1 + [1] X2 + [10] >= [1] X1 + [1] X2 + [4] = nf(X1,X2) f(0(),X) = [1] X + [12] >= [1] = nil() p(X,0()) = [1] X + [24] >= [1] X + [0] = X p(0(),X) = [8] X + [10] >= [1] X + [0] = X s(X) = [1] X + [0] >= [1] X + [0] = ns(X) t(N) = [1] N + [9] >= [1] N + [21] = cs(r(q(N)),nt(ns(N))) t(X) = [1] X + [9] >= [1] X + [8] = nt(X) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 5: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) d(0()) -> 0() s(X) -> ns(X) t(N) -> cs(r(q(N)),nt(ns(N))) - Weak TRS: a(X) -> X a(nt(X)) -> t(a(X)) f(X1,X2) -> nf(X1,X2) f(0(),X) -> nil() p(X,0()) -> X p(0(),X) -> X q(0()) -> 0() t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(cs) = {1}, uargs(f) = {1,2}, uargs(r) = {1}, uargs(s) = {1}, uargs(t) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [8] p(a) = [1] x1 + [3] p(cs) = [1] x1 + [8] p(d) = [2] x1 + [2] p(f) = [1] x1 + [1] x2 + [0] p(nf) = [1] x1 + [1] x2 + [0] p(nil) = [4] p(ns) = [1] x1 + [0] p(nt) = [1] x1 + [0] p(p) = [1] x1 + [2] x2 + [5] p(q) = [8] p(r) = [1] x1 + [3] p(s) = [1] x1 + [0] p(t) = [1] x1 + [0] Following rules are strictly oriented: d(0()) = [18] > [8] = 0() Following rules are (at-least) weakly oriented: a(X) = [1] X + [3] >= [1] X + [0] = X a(nf(X1,X2)) = [1] X1 + [1] X2 + [3] >= [1] X1 + [1] X2 + [6] = f(a(X1),a(X2)) a(ns(X)) = [1] X + [3] >= [1] X + [3] = s(a(X)) a(nt(X)) = [1] X + [3] >= [1] X + [3] = t(a(X)) f(X1,X2) = [1] X1 + [1] X2 + [0] >= [1] X1 + [1] X2 + [0] = nf(X1,X2) f(0(),X) = [1] X + [8] >= [4] = nil() p(X,0()) = [1] X + [21] >= [1] X + [0] = X p(0(),X) = [2] X + [13] >= [1] X + [0] = X q(0()) = [8] >= [8] = 0() s(X) = [1] X + [0] >= [1] X + [0] = ns(X) t(N) = [1] N + [0] >= [19] = cs(r(q(N)),nt(ns(N))) t(X) = [1] X + [0] >= [1] X + [0] = nt(X) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 6: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) s(X) -> ns(X) t(N) -> cs(r(q(N)),nt(ns(N))) - Weak TRS: a(X) -> X a(nt(X)) -> t(a(X)) d(0()) -> 0() f(X1,X2) -> nf(X1,X2) f(0(),X) -> nil() p(X,0()) -> X p(0(),X) -> X q(0()) -> 0() t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(cs) = {1}, uargs(f) = {1,2}, uargs(r) = {1}, uargs(s) = {1}, uargs(t) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [0] p(a) = [10] x1 + [8] p(cs) = [1] x1 + [0] p(d) = [0] p(f) = [1] x1 + [1] x2 + [11] p(nf) = [1] x1 + [1] x2 + [2] p(nil) = [0] p(ns) = [1] x1 + [1] p(nt) = [1] x1 + [1] p(p) = [2] x1 + [2] x2 + [0] p(q) = [8] p(r) = [1] x1 + [0] p(s) = [1] x1 + [1] p(t) = [1] x1 + [10] Following rules are strictly oriented: a(nf(X1,X2)) = [10] X1 + [10] X2 + [28] > [10] X1 + [10] X2 + [27] = f(a(X1),a(X2)) a(ns(X)) = [10] X + [18] > [10] X + [9] = s(a(X)) t(N) = [1] N + [10] > [8] = cs(r(q(N)),nt(ns(N))) Following rules are (at-least) weakly oriented: a(X) = [10] X + [8] >= [1] X + [0] = X a(nt(X)) = [10] X + [18] >= [10] X + [18] = t(a(X)) d(0()) = [0] >= [0] = 0() f(X1,X2) = [1] X1 + [1] X2 + [11] >= [1] X1 + [1] X2 + [2] = nf(X1,X2) f(0(),X) = [1] X + [11] >= [0] = nil() p(X,0()) = [2] X + [0] >= [1] X + [0] = X p(0(),X) = [2] X + [0] >= [1] X + [0] = X q(0()) = [8] >= [0] = 0() s(X) = [1] X + [1] >= [1] X + [1] = ns(X) t(X) = [1] X + [10] >= [1] X + [1] = nt(X) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 7: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: s(X) -> ns(X) - Weak TRS: a(X) -> X a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) a(nt(X)) -> t(a(X)) d(0()) -> 0() f(X1,X2) -> nf(X1,X2) f(0(),X) -> nil() p(X,0()) -> X p(0(),X) -> X q(0()) -> 0() t(N) -> cs(r(q(N)),nt(ns(N))) t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(cs) = {1}, uargs(f) = {1,2}, uargs(r) = {1}, uargs(s) = {1}, uargs(t) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [0] p(a) = [11] x1 + [0] p(cs) = [1] x1 + [0] p(d) = [0] p(f) = [1] x1 + [1] x2 + [0] p(nf) = [1] x1 + [1] x2 + [0] p(nil) = [0] p(ns) = [1] x1 + [1] p(nt) = [1] x1 + [0] p(p) = [2] x1 + [2] x2 + [0] p(q) = [1] x1 + [0] p(r) = [1] x1 + [0] p(s) = [1] x1 + [11] p(t) = [1] x1 + [0] Following rules are strictly oriented: s(X) = [1] X + [11] > [1] X + [1] = ns(X) Following rules are (at-least) weakly oriented: a(X) = [11] X + [0] >= [1] X + [0] = X a(nf(X1,X2)) = [11] X1 + [11] X2 + [0] >= [11] X1 + [11] X2 + [0] = f(a(X1),a(X2)) a(ns(X)) = [11] X + [11] >= [11] X + [11] = s(a(X)) a(nt(X)) = [11] X + [0] >= [11] X + [0] = t(a(X)) d(0()) = [0] >= [0] = 0() f(X1,X2) = [1] X1 + [1] X2 + [0] >= [1] X1 + [1] X2 + [0] = nf(X1,X2) f(0(),X) = [1] X + [0] >= [0] = nil() p(X,0()) = [2] X + [0] >= [1] X + [0] = X p(0(),X) = [2] X + [0] >= [1] X + [0] = X q(0()) = [0] >= [0] = 0() t(N) = [1] N + [0] >= [1] N + [0] = cs(r(q(N)),nt(ns(N))) t(X) = [1] X + [0] >= [1] X + [0] = nt(X) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 8: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: a(X) -> X a(nf(X1,X2)) -> f(a(X1),a(X2)) a(ns(X)) -> s(a(X)) a(nt(X)) -> t(a(X)) d(0()) -> 0() f(X1,X2) -> nf(X1,X2) f(0(),X) -> nil() p(X,0()) -> X p(0(),X) -> X q(0()) -> 0() s(X) -> ns(X) t(N) -> cs(r(q(N)),nt(ns(N))) t(X) -> nt(X) - Signature: {a/1,d/1,f/2,p/2,q/1,s/1,t/1} / {0/0,cs/2,nf/2,nil/0,ns/1,nt/1,r/1} - Obligation: innermost runtime complexity wrt. defined symbols {a,d,f,p,q,s,t} and constructors {0,cs,nf,nil,ns,nt,r} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))