We consider the following Problem: Strict Trs: { double(0()) -> 0() , double(s(x)) -> s(s(double(x))) , +(x, 0()) -> x , +(x, s(y)) -> s(+(x, y)) , +(s(x), y) -> s(+(x, y)) , double(x) -> +(x, x)} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^2)) Proof: We consider the following Problem: Strict Trs: { double(0()) -> 0() , double(s(x)) -> s(s(double(x))) , +(x, 0()) -> x , +(x, s(y)) -> s(+(x, y)) , +(s(x), y) -> s(+(x, y)) , double(x) -> +(x, x)} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^2)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {double(0()) -> 0()} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(+) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [1 0] x1 + [1] [1 0] [1] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 0] [1] +(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 0] [0 0] [1] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { double(s(x)) -> s(s(double(x))) , +(x, 0()) -> x , +(x, s(y)) -> s(+(x, y)) , +(s(x), y) -> s(+(x, y)) , double(x) -> +(x, x)} Weak Trs: {double(0()) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^2)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {+(x, 0()) -> x} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(+) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [1 0] x1 + [1] [1 0] [1] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 0] [1] +(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 1] [0 0] [1] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { double(s(x)) -> s(s(double(x))) , +(x, s(y)) -> s(+(x, y)) , +(s(x), y) -> s(+(x, y)) , double(x) -> +(x, x)} Weak Trs: { +(x, 0()) -> x , double(0()) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^2)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {double(x) -> +(x, x)} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(+) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [1 0] x1 + [1] [0 1] [3] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 1] [2] +(x1, x2) = [1 0] x1 + [0 0] x2 + [0] [0 1] [0 0] [1] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { double(s(x)) -> s(s(double(x))) , +(x, s(y)) -> s(+(x, y)) , +(s(x), y) -> s(+(x, y))} Weak Trs: { double(x) -> +(x, x) , +(x, 0()) -> x , double(0()) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^2)) Proof: We consider the following Problem: Strict Trs: { double(s(x)) -> s(s(double(x))) , +(x, s(y)) -> s(+(x, y)) , +(s(x), y) -> s(+(x, y))} Weak Trs: { double(x) -> +(x, x) , +(x, 0()) -> x , double(0()) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^2)) Proof: The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(+) = {} We have the following restricted polynomial interpretation: Interpretation Functions: [double](x1) = 3*x1 + 3*x1^2 [0]() = 0 [s](x1) = 2 + x1 [+](x1, x2) = x1 + x1^2 + 2*x2 Hurray, we answered YES(?,O(n^2))