We consider the following Problem: Strict Trs: { s(a()) -> a() , s(s(x)) -> x , s(f(x, y)) -> f(s(y), s(x)) , s(g(x, y)) -> g(s(x), s(y)) , f(x, a()) -> x , f(a(), y) -> y , f(g(x, y), g(u, v)) -> g(f(x, u), f(y, v)) , g(a(), a()) -> a()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: We consider the following Problem: Strict Trs: { s(a()) -> a() , s(s(x)) -> x , s(f(x, y)) -> f(s(y), s(x)) , s(g(x, y)) -> g(s(x), s(y)) , f(x, a()) -> x , f(a(), y) -> y , f(g(x, y), g(u, v)) -> g(f(x, u), f(y, v)) , g(a(), a()) -> a()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: { s(a()) -> a() , s(s(x)) -> x} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(s) = {}, Uargs(f) = {1, 2}, Uargs(g) = {1, 2} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: s(x1) = [1 0] x1 + [1] [0 1] [1] a() = [0] [0] f(x1, x2) = [1 0] x1 + [1 0] x2 + [0] [0 0] [0 0] [0] g(x1, x2) = [1 0] x1 + [1 0] x2 + [0] [0 0] [0 0] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { s(f(x, y)) -> f(s(y), s(x)) , s(g(x, y)) -> g(s(x), s(y)) , f(x, a()) -> x , f(a(), y) -> y , f(g(x, y), g(u, v)) -> g(f(x, u), f(y, v)) , g(a(), a()) -> a()} Weak Trs: { s(a()) -> a() , s(s(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, a()) -> x , f(a(), y) -> y , g(a(), a()) -> a()} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(s) = {}, Uargs(f) = {1, 2}, Uargs(g) = {1, 2} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: s(x1) = [0 1] x1 + [1] [1 0] [0] a() = [0] [0] f(x1, x2) = [1 0] x1 + [1 0] x2 + [1] [0 1] [0 1] [0] g(x1, x2) = [1 0] x1 + [1 0] x2 + [1] [0 1] [0 1] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { s(f(x, y)) -> f(s(y), s(x)) , s(g(x, y)) -> g(s(x), s(y)) , f(g(x, y), g(u, v)) -> g(f(x, u), f(y, v))} Weak Trs: { f(x, a()) -> x , f(a(), y) -> y , g(a(), a()) -> a() , s(a()) -> a() , s(s(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(g(x, y), g(u, v)) -> g(f(x, u), f(y, v))} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(s) = {}, Uargs(f) = {1, 2}, Uargs(g) = {1, 2} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: s(x1) = [0 1] x1 + [1] [1 0] [0] a() = [0] [0] f(x1, x2) = [1 0] x1 + [1 0] x2 + [1] [0 1] [0 1] [0] g(x1, x2) = [1 0] x1 + [1 0] x2 + [3] [0 1] [0 1] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { s(f(x, y)) -> f(s(y), s(x)) , s(g(x, y)) -> g(s(x), s(y))} Weak Trs: { f(g(x, y), g(u, v)) -> g(f(x, u), f(y, v)) , f(x, a()) -> x , f(a(), y) -> y , g(a(), a()) -> a() , s(a()) -> a() , s(s(x)) -> x} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: We consider the following Problem: Strict Trs: { s(f(x, y)) -> f(s(y), s(x)) , s(g(x, y)) -> g(s(x), s(y))} Weak Trs: { f(g(x, y), g(u, v)) -> g(f(x, u), f(y, v)) , f(x, a()) -> x , f(a(), y) -> y , g(a(), a()) -> a() , s(a()) -> a() , s(s(x)) -> x} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The problem is match-bounded by 0. The enriched problem is compatible with the following automaton: { s_0(2) -> 1 , a_0() -> 1 , a_0() -> 2 , f_0(2, 2) -> 1 , g_0(2, 2) -> 1} Hurray, we answered YES(?,O(n^1))