We consider the following Problem: Strict Trs: { double(0()) -> 0() , double(s(x)) -> s(s(double(x))) , half(0()) -> 0() , half(s(0())) -> 0() , half(s(s(x))) -> s(half(x)) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , if(0(), y, z) -> y , if(s(x), y, z) -> z , half(double(x)) -> x} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: We consider the following Problem: Strict Trs: { double(0()) -> 0() , double(s(x)) -> s(s(double(x))) , half(0()) -> 0() , half(s(0())) -> 0() , half(s(s(x))) -> s(half(x)) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , if(0(), y, z) -> y , if(s(x), y, z) -> z , half(double(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: { double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(half) = {}, Uargs(-) = {}, Uargs(if) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [0 0] x1 + [1] [1 0] [1] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 1] [0] half(x1) = [0 1] x1 + [1] [0 0] [1] -(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 0] [0 0] [1] if(x1, x2, x3) = [1 0] x1 + [1 0] x2 + [0 0] x3 + [1] [0 0] [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))) , half(s(s(x))) -> s(half(x)) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , if(0(), y, z) -> y , if(s(x), y, z) -> z , half(double(x)) -> x} Weak Trs: { double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {if(0(), y, z) -> y} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(half) = {}, Uargs(-) = {}, Uargs(if) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [0 0] x1 + [1] [1 0] [1] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 1] [0] half(x1) = [0 1] x1 + [1] [0 0] [1] -(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 0] [0 0] [1] if(x1, x2, x3) = [1 0] x1 + [1 0] x2 + [0 0] x3 + [1] [0 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))) , half(s(s(x))) -> s(half(x)) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , if(s(x), y, z) -> z , half(double(x)) -> x} Weak Trs: { if(0(), y, z) -> y , double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {if(s(x), y, z) -> z} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(half) = {}, Uargs(-) = {}, Uargs(if) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [0 0] x1 + [1] [1 0] [1] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 1] [0] half(x1) = [0 1] x1 + [1] [0 0] [1] -(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 0] [0 0] [1] if(x1, x2, x3) = [1 0] x1 + [1 0] x2 + [1 0] x3 + [1] [0 0] [0 1] [0 1] [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))) , half(s(s(x))) -> s(half(x)) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , half(double(x)) -> x} Weak Trs: { if(s(x), y, z) -> z , if(0(), y, z) -> y , double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) 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(half) = {}, Uargs(-) = {}, Uargs(if) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [0 0] x1 + [1] [1 0] [1] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 1] [0] half(x1) = [0 1] x1 + [1] [0 0] [1] -(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 1] [0 0] [1] if(x1, x2, x3) = [0 0] x1 + [1 0] x2 + [1 0] x3 + [1] [0 0] [0 1] [0 1] [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))) , half(s(s(x))) -> s(half(x)) , -(s(x), s(y)) -> -(x, y) , half(double(x)) -> x} Weak Trs: { -(x, 0()) -> x , if(s(x), y, z) -> z , if(0(), y, z) -> y , double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: { half(s(s(x))) -> s(half(x)) , -(s(x), s(y)) -> -(x, y)} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(half) = {}, Uargs(-) = {}, Uargs(if) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [0 0] x1 + [1] [1 0] [0] 0() = [0] [0] s(x1) = [1 0] x1 + [2] [0 1] [0] half(x1) = [1 1] x1 + [1] [0 0] [0] -(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 1] [0 0] [1] if(x1, x2, x3) = [0 0] x1 + [1 0] x2 + [1 0] x3 + [1] [0 0] [0 1] [0 1] [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))) , half(double(x)) -> x} Weak Trs: { half(s(s(x))) -> s(half(x)) , -(s(x), s(y)) -> -(x, y) , -(x, 0()) -> x , if(s(x), y, z) -> z , if(0(), y, z) -> y , double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The weightgap principle applies, where following rules are oriented strictly: TRS Component: {half(double(x)) -> x} Interpretation of nonconstant growth: ------------------------------------- The following argument positions are usable: Uargs(double) = {}, Uargs(s) = {1}, Uargs(half) = {}, Uargs(-) = {}, Uargs(if) = {} We have the following EDA-non-satisfying and IDA(1)-non-satisfying matrix interpretation: Interpretation Functions: double(x1) = [0 1] x1 + [1] [1 0] [1] 0() = [0] [0] s(x1) = [1 0] x1 + [0] [0 1] [0] half(x1) = [0 1] x1 + [0] [1 0] [0] -(x1, x2) = [1 0] x1 + [0 0] x2 + [1] [0 1] [0 0] [1] if(x1, x2, x3) = [0 0] x1 + [1 0] x2 + [1 0] x3 + [1] [0 0] [0 1] [0 1] [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)))} Weak Trs: { half(double(x)) -> x , half(s(s(x))) -> s(half(x)) , -(s(x), s(y)) -> -(x, y) , -(x, 0()) -> x , if(s(x), y, z) -> z , if(0(), y, z) -> y , double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: We consider the following Problem: Strict Trs: {double(s(x)) -> s(s(double(x)))} Weak Trs: { half(double(x)) -> x , half(s(s(x))) -> s(half(x)) , -(s(x), s(y)) -> -(x, y) , -(x, 0()) -> x , if(s(x), y, z) -> z , if(0(), y, z) -> y , double(0()) -> 0() , half(0()) -> 0() , half(s(0())) -> 0()} StartTerms: basic terms Strategy: innermost Certificate: YES(?,O(n^1)) Proof: The problem is match-bounded by 1. The enriched problem is compatible with the following automaton: { double_0(2) -> 1 , double_1(2) -> 4 , 0_0() -> 1 , 0_0() -> 2 , 0_1() -> 4 , s_0(1) -> 1 , s_0(2) -> 1 , s_0(2) -> 2 , s_1(3) -> 1 , s_1(3) -> 4 , s_1(4) -> 3 , half_0(2) -> 1 , -_0(2, 2) -> 1 , if_0(2, 2, 2) -> 1} Hurray, we answered YES(?,O(n^1))