We consider the following Problem: Strict Trs: { f(X) -> if(X, c(), n__f(n__true())) , if(true(), X, Y) -> X , if(false(), X, Y) -> activate(Y) , f(X) -> n__f(X) , true() -> n__true() , activate(n__f(X)) -> f(activate(X)) , activate(n__true()) -> true() , activate(X) -> X} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: Arguments of following rules are not normal-forms: {if(true(), X, Y) -> X} All above mentioned rules can be savely removed. We consider the following Problem: Strict Trs: { f(X) -> if(X, c(), n__f(n__true())) , if(false(), X, Y) -> activate(Y) , f(X) -> n__f(X) , true() -> n__true() , activate(n__f(X)) -> f(activate(X)) , activate(n__true()) -> true() , 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: {true() -> n__true()} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(f) = {1}, Uargs(if) = {}, Uargs(n__f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: f(x1) = [1 0] x1 + [0] [0 0] [1] if(x1, x2, x3) = [1 0] x1 + [1 0] x2 + [0 0] x3 + [1] [1 0] [0 0] [0 0] [1] c() = [0] [0] n__f(x1) = [1 0] x1 + [0] [0 0] [0] n__true() = [0] [0] true() = [2] [0] false() = [0] [0] activate(x1) = [1 0] x1 + [1] [1 0] [1] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { f(X) -> if(X, c(), n__f(n__true())) , if(false(), X, Y) -> activate(Y) , f(X) -> n__f(X) , activate(n__f(X)) -> f(activate(X)) , activate(n__true()) -> true() , activate(X) -> X} Weak Trs: {true() -> n__true()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {activate(n__true()) -> true()} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(f) = {1}, Uargs(if) = {}, Uargs(n__f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: f(x1) = [1 0] x1 + [0] [0 0] [1] if(x1, x2, x3) = [1 0] x1 + [1 0] x2 + [0 0] x3 + [1] [1 0] [0 0] [0 0] [1] c() = [0] [0] n__f(x1) = [1 0] x1 + [0] [0 0] [0] n__true() = [0] [0] true() = [0] [0] false() = [0] [0] activate(x1) = [1 0] x1 + [1] [1 0] [1] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { f(X) -> if(X, c(), n__f(n__true())) , if(false(), X, Y) -> activate(Y) , f(X) -> n__f(X) , activate(n__f(X)) -> f(activate(X)) , activate(X) -> X} Weak Trs: { activate(n__true()) -> true() , true() -> n__true()} 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) -> if(X, c(), n__f(n__true())) , f(X) -> n__f(X)} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(f) = {1}, Uargs(if) = {}, Uargs(n__f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: f(x1) = [1 0] x1 + [2] [0 0] [1] if(x1, x2, x3) = [0 0] x1 + [1 0] x2 + [0 0] x3 + [1] [0 0] [1 0] [0 0] [1] c() = [0] [0] n__f(x1) = [1 0] x1 + [0] [0 0] [0] n__true() = [0] [0] true() = [0] [0] false() = [0] [0] activate(x1) = [1 0] x1 + [1] [1 0] [1] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { if(false(), X, Y) -> activate(Y) , activate(n__f(X)) -> f(activate(X)) , activate(X) -> X} Weak Trs: { f(X) -> if(X, c(), n__f(n__true())) , f(X) -> n__f(X) , activate(n__true()) -> true() , true() -> n__true()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {if(false(), X, Y) -> activate(Y)} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(f) = {1}, Uargs(if) = {}, Uargs(n__f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: f(x1) = [1 0] x1 + [1] [0 0] [1] if(x1, x2, x3) = [0 0] x1 + [1 0] x2 + [1 0] x3 + [1] [0 0] [1 0] [1 0] [1] c() = [0] [0] n__f(x1) = [1 0] x1 + [0] [0 0] [0] n__true() = [0] [0] true() = [0] [0] false() = [0] [0] activate(x1) = [1 0] x1 + [0] [1 0] [0] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: { activate(n__f(X)) -> f(activate(X)) , activate(X) -> X} Weak Trs: { if(false(), X, Y) -> activate(Y) , f(X) -> if(X, c(), n__f(n__true())) , f(X) -> n__f(X) , activate(n__true()) -> true() , true() -> n__true()} 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(f) = {1}, Uargs(if) = {}, Uargs(n__f) = {}, Uargs(activate) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: f(x1) = [1 2] x1 + [0] [0 0] [3] if(x1, x2, x3) = [1 0] x1 + [1 0] x2 + [1 0] x3 + [0] [0 0] [0 1] [0 1] [3] c() = [0] [0] n__f(x1) = [1 2] x1 + [0] [0 0] [0] n__true() = [0] [0] true() = [0] [0] false() = [2] [0] activate(x1) = [1 0] x1 + [1] [0 1] [2] The strictly oriented rules are moved into the weak component. We consider the following Problem: Strict Trs: {activate(n__f(X)) -> f(activate(X))} Weak Trs: { activate(X) -> X , if(false(), X, Y) -> activate(Y) , f(X) -> if(X, c(), n__f(n__true())) , f(X) -> n__f(X) , activate(n__true()) -> true() , true() -> n__true()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: We consider the following Problem: Strict Trs: {activate(n__f(X)) -> f(activate(X))} Weak Trs: { activate(X) -> X , if(false(), X, Y) -> activate(Y) , f(X) -> if(X, c(), n__f(n__true())) , f(X) -> n__f(X) , activate(n__true()) -> true() , true() -> n__true()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The problem is match-bounded by 2. The enriched problem is compatible with the following automaton: { f_0(2) -> 1 , f_1(3) -> 1 , f_1(3) -> 3 , f_2(7) -> 1 , f_2(7) -> 3 , if_0(2, 2, 2) -> 1 , if_1(2, 4, 5) -> 1 , if_1(3, 4, 5) -> 1 , if_1(3, 4, 5) -> 3 , if_2(3, 8, 9) -> 1 , if_2(3, 8, 9) -> 3 , if_2(7, 8, 9) -> 1 , if_2(7, 8, 9) -> 3 , c_0() -> 1 , c_0() -> 2 , c_0() -> 3 , c_1() -> 4 , c_2() -> 8 , n__f_0(2) -> 1 , n__f_0(2) -> 2 , n__f_0(2) -> 3 , n__f_1(3) -> 1 , n__f_1(3) -> 3 , n__f_1(6) -> 1 , n__f_1(6) -> 3 , n__f_1(6) -> 5 , n__f_2(7) -> 1 , n__f_2(7) -> 3 , n__f_2(10) -> 1 , n__f_2(10) -> 3 , n__f_2(10) -> 9 , n__true_0() -> 1 , n__true_0() -> 2 , n__true_0() -> 3 , n__true_1() -> 3 , n__true_1() -> 6 , n__true_1() -> 7 , n__true_2() -> 7 , n__true_2() -> 10 , true_0() -> 1 , true_1() -> 3 , true_2() -> 7 , false_0() -> 1 , false_0() -> 2 , false_0() -> 3 , activate_0(2) -> 1 , activate_1(2) -> 3 , activate_1(5) -> 1 , activate_1(5) -> 3 , activate_1(9) -> 1 , activate_1(9) -> 3 , activate_2(6) -> 7 , activate_2(10) -> 7} Hurray, we answered YES(?,O(n^1))