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