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