We consider the following Problem: Strict Trs: { h(X) -> g(X, X) , g(a(), X) -> f(b(), activate(X)) , f(X, X) -> h(a()) , a() -> b() , activate(X) -> X} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: Arguments of following rules are not normal-forms: {g(a(), X) -> f(b(), activate(X))} All above mentioned rules can be savely removed. We consider the following Problem: Strict Trs: { h(X) -> g(X, X) , f(X, X) -> h(a()) , a() -> b() , activate(X) -> X} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {f(X, X) -> h(a())} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(h) = {1}, Uargs(g) = {}, Uargs(f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: h(x1) = [1 0] x1 + [1] [0 0] [1] g(x1, x2) = [0 0] x1 + [0 0] x2 + [0] [0 0] [1 0] [0] a() = [0] [0] f(x1, x2) = [0 0] x1 + [0 0] x2 + [2] [0 0] [0 0] [2] b() = [0] [0] activate(x1) = [1 0] x1 + [0] [0 0] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { h(X) -> g(X, X) , a() -> b() , activate(X) -> X} Weak Trs: {f(X, X) -> h(a())} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {a() -> b()} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(h) = {1}, Uargs(g) = {}, Uargs(f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: h(x1) = [1 0] x1 + [1] [0 0] [1] g(x1, x2) = [0 0] x1 + [0 0] x2 + [0] [0 0] [1 0] [0] a() = [2] [0] f(x1, x2) = [0 0] x1 + [0 0] x2 + [3] [0 0] [0 0] [2] b() = [0] [0] activate(x1) = [1 0] x1 + [0] [0 0] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { h(X) -> g(X, X) , activate(X) -> X} Weak Trs: { a() -> b() , f(X, X) -> h(a())} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {h(X) -> g(X, X)} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(h) = {1}, Uargs(g) = {}, Uargs(f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: h(x1) = [1 0] x1 + [1] [1 0] [1] g(x1, x2) = [0 0] x1 + [0 0] x2 + [0] [1 0] [0 0] [0] a() = [0] [0] f(x1, x2) = [0 0] x1 + [0 0] x2 + [2] [0 0] [0 0] [2] b() = [0] [0] activate(x1) = [1 0] x1 + [0] [0 0] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: {activate(X) -> X} Weak Trs: { h(X) -> g(X, X) , a() -> b() , f(X, X) -> h(a())} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {activate(X) -> X} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(h) = {1}, Uargs(g) = {}, Uargs(f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: h(x1) = [1 0] x1 + [1] [0 1] [1] g(x1, x2) = [0 0] x1 + [0 0] x2 + [0] [0 0] [0 1] [0] a() = [0] [0] f(x1, x2) = [1 0] x1 + [0 0] x2 + [2] [0 1] [0 0] [2] b() = [0] [0] activate(x1) = [1 0] x1 + [2] [0 1] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Weak Trs: { activate(X) -> X , h(X) -> g(X, X) , a() -> b() , f(X, X) -> h(a())} StartTerms: basic terms Strategy: innermost Certificate: YES(O(1),O(1)) Proof: We consider the following Problem: Weak Trs: { activate(X) -> X , h(X) -> g(X, X) , a() -> b() , f(X, X) -> h(a())} StartTerms: basic terms Strategy: innermost Certificate: YES(O(1),O(1)) Proof: Empty rules are trivially bounded Hurray, we answered YES(?,O(n^1))